[자료구조] 그래프 순회(Graph Traversal)

그래프 순회(Graph Traversal)

하나의 정점에서 시작하여 그래프에 있는 모든 정점을 한 번씩 방문하여 처리하는 연산
 

깊이 우선 탐색(DFS: depth first search)

1. 시작 정점 v를 결정하여 방문한다.
2. 정점 v에 인접한 정점 중에서
    (a) 방문하지 않은 정점 w가 있으면,
         정점 v를 스택에 push하고 정점 w를 방문한다. 그리고 v로 하여 다시 2번을 반복한다.
    (b) 방문하지 않은 정점이 없으면,
         탐색의 방향을 바꾸기 위해서 스택을 pop하여 받은 가장 마지막 방문 정점을 v로 하여 다시 2번을 반복한다.
3. 스택이 공백이 될 떄까지 2번을 반복한다.
 
❗️시간 복잡도❗️
<인접 리스트로 구현한 경우>

• 인접 리스트의 노드들의 탐색을 끝내는 시간 O(e)
• O(|V| + |E|) = O(|V|) + O(|E|)
• e = |E|, n = |V|

 
<인접 행렬로 구현한 경우>

• V에 인접한 모든 정점들을 찾는데 O(n)의 시간
• 최대 n개의 vertex를 방문해야 하므로 O(n^2)
• 최악의 경우 |E| = n^2

(일반적으로 일접 리스트가 더 효율적이라고 한다.)

너비 우선 탐색(BFS: breadth first search)

1. 시작 정점 V를 방문한다.
2. V에 인접한 모든 정점들을 방문한다.
3. 새롭게 방문한 정점들에 인접하면서 아직 방문하지 못한 정점들을 방문한다.

인접한 정점들에 대해서 차례로 다시 너비 우선 탐색을 반복해야 하므로 선입선출의 구조를 갖는 큐를 사용한다.

virtual void Graph::BFS(int v) // 너비-우선 탐색은 정점 v에서부터 시작한다. 
{ // v 방문시 visited[i]는 TRUE로 설정
	visited = new bool[n];
	fill(visited, visited+n, false); 
	visited[v] = true;
	Queue<int> q; 
	q.push(v); 	
	while(!q.IsEmpty()) {
		v = *q.Front(); 
		q.Pop();
		for(v에 인접한 모든 정점 w에 대해) // 실제 코드는 반복자를 사용
			if(!visited[w]) {
				q.Push(w);
				visited[w] = TRUE;
			}
		} // while 루프의 끝
	delete [] visited;
}

너비 우선 탐색을 구현하면 위와 같다.
 
❗️시간 복잡도❗️
전체 시간: O(n^2) = O(|V| + |E|)
인접 리스트 표현: 전체 비용 O(e) = O(1)에서 O(n^2)까지

 

연결 요소(Connected Component)

연결 여부는 DFS 또는 BFS를 호출하여 남아있는 정점이 있는지 확인한다.

연결 요소는 방문하지 않은 정점 v에 대하여 DFS 또는 BFS를 반복 호출하여 구한다.

Virtual void Graph::Components() // 그래프의 연결요소들을 결정
{ // visited는 Graph의 bool* 데이터 멤버로 선언되었다고 가정.
	visited = new bool[n];
	fill(visited, visited+n, false); 
	for(i=0; i<n; i++) {
		if(!visited[i]) {
			DFS(i); // 연결 요소를 탐색
			OutputNewComponent();
		}
	}
	delete [] visited;
}