연습문제
그래프 G의 정점은 1에서 8까지의 정수고 각 정점의 인접정점들은 아래 테이블에 나열된대로다. G를 순회할 때 주어진 정점의 인접정점들이 테이블에 나열된 순서와 동일한 순서로 반환된다고 가정하고 다음에 답해라
| 정점 | 인접정점들 |
|---|---|
| 1 | 2,3,4 |
| 2 | 1,3,4 |
| 3 | 1,2,4 |
| 4 | 1,2,3,6 |
| 5 | 6,7,8 |
| 6 | 4,5,7 |
| 7 | 5,6,8 |
| 8 | 5,7 |
| #### 그래프 G를 그려라 |
정점 1에서 출발하는 DFS순회에서 정점들이 방문되는 순서를 구하라
1 - 2 - 3 - 4 - 6 - 5 - 7 - 8
정점 1에서 출발하는 BFS 순회에서 정점들이 방문되는 순서를 구하라
1 - 2 - 3 - 4 - 6 - 5 - 7 - 8
인접행렬 구조로 표현된 n-정점 단순그래프에서 DFS 순회가 $O(n^2)$시간에 수행하는 이유를 설명하여라
모든 정점을 두 번씩 방문하기 때문이다.
정점과 간선의 라벨을 쓰고 읽는데 $O(1)$ 시간이 소요한다. 이는 정점이나 간선을 구현하는 노드가 Fresj, Visited, Tree, Back 등의 값을 저장하는 라벨을 가지도록 각 노드의 데이터구조를 확장하면 가능하다. 각 정점은 두 번 라벨된다. 한 번은 Fresh로, 또 한번은 Visited로 라벨된다. 각 간선 역시 두 번 라벨된다. 한 번은 Fresh로, 또 한 번은 Tree 또는 Back으로 라벨된다. 알고리즘 rDFS에서 수행하는 메쏘드 incidentEdges는 각 정점에 대해 한 번 호출된다. 그래프가 인접행렬로 표현된 경우 한 번 호출에 $O(n)$ 시간을 소요하며 $\sum_v{n} = n^2$이므로 명령문 2행은 총 $O(n^2)$ 시간에 수행한다. 그러므로 그래프가 인접행렬로 표현된 경우 DFS는 $O(n^2)$ 시간에 수행한다.
꺽정은 방향그래프 G에 대한 DFS 순회를 수행한 결과로 얻은 DFS 숲에서 동일한 DFS트리 내의 두 정점 a와 b에 대한 방문 시각이 t(a)<t(b) , 즉 a를 b보다 먼저 방문한 것으로 나타났다면 해당 DFS 트리에서 a는 b의 조상임을 의미한다고 주장한다. 꺽정의 주장이 옳은지 그른지 논거와 함께 설명하라.
DFS는 계속 가다가 갈 곳이 없으면 이전의 지나친 길 중에서 안간 길로 다시 가기 시작한다. 그러므로 항상 a가 b의 조상은 아니다. 형제일 경우도 있고, 이모와 같이 v가 더 위일 수 있다.
다르다. 이유는 세개의 정점 s,a,b와 두 개의 간선 (s,a),(s,b)만이 존재하는 그래프에서 s를 출발정점으로 하는 DFS순회로 얻은 DFS트리에서 a와 v는 형제(siblings)가 된다. 그러므로 어느 정점도 다른 정점의 조상이 아니다.
DFS 순회 알고리즘의 비재귀적 버전을 작성하라
정점에 다른 길이 있었다면 리스트의 마지막에 넣어두고, 갈 길이 없다면 마지막에서 하나씩 빼서 쓴다.
Alg DFS1(G,v)
1. S = empty stack
2. S.push(v)
3. while(!S.isEmpty()){
v = S.pop()
l(v) = Visted
for each e ∈ G.incidentEdges(v){
if(l(e)== Fresh){
w = G.opposite(v,e)
if(l(w)==Fresh){
l(e) = Tree
S.push(w)
}
else
l(e) = back
}
}
}
4. return