자료구조 & 알고리즘 (그래프)

그래프

정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조

정점 집합과 간선 집합으로 표현할 수 있다.

그래프의 특징

▶정점은 여러 개의 간선을 가질 수 있다.

▶크게 방향 그래프와 무방향 그래프로 나눌 수 있다.

▶간선은 가중치를 가질 수 있다.

▶사이클이 발생할 수 있다.

무방향 그래프

간선으로 이어진 정점끼리는 양방향으로 이동이 가능하다.

표현하기에(A,B)와(B,A)는 같은 간선으로 취급한다.

ex) 양방향 통행도로

방향 그래프

간선에 방향성이 존재하는 그래프

양방향으로 갈 수 있더라도 <A,B>와 <B,A>는 다른 간선으로 취급한다.

ex) 일반통행

연결 그래프

모든 정점이 서로 연결 가능한 상태인 그래프

비연결 그래프

특정 정점쌍 사이에 간선이 존재하지 않는 그래프

ex) 친한 친구 설문 그래프

완전 그래프

모든 정점끼리 연결된 상태인 그래프

사이클

그래프의 정점과 간선의 부분 집합에서 순환이 되는 부분

그래프의 구현 방법

인접행렬, 인접 리스트 두가지 방식으로 그래프를 표현할 수 있다.

JavaScript에서 사용법

인접행렬

인접 리스트