데이터 구조의 쌍곡선에 대한 깊이 우선 검색

그래프에 대한 깊이 우선 검색은 유사합니다. 그러나 Digraphs 또는 방향 그래프의 경우 몇 가지 유형의 간선을 찾을 수 있습니다. DFS 알고리즘은 DFS 트리라는 트리를 형성합니다. −

• 트리 에지(T) - DFS 트리에 존재하는 가장자리

• 포워드 에지(F) − 트리 에지 세트와 평행합니다. (작은 DFS 번호에서 큰 DFS 번호로, 큰 DFS 완료 번호에서 작은 DFS 완료 번호로)

• 백워드 에지(B) − 큰 DFS 번호에서 작은 DFS 번호로, 작은 DFS 완료 번호에서 큰 DFS 완료 번호로.

• 크로스 에지(C) - 큰 DFS 번호에서 작은 DFS 번호로, 큰 DFS 완료 번호에서 작은 DFS 완료 번호로

아래와 같은 그래프가 있다고 가정해 보겠습니다. -

이제 A를 초기 정점으로 취하여 DFS를 수행하고 DFS 번호와 DFS 완료 번호를 넣습니다. 따라서 트리는 아래와 같이 보일 것입니다 -

따라서 DFS 순회는 A, B, F, D, G, C, E

트리 에지는 − T ={(A, B), (B, F), (F, D), (F, G), (A, C), (C, E)}

전방 에지는 − F ={(A, G)}

뒤로 에지는 − B ={(G, B)}

교차 모서리는 -C ={(G, D)}