31. dfs [12 1주차]

31. DFS [12-1주차]

2024년 1월 14일 일요일

오후 2:46

<What Kind of Box>

Graph Traversal 과정에서 어떤 상자를 사용할 것인가?

 

Stack 사용 -> 마지막에 들어간 노드부터 분석 -> 깊이 우선 탐색(DFS)을 하게 됨

Queue 사용 -> 먼저 들어간 노드부터 분석 -> 너비 우선 탐색(BFS)을 하게 됨

• 가중치가 전부 같은 그래프의 경우, BFS를 통해 shortest path를 찾는 방법도 있다.

 

Priority queue 사용 ->

• 기준이 edge weight인 경우 -> Prim 알고리즘
• 기준이 s로부터의 거리인 경우 -> Dijkstra 알고리즘
• 기준이 어떤 함수인 경우 -> ex) A*라는 인공지능 구현에 사용된다. 바둑판의 자리에 대해 얼마나 좋은 자리인지를 계산하는 함수를 만들고, 그 함수를 기준으로 우선순위 큐에서 칸 하나를 꺼내 그 칸에 바둑을 놓는다.

 

 

<Recursive DFS>

깊이 우선 탐색을 하는 방법으로 stack을 사용할 수도 있지만, 재귀 호출로 구현할 수도 있다.

묵시적인 스택을 사용하는 것과 같다. (함수 호출 콜 스택을 사용하게 된다)

 

DFS(Graph G) {

time = 0

for G의 각 노드 u에 대해

if u의 색이 흰색이면(아직 방문되지 않았으면)

RDFS(u)

}

 

RDFS(Node u) {

Pre(u)

u의 모든 인접 노드 v에 대해

if v가 흰색이면

RDFS(v)

Post(u)

}

 

Pre(Node u) {

u.pre = ++time

}

 

Post(Node u) {

u.post = ++time

}

 

그래프의 각 노드는 DFS과정에서 Pre번호와 Post번호를 가지게 된다.

• Pre번호는 노드를 방문한 시점에서 매겨지며, 노드의 방문 시작 순서를 나타낸다.
• Post번호는 특정 노드의 인접 노드들에 대한 조사가 모두 끝난 뒤 매겨지며, 노드의 방문 종료 순서를 나타낸다.

DFS 시작 전 노드들의 색을 흰색이라 하고, Pre번호가 매겨지면 회색, Post번호가 매겨지면 검은색이라 부른다.

Pre번호와 Post번호는 앞으로 배울 그래프 알고리즘에서 중요한 역할을 한다.

 

주의 : 한 노드에 대해 흰색 인접 노드들의 목록을 미리 뽑아 놓고, 그 노드들 모두에 대해 재귀 호출해선 안 된다. 이미 검은색이 칠해진 노드를 방문하게 될 수 있기 때문이다. 재귀 호출 직전에 흰색인지 검사해야 한다.

 

 

 

<DFS Tree>

RDFS과정에서 인접 노드를 분석할 때, (재귀 호출 직전에) 노드가 흰색이라면, 해당 노드로의 엣지를 집합에 저장한다. 그 결과 DFS가 끝나면 루트가 있는 트리가 만들어진다.

RDFS과정에서 a노드가 b노드를 재귀 호출하면, a가 b의 부모 노드가 된다.

 

 

<pre, post 번호를 통한 조상, 자손 노드 판단>

노드 a, b에 대해, DFS Tree에서 다음이 성립한다.

•  a.pre < b.pre, b.post < a.post <-> a는 b의 조상 노드

 

증명

노드 a, b에 대해 a.pre < b.pre, b.post < a.post 가 성립한다면, a로부터의 재귀 호출 과정에서 b의 방문 시작과 종료가 이루어졌을 것이다.

즉, a가 b의 조상 노드가 된다.

역으로 a가 b의 조상 노드라면 a가 먼저 방문되고 b의 방문이 먼저 끝나므로 a.pre < b.pre, b.post < a.post가 성립한다.

 

 

 

<그래프 간선의 종류>

DFS Tree를 통해, 그래프의 간선을 다음 4종류로 구분할 수 있다.

1.     Tree Edge : DFS Tree를 구성하는 간선

2.     Back Edge : DFS Tree의 특정 노드에서 출발하여 그 노드의 조상 노드로 향하는 간선. self loop(어떤 노드에서 출발하여 바로 자기 자신으로 들어가는 간선)도 back edge에 포함된다.

3.     Forward Edge : 특정 노드에서 출발하여 그 노드의 자손 노드로 향하는 간선.

4.     Cross Edge : 1, 2, 3을 제외한 나머지 모든 간선. 서로 조상과 자손 관계가 아닌 노드를 연결하게 된다.

 

간선의 종류는 다음과 같이 DFS과정에서 분류할 수 있다.

 

RDFS(Node u) {

Set Pre(u)

u의 모든 인접 노드 v에 대해

if v가 흰색이면

(u, v)는 Tree Edge

RDFS(t) 로 재귀 호출

else if v가 회색이면

(u, v)는 Back Edge

else if v가 검은색이면

if u.pre < v.pre

(u, v)는 Forward Edge

else if u.pre > v.pre

(u, v)는 Cross Edge

Set Post(s)

}

 

증명

1.     흰색이면 Tree Edge : 자명하다.

2.     회색이면 Back Edge : 회색 노드들은 DFS트리에서 1차원 리스트를 형성하므로 v는 u의 조상 또는 자손이다. u에서 인접 노드들에 대한 탐색이 이루어지고 있으므로 u가 회색 노드 중 가장 깊이 있다. 따라서 v는 u의 조상 노드이다.

3.     검은색이면

검은색인 노드 v는 방문이 끝났고, u는 아직 회색이므로, v.post < u.post 가 될 것이다.

• u.pre < v.pre 이면 앞에서의 증명에 따라 u가 v의 조상 노드이다.
• u.pre > v.pre 이면 앞에서의 증명에 따라 v가 u는 조상과 자손 관계에 있지 않다.

 

무방향 그래프에서는 위의 정의로 Back Edge와 Forward Edge를 구분하기 애매하다.

따라서, 무방향 그래프에서는 RDFS에서 처음 부여된 간선 종류를 진짜 간선 종류로 정의한다.

 

 

<무방향 그래프는 Tree, Back Edges만 존재>

위의 정의에 따르면, 무방향 그래프에서 Forward Edge와 Cross Edge는 존재하지 않게 된다. 즉, 무방향 그래프에서 DFS트리에 포함되지 않는 간선들은 Back Edge 뿐이다

 

증명

DFS 트리에서 노드 a, b에 대해, a와 b를 연결하는 간선이 존재한다고 가정한다. 또한 a에 대해 RDFS가 먼저 호출된다고 하자.

 

a.pre < b.pre 가 성립한다.

또한 간선 (a, b)의 존재로 인해, RDFS(a)의 재귀 호출로부터 RDFS(b)가 무조건 호출된다. 따라서 b.post < a.post가 성립하고, a는 b의 조상 노드임을 알 수 있다.

 

RDFS(a) 호출 중 a의 인접 노드들에 대해 재귀 호출을 시도할 때,

• b가 흰색이라면 RDFS(b)가 호출되기 직전, DFS트리에 간선 (a, b)가 추가되어, (a, b)는 Tree Edge가 된다.
• b가 회색이면 b가 a의 조상이라는 모순이 발생한다. 따라서 b는 회색일 수 없다.

• b가 검은색이라면

b의 인접 노드들에 대한 분류가 이미 끝났다는 뜻이다. 따라서 간선 (a, b)의 분류도 b에 의해 이미 끝났을 것이다. a는 b의 조상이므로, (b, a)는 Back Edge로 분류된다.