공대생 정리노트
Graphs(2) 본문
Graph Traversals
Depth First Search (DFS)
어떠한 vertex s를 방문하면 그 s의 neighbor vertex v를 방문하고, 그 v의 neighbor vertex v'을 방문하는 것을 반복.
모든 vertex를 방문할 때까지 반복한다.
stack을 이용하면 쉽게 구현할 수 있다.
cost : O(|V| + |E|)
Breath First Search (BFS)
DFS와 비슷하지만 stack이 아니라 queue를 이용한다.
어떠한 vertex를 방문하면 그 vertex의 neighbors들을 모두 방문 후 tree에서 깊어진다.
Cost : O(|V| + |E|)
Topological Sort
위에 나온 것처럼 전제조건이 있을 때(J2는 J1보다 먼저 나오면 안되고, J4는 J2보다 먼저 나오면 안되고... 등) Solution들은 여러가지가 있을 수 있다.
이 Solution들 중 DFS와 queue를 이용해서 구하는 Solution들을 알아보겠다.
Topological Sort with DFS
방문하지 않은 각각의 vertices에서 DFS를 수행한다. 이때 방문된 vertices를 순차적으로 print한다.
이를 모든 vertices들이 방문이 될 때까지 반복한다.
이렇게 나온 순서들을 가진 vertices들은 topological sort order의 reverse이다.
Topological Sort with Queue
모든 edge들을 방문하여 각 vertex로 들어오는 incoming edges들의 개수를 센다.
그리고 incoming edges가 없는 vertex를 담는 queue를 하나 만든다.
incoming edges가 없는 vertex는 cycle이 아닌 이상 최소 1개 존재한다.
그러므로 queue에서 vertex를 하나 꺼내 그 vertex를 print하고 그 vertex의 outgoing edges와 연결된 vertex들의 incoming edges들의 개수를 1개씩 차감한다.
그렇다면 queue에 들어오는 새로운 vertex가 생길 수 있다.
이러한 절차를 queue에 아무 vertex도 남아있지 않을 때까지 반복한다.
출처 : 서울대학교 컴퓨터공학부 강유 교수님 자료구조 수업
'CS 공부 > 자료구조' 카테고리의 다른 글
Graphs(4) - MST(Minimum Spanning Tree) (0) | 2020.05.04 |
---|---|
Graphs(3) - Dijkstra's algorithm (0) | 2020.05.02 |
Graphs(1) (0) | 2020.04.25 |
Hashing(2) (0) | 2020.04.22 |
Hashing(1) (0) | 2020.04.21 |