그래프 순회
그래프 순회 ? 그래프에 있는 모든 노드를 방문하는 과정
1) breadth first search
2) depth first search
BFS
- 하나의 vertex 선택, visit check
- queue에 push
- queue가 비지 않을 때까지 인접하고, visited가 아닌 vertex를 push
만약, queue가 비었는데 visited 되지 않은 vertex가 존재한다면?
-> 이 graph는 unconnected
DFS
- 하나의 vertex 선택, visit check (BFS와 동일)
- stack이 비지 않을 때까지 인접하고, visited가 아닌 vertex를 push
인접한 vertex를 스택이나 큐에 추가하는 경우의 수가 다양할 수 있다.
= BFS, DFS가 항상 유니크한 순회 순서를 보장하지는 않는다.
connected component
그래프에서 어떤 노드들끼리 connected 되어있는지 BFS, DFS로 알 수 있다.
스택이나 큐가 비어있는데 unvisited인 노드가 있는 경우 나머지 vertex중에 하나를 시작점으로 또다른 DFS나 BFS를 수행
-> 두 개의 connected component를 분리
