Graphs and Graph Traversals

Directed graph (digraph)

- G = (V, E)

- V: vertex들의 집합

- E: V 원소들의 순서쌍 집합

- directed edge (v, w)는 v->w 또는 vw로 나타냄.

 

Undirected graph

- G = (V, E)

- V: vertex들의 집합

- E: V 원소들의 순서가 없는 쌍 집합

- undirected edge {v, w}는 v-w 또는 vw, wv로 나타냄.

- incident: 간선-정점 간의 연결 관계 / adjacent: 정점-정점 간의 인접 관계

 

Weighted Graph

- edge에 값이 있는 경우.

- (V, E, W)또는 (V, E)로 나타냄

 

Graph Representations

- G = (V, E), n = |V|, m = |E|, V = {v1, v2, ..., vn} 이라고 할 때

- Adjacency matrix representation: 인접행렬 표현

- (Array of) adjacency lists representation: 인접리스트 표현

- 수행 시간 비교

- v.incidentEdge() : vertex v의 incident edges 구하기

- matrix: O(n) : 해당 행 또는 열을 훑음 -> vertex 수와 같다.

- list :      O(deg(v)) : 해당 vertex의 edge 수만큼

- v.isAdjacentTo(w) : v와 w가 인접한지 판별

- matrix: O(1) : 해당 인덱스에 접근해 바로 확인 가능

- list:       O(min(deg(v), deg(w)) : v, w 중 리스트 수가 적은 곳을 훑어 확인

 

용어 정리

- Subgraph: 그래프 G=(V, E), G’=(V’, E’)이 있을 때, V’⊆V 이고 E’⊆E 라면 G’는 G의 subgraph

- Complete graph: 그래프의 모든 vertex 쌍이 edge를 갖는 그래프(모든 vertex가 adjacent)

- Adjacency relation: 인접 관계. 두 vertex가 edge로 (바로)연결되어 있는 관계.

- Path: vertex v에서 y로 가는 경로가 v-w-z-y일 때, <vw, wz, zy>로 표현됨. 이때 path의 길이=edge 수=3

- Simple path: 포함된 모든 vertex가 다 다른 path.

- reachable: v에서 w로 가는 path가 존재한다면 w는 v로부터 reachable (w is reachable from v via path p).

- Connected: 임의의 vertex 쌍이 reachable일 때 해당 (undirected)그래프는 connected.
                    어느 한 정점에서 다른 정점으로 갈 수 있음 (모든 정점에 해당).

- Strongly Connected: digraph가 connected일 때.

- Cycle: 시작 정점=끝 정점인 nonempty path. self-loop일 때도 cycle.
           (undirected에선 self loop가 없기 때문에 길이가 3 이상이어야 cycle을 정의할 수 있음.)

- Simple cycle: 시작-끝 정점을 제외한 모든 정점이 한번씩만 등장하는 cycle

- Acyclic: (그래프) 사이클이 없는 경우.

- Undirected forest: acyclic이면서 undirected인 그래프

- Free tree (Undirected tree): connected, acyclic, undirected인 그래프

- Rooted tree: root가 존재하는 free tree

- Connected component: G의 connected subgraph 중 최대로 연결된 subgraph.

 

특성 정리

- deg(v) = incoming edge 수 + outgoing edge 수

- 그래프 G=(V, E), n=|V|, m=|E|에 대해 Σdeg(v)=2m  (undirected, directed graph 둘 다 만족하는 특성)

- Digraph G에 대해 Σin_deg(v)=m, Σout_deg(v)=m. m<=n(n-1)

- Undirected graph G의 edge 수 m<=n(n-1)/2

1. G가 connected라면, m>=n-1

2. G가 tree라면, m=n-1

3. G가 forest라면, m<=n-1

- Dense graph: m이 O(n2)에 가까울 때

- Sparse graph: m이 O(n)에 가까울 때

 

Traversing Graphs

- BFS, DFS

- vertex의 상태: undiscovered(white) / discovered(gray) / finished (black)

- edge의 상태: unexplored / explored

 

Depth-first Search Tree

- edges are classified

- tree edge: 트리에 포함되는 edge

- back edge: 트리에서 ancestor 관계

- descendant edge: descendant 관계

- cross edge: 조상이나 후손 관계 아닐 때

 

BFS

- 처음 시작하는 A는 d=0임. 큐를 이용한다.

 

Strongly Connected Components (SCC)

- Strongly connected: 방향그래프에서 어떤 두 정점 사이에 갈 수 있는 경로가 존재한다.

- Strongly connected component: digraph G의 maximal strongly connected subgraph.

 

{A, B, D, F}, {C}, {G, E}는 maximal strongly connected component이다.

 

SCC 구하는 알고리즘 (kosaraju’s algorithm)

- Array of adjacency list로 구현했다면 시간, 공간 복잡도는 O(n+m), total O(n+m)

- Phase 1:

  - G를 DFS 돌면서 finished vertex를 스택에 넣음

- Phase 2:

  - 스택에서 하나씩 꺼내면서 GT를 DFS 돎 (GT 쓰는 이유: 방향을 바꿔도 서로 갈 수 있는 경로가 있어야 함)

- Starting vertex (leader)가 같은 vertex들이 strongly connected component가 된다.