Graphs(2)

Graph Traversals

Depth First Search (DFS)

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에서 깊어진다.

 

BFS

 

Cost : O(|V| + |E|)

 

 

 

Topological Sort

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도 남아있지 않을 때까지 반복한다.

 

 

 

 

 

 

 

출처 : 서울대학교 컴퓨터공학부 강유 교수님 자료구조 수업