Graphs and Graph Traversals

Definition

1. Directed Graph

• Digraph, a pair $G = (V, E)$
• $V$ : Set of vertices (Node)
• $E$ : Set of ordered pairs of elements of $V$

 

2. Undirected Graph

• A pair $G = (V, E)$
• $V$ : Set of vertices (Node)
• $E$ : Set of unordered pairs of distinct elements of $V$

 

3. Weighted Graph

• A triple $G = (V, E, W)$
• $(V, E)$ is graph (directed or undirected)
• For an edge, $W(e)$ : weight

 

4. Graph Representations

• $G = (V, E), \ n = |V|, \ m = |E|, \ V = {v_1, \ v_2, \ \cdots , v_n}$
• Adjacency matrix representation : $n \times n$ matrix
• Array of adjacency lists representation : An array and lists

 

Traversing Graphs

1. 깊이 우선 탐색 (DFS, Depth-First Search)

• 모든 노드를 방문할 때 사용
• 노드의 방문 여부를 반드시 검사 (Backtracking)
• Stack이나 재귀함수를 통해 구현

void traversal(node)
	if node != NULL
		visit(node); // Preorder
		traversal(node->left);
		visit(node); // Inorder
		traversal(node->right);
		visit(node); // Postorder
	return;

• Preorder Traversal : 트리를 복사하거나, 전위 표기법을 구할 때 사용
• Inorder Traversal (Symmetric Traversal) : 이진 탐색에 주로 사용
• Postorder Traversal : 트리를 삭제할 때 주로 사용

DFS 예시

 

2. 너비 우선 탐색 (BFS, Breadth-First Search)

• Level-Order Traversal
• 출발 노드에서 목표 노드까지 최단 길이 경로를 보장
• 경로가 매우 길 경우 탐색 가지가 급증함에 따라 많은 기억 공간이 필요
• 선입선출의 방식을 활용하기 위해 Queue를 통해 구현

BFS 예시

 

3. Classifying Edge

• Tree Edge : DFS의 결과로 완성된 트리의 모든 간선들
• Back Edge : 트리에서 자식이 부모를 연결하는 간선들
• Forward Edge : 트리에서 부모가 자식을 연결하는 Tree Edge가 아닌 간선들
• Cross Edge : 이 외의 모든 간선들

 

4. Strongly Connected Components

• Strongly Connected : For $(v, w)$, there is a path from $v$ to $w$
• Strongly Connected Component : Maximal strongly connected subgraph of $G$

Strongly Connected Components

• Strategy
  1. Phase 1 : Depth-First Search on $G$ and put in stack
  2. Phase 2 : Depth-First Search on $G^T$, the transpose graph. To start a search, vertices are popped from the stack