그래프를 방문하는 여러 방식이 있다.
Any-order Traversal
- 시작노드 s가 있다.
- s를 BOX에 넣는다.
- while BOX is not empty
- 1) BOX에서 하나의 노드를 꺼낸다.
- 2) 만약에 노드가 Mark 되어 있지 않으면
- 2-1) Mark한다
2-2) 노드에 대한 계산을 수행한다.
2-3) 해당 노드의 모든 인접 노드를 BOX에 넣는다.
1) Reachability 문제
Any-order Traversal을 통해 다음 문제를 해결할 수 있다.
문제
- 노드 s에서 시작해서 노드 t에 도달할 수 있는지?
- 노드 s에서 노드 t로 가는 길이 있는지?
해결방법
- 노드 s에서 Any-Order Traversal을 시작한다.
- Traversal 이 끝난 이후에 t가 Mark되어 있는지 확인한다.
- Mark 되어 있다면 Reachable 한 것이다.
2) Connected Component 문제
- Traversal 이 끝난 후에 Mark되지 않은 노드에서 다시 Any-order Traversal을 진행한다.
- 이를 반복하면 어떤 노드끼리 뭉쳐있는지, 즉 Connected Component의 그룹을 구분할 수 있게 된다.
Connected Component
- 덩어리 내의 노드들은 서로 모든 쌍에 대해 길이 있다.
- 노드를 더 이상 추가할 수 없다.
같은 그래프에 대해 해당 노드가 어떤 그룹에 속하는지 여러 번 물어보면,
매번 Traversal을 해야 할 것이다.
그런데 한 번 할 때 노드에 자신이 어떤 그룹인지 번호를 매겨놓으면 한 번만 Traversal을 하면 된다.
시간복잡도
- N: 노드 수, M: 엣지 수
- 모든 노드 방문 시간 N
- 인접한 노드를 Box에 넣는 시간 2M
Box에 노드를 몇 번 넣게 되나?
- 한 노드와 인접한 노드를 넣게 된다.
- 인접노드는 엣지로 연결되어 있을 것이다.
- 따라서 각 엣지 당 2개의 노드를 넣게 된다.
Game Programmer