DFS(Depth First Search)는 그래프를 탐색하고 돌아올 수 있는 모든 노드를 방문하기 전에 방문하는 알고리즘입니다. 또한 두 노드 사이에 경로가 존재하는지 여부를 판별합니다.
그래프나 트리를 심층적으로 검색합니다.
알고리즘
다음은 깊이 우선 탐색(DFS) 구현을 위한 알고리즘입니다. -
1단계 − 초기 스택은 비어 있습니다.
2단계 − 방문할 노드가 스택에 없으면 스택에 푸시하고 방문한 것으로 표시합니다.
3단계 − 그런 다음 현재 노드가 검색 기준과 일치하는지 확인합니다.
3.1단계 − 있으면 완료됩니다.
4단계 − 그렇지 않으면 현재 노드에서 인접한 모든 노드로 이동해야 합니다.
4.1단계 − 그런 다음 임의의 순서로 해당 유형의 모든 노드를 방문하고 계속 검색합니다.
5단계 − 모든 인접 노드가 이미 방문한 경우 막 다른 골목이 됩니다.
6단계 − 이전에 방문한 노드로 이동하여 스택에서 최근 노드를 팝합니다.
7단계 − 모든 노드가 검색되거나 답이 나오면 알고리즘이 종료됩니다.
프로그램
다음은 DFS(Depth First Search) 구현을 위한 C 프로그램입니다. -
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 5
void addVertex(char);
void addEdge(int,int );
void displayVertex(int);
void depthFirstSearch();
int getAdjUnvisitedVertex(int);
struct Vertex {
char label;
bool visited;
};
//stack variables
int stack[MAX];
int top = -1;
//graph variables
//array of vertices
struct Vertex* lstVertices[MAX];
//adjacency matrix
int adjMatrix[MAX][MAX];
//vertex count
int vertexCount = 0;
//stack functions
void push(int item) {
stack[++top] = item;
}
int pop() {
return stack[top--];
}
int peek() {
return stack[top];
}
bool isStackEmpty() {
return top == -1;
}
//graph functions
//add vertex to the vertex list
void addVertex(char label) {
struct Vertex* vertex = (struct Vertex*) malloc(sizeof(struct Vertex));
vertex->label = label;
vertex->visited = false;
lstVertices[vertexCount++] = vertex;
}
//add edge to edge array
void addEdge(int start,int end) {
adjMatrix[start][end] = 1;
adjMatrix[end][start] = 1;
}
//display the vertex
void displayVertex(int vertexIndex) {
printf("%c ",lstVertices[vertexIndex]->label);
}
//get the adjacent unvisited vertex
int getAdjUnvisitedVertex(int vertexIndex) {
int i;
for(i = 0; i < vertexCount; i++) {
if(adjMatrix[vertexIndex][i] == 1 && lstVertices[i]->visited == false) {
return i;
}
}
return -1;
}
void depthFirstSearch() {
int i;
//mark first node as visited
lstVertices[0]->visited = true;
//display the vertex
displayVertex(0);
//push vertex index in stack
push(0);
while(!isStackEmpty()) {
//get the unvisited vertex of vertex which is at top of the stack
int unvisitedVertex = getAdjUnvisitedVertex(peek());
//no adjacent vertex found
if(unvisitedVertex == -1) {
pop();
} else {
lstVertices[unvisitedVertex]->visited = true;
displayVertex(unvisitedVertex);
push(unvisitedVertex);
}
}
//stack is empty, search is complete, reset the visited flag
for(i = 0;i < vertexCount;i++) {
lstVertices[i]->visited = false;
}
}
int main() {
int i, j;
for(i = 0; i < MAX; i++) // set adjacency {
for(j = 0; j < MAX; j++) // matrix to 0
adjMatrix[i][j] = 0;
addVertex('S'); // 0
addVertex('A'); // 1
addVertex('B'); // 2
addVertex('C'); // 3
addVertex('D'); // 4
addEdge(0, 1); // S - A
addEdge(0, 2); // S - B
addEdge(0, 3); // S - C
addEdge(1, 4); // A - D
addEdge(2, 4); // B - D
addEdge(3, 4); // C - D
printf("Depth First Search: ");
depthFirstSearch();
return 0;
} 출력
위의 프로그램이 실행되면 다음과 같은 결과가 생성됩니다 -
Depth First Search: S A D B C