6. Graphs

그래프(graph)란?

연결되어 있는 객체 간의 관계를 표현하는 자료구조.

그래프로 표현함으로써 문제를 쉽게 모델링하여 해결할 수 있다.

 

---

그래프 데이터 타입

그래프 G의 두 가지 구성 요소

• V(G): G에 포함된 vertex(정점)들의 집합
• E(G): G에 포함된 edge(간선)들의 집합
• G=(V,E)라고 쓰기도 함.

무방향성 그래프와 방향성 그래프.

• 무방향성 그래프(undirected graph): edge의 방향성이 없음. (u,v), (v,u)는 동일한 edge를 표현한다.
• 방향성 그래프(directed graph=Digraph): edge에 방향성이 존재함. <u,v>는 u에서 v로 간다는 뜻.

 

그래프에서 사용되는 용어들.

• 완전 그래프(complete graph): Edge의 수가 최대인 그래프. n개의 vertex가 있을 때 최대 edge 수=n(n-1)/2
• 인접(adjacent): edge로 연결되어있는 경우. //방향성 그래프에서 <u,v>일 때 u는 v에 인접하고, v는 u로부터 인접함.
• 부분 그래프(Subgraph)
• 경로(path) : vertex u부터 v까지 가는 동안 거치는 vertex들의 나열 u,v1,v2,...,v
• 경로의 길이 : 경로 상에 있는 edge 수. (간선 수라는거 주의하기)
• 단순 경로(simple path) : 경로에서 같은 정점을 중복하여 거치지 않는 경로. //방향성 그래프: Simple directed path
• 연결(connected): vertex u와 v사이에 경로가 존재하는 경우 u,v는 연결되어있음.//방향성 그래프: strongly connected
• 연결 요소(connected component): 고립된 subgraph들. //방향성 그래프: strongly connected component
• 트리=connected acyclic graph임. (모두 연결되어있고 사이클이 없는 그래프)
• Vertex v의 차수(degree): v에 부속된 edge의 수//방향성 그래프에서는 in-degree/out-degree로 나뉘어짐.

---

그래프 표현법

• 인접 행렬(Adjacency Matrix)
• 인접 리스트(Adjacency List)
• 인접 다중 리스트(Adjacency Multilist)

 

---

인접 행렬(Adjacency Matrix)

 

n개의 vertex를 갖는 그래프 G가 있을 때, A[n][n] 배열로 표현함.

G(u,v)일 때, A[u][v]=1로 표현하고, vertex끼리의 edge가 존재하지 않는 경우는 0으로 표현한다.

 

무방향성 그래프일 때 A[][]는 대칭행렬이다. ==> A[n(n-1)/2]로 구현이 가능할 듯.

방향성 그래프일 때 A[][]는 비대칭 행렬이다. 

 

 

---

인접 리스트(Adjacency Multilist)

 

인접 행렬의 n행들을 n개의 연결 리스트로 표현.

(즉, 그래프의 vertex마다 하나의 연결 리스트가 존재함)

 

---

인접 다중 리스트(Adjacency Multilist)

 

Edge마다 하나의 노드를 할당한다.=> 각 edge를 검사했다는 표시를 나타내는데 용이하다.

(각 노드는 marked, vertex1, vertex2, path1, path2가 존재함.)

---

 

그래프 표현 방식들의 분석

 

G에 존재하는 edge수 혹은 G가 연결되었는지 검사할 때

인접 행렬: 배열의 한 칸 한 칸을 모두 조사해야 하므로 O(n^2)

인접 리스트: O(n+e) ==> n개의 정점, 간선 수 e.  완전그래프의 경우 e는 n(n-1)/2가 되어 e가 커지고 희소행렬이면 e가 작아짐

 

Digraph에서 vertex의 in-degree를 조사하는 방법

인접 행렬: O(n) ==> 세로줄 하나를 검사하면 끝남

인접 리스트: O(n+e) ==> out-degree만 표시되어있기 때문에 다 찾아봐야함