데이터 구조-깊이 우선 순회

DFS (Depth First Search) 알고리즘은 깊이 이동으로 그래프를 탐색하고 스택을 사용하여 반복에서 막 다른 골목이 발생할 때 검색을 시작하기 위해 다음 정점을 가져 오는 것을 기억합니다.

위에 주어진 예에서와 같이 DFS 알고리즘은 먼저 S에서 A, D, G, E, B를 순회 한 다음 F, ​​마지막으로 C를 순회합니다. 다음 규칙을 사용합니다.

• Rule 1− 방문하지 않은 인접한 정점을 방문합니다. 방문한 것으로 표시하십시오. 그것을 표시하십시오. 스택에 밀어 넣으십시오.

• Rule 2− 인접한 정점이 없으면 스택에서 정점을 팝업합니다. (인접한 정점이없는 스택의 모든 정점이 팝업됩니다.)

• Rule 3 − 스택이 비워 질 때까지 규칙 1과 규칙 2를 반복합니다.

단계	순회	기술
1		스택을 초기화합니다.
2		표 S방문하여 스택에 넣습니다. 방문하지 않은 인접 노드를 탐색하십시오.S. 3 개의 노드가 있으며 그중 하나를 선택할 수 있습니다. 이 예에서는 알파벳 순서로 노드를 가져옵니다.
삼		표 A방문하여 스택에 넣습니다. A에서 방문하지 않은 인접 노드를 탐색하십시오. 둘 다S 과 D 인접하다 A 그러나 우리는 방문하지 않은 노드에만 관심이 있습니다.
4		방문 D방문한 것으로 표시하고 스택에 넣습니다. 여기, 우리는B 과 C 인접한 노드 D둘 다 방문하지 않았습니다. 그러나 다시 알파벳순으로 선택하겠습니다.
5		우리는 선택합니다 B, 방문한 것으로 표시하고 스택에 넣습니다. 여기B방문하지 않은 인접 노드가 없습니다. 그래서 우리는 팝B 스택에서.
6		이전 노드로 돌아 가기 위해 스택 상단을 확인하고 방문하지 않은 노드가 있는지 확인합니다. 여기에서 우리는D 스택의 맨 위에 있습니다.
7		방문하지 않은 인접 노드 만 D 이다 C지금. 그래서 우리는 방문합니다C, 방문한 것으로 표시하고 스택에 넣습니다.

같이 C방문하지 않은 인접 노드가 없으므로 방문하지 않은 인접 노드가있는 노드를 찾을 때까지 스택을 계속 표시합니다. 이 경우에는 아무것도없고 스택이 비워 질 때까지 계속 터집니다.

이 알고리즘의 C 프로그래밍 언어 구현에 대해 알아 보려면 여기를 클릭하십시오 .