그래프 (Graph)

이번 포스트에서는 자료구조 상의 그래프(Graph)에 대해 다루도록 하겠습니다.

 

그래프란?

: 그래프는 2개의 집합 V와 E로 구성됩니다. 이때 V는 공집합이 아닌 정점(vertex)의 유한 집합이고 E는 간선(edge)들의 집합입니다.

 

그래프의 특징 :

• 2개이상의 경로가 가능하다.
• 루트 노드라는 개념이 없다.
• 부모-자식 관계라는 개념이 없다.

그래프에 사용되는 용어 :

• 정점(vertex) : 위치라는 개념
• 간선(edge) : 위치 간의 관계, 즉 노드를 연결하는 선
• 완전 그래프(Complete graph) : 간선의 수가 최대인 그래프
• 인접(adjacent) : 간선에 의해 직접 연결된다
• 부분 그래프(Subgraph) : V(G')⊆V(G)이고 E(G')⊆E(G)일 경우, G'는 G의 부분 그래프
• 경로의 길이 : 경로 상에 있는 간선의 수
• 단순 경로(simple path) : 처음과 마지막을 제외한 정점이 다른 경우
• 사이클(cycle) : 처음과 마지막이 동일한 단순 경로
• 연결(connected) : 정점 u와 v사이에 경로가 존재할 경우, u와 v는 연결
• 연결 요소(connected component) : 최대 연결 부분 그래프

그래프의 종류 :

• 무방향성 그래프(Undirected Graph) : 정점의 쌍을 나타내는 간선이 방향성이 없음 (ex. (u, v), (v, u): 동일한 간선을 표현)
• 방향성 그래프(Directed Graph) : 각 간선에 방향성이 존재하는 그래프 (ex. <u, v> : u->v인 간선을 표현)

그래프의 예시 : 

• V(G1) = {0, 1, 2, 3}
• E(G1) = {(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)}
• V(G2) = {0, 1, 2, 3, 4, 5, 6}
• E(G2) = {(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6)}
• V(G3) = {0, 1, 2}
• E(G3) = {<0, 1>, <1, 0>, <1, 2>}