Graph Traversal(그래프 순회)

이번 포스팅에서는 Graph traversal(그래프 순회)와, Connected Component 대해 알아보자.

 

Graph Traversal

그래프 순회 정의

모든 Node, Edge를 한번씩 지정된 순서로 방문하는 것이다.

순회를 거친 후에, 그래프에서 뽑아낸 자료구조가 만들어진다. (ex. 트리구조)

트리에서 문제를 푸는 것이 그래프에서 푸는 것보다 쉽다.

 

그래프 순회의 종류

- Depth First Search (깊이 우선 탐색)

- Breadth First Search (너비 우선 탐색)

 

Any-order Traversal

• Start at a Node S (put S into BOX)
• While BOX is not Empty
  • Take one Node from BOX
  • If Node not Marked
    • Mark Node
    • Do Computation on Node
    • Put Every Adjacent Node into BOX

BOX : 앞으로 방문할 노드를 넣는 자료구조라고 하자.

BOX에 시작 노드부터 넣는다.

노드에 마킹이 안되어 있으면(방문하지 않았으면), 마킹한다.

마킹이 되어 있는 노드는 다시 방문하지 않는다. (BOX에서 꺼냈어도 마킹이 되어있는 노드라면 그냥 버린다.)

 

BOX 자료구조

1. Stack

위 로직에서 BOX가 스택이 될 경우, DFS 방식으로 그래프를 탐색하게 된다.

(Node,Edge) = (V, E) 라고 한다면 최악의 경우는 모든 노드와 엣지를 방문하는 경우이므로,  시간복잡도 : O(V + E) 이다.

 

2. Queue

위 로직에서 BOX 가 큐일 경우, BFS 방식으로 그래프를 탐색하게 된다.

마찬가지로 모든 노드와 간선을 방문한다고 했을 때, 시간복잡도 : O(V + E) 이다.

 

3. Priority Queue

어느 것을 기준으로 하느냐에 따라서 여러 개로 나눠진다.

• 간선의 가중치 -> Prim 
• 시작점에서의 거리 -> Dijkstra
• 평가함수 -> A*

(프림, 다익스트라 알고리즘에 관한 정확성 증명은 해당 블로그의 다른 포스팅을 참고하길 바랍니다.)

평가함수를 활용한 것은 A* 알고리즘으로, 인공지능에서 탐색 기법에 많이 활용되는 알고리즘이다.

A* 알고리즘은 상태 공간을 탐색할 때 아주 훌륭한 기법으로 평가되고 있다.

 

위처럼 그래프 순회는 노드를 어떤 순서대로, 어떤 방식으로 탐색하는지를 나타낸다. 

어느 노드를 먼저 선택하느냐에 따라 탐색하는 순서는 달라질 수 있다. 

 

---

Connected Component

• Repeat Any-Order Traversal with unmarked Nodes

위에서 봤던 그래프 순회를 연결 요소(Connected Component)를 찾는데 활용할 수 있다.

위와 같이 DFS, BFS 혹은 다른 그래프 순회를 통해 하나의 연결 요소(Connected Component) 를 찾을 수 있다.

아직 방문하지 않은 노드에 다시 그래프 순회를 적용하면 연결 요소의 개수를 찾을 수 있다.

 

연결 요소는 다음과 같은 문제로 나올 수 있다.

• 선생님이 학생들에게 비상 연락망으로 최소 몇 명의 학생에게 연락을 돌려야 모두에게 전달될 수 있는가?