使用 C 语言实现深度优先搜索 (DFS)
cserver side programmingprogramming
深度优先搜索 (DFS) 是一种遍历图并访问所有节点后返回的算法。此外，它还确定两个节点之间是否存在路径。
它以深度方式搜索图或树。
算法
下面给出了深度优先搜索 (DFS) 的实现算法 −
步骤 1 − 初始堆栈为空。
步骤 2 − 如果要访问的节点不在堆栈中，则将其压入堆栈并将其标记为已访问。
步骤 3 − 然后，检查当前节点是否符合我们的搜索条件。
步骤 3.1 − 如果存在，则完成。
步骤 4 − 否则，我们需要从当前节点访问所有相邻节点。
步骤 4.1 − 然后以任意随机顺序访问所有此类节点，并继续搜索。
步骤 5 − 如果所有相邻节点都已被访问，则进入死胡同。
步骤 6 − 我们转到先前访问过的节点，并从堆栈中弹出最近的节点。
步骤 7 −如果所有节点都已搜索完毕，或者我们得到了答案，算法将终止。
程序
以下是用于实现深度优先搜索 (DFS)的 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;
};
//堆栈变量
int stack[MAX];
int top = -1;
//图变量
//顶点数组
struct Vertex* lstVertices[MAX];
//邻接矩阵
int adjMatrix[MAX][MAX];
//顶点数量
int vertexCount = 0;
//堆栈函数
void push(int item) {
stack[++top] = item;
}
int pop() {
return stack[top--];
}
int peek() {
return stack[top];
}
bool isStackEmpty() {
return top == -1;
}
//图函数
//将顶点添加到顶点列表
void addVertex(char label) {
struct Vertex* vertex = (struct Vertex*) malloc(sizeof(struct Vertex));
vertex->label = label;
vertex->visited = false;
lstVertices[vertexCount++] = vertex;
}
//将边添加到边数组
void addEdge(int start,int end) {
adjMatrix[start][end] = 1;
adjMatrix[end][start] = 1;
}
//显示顶点
void displayVertex(int vertexIndex) {
printf("%c",lstVertices[vertexIndex]->label);
}
//获取相邻的未访问顶点
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;
//将第一个节点标记为已访问
lstVertices[0]->visited = true;
//显示顶点
displayVertex(0);
//将顶点索引压入堆栈
push(0);
while(!isStackEmpty()) {
//获取位于堆栈顶部的顶点的未访问顶点
int unvisitedVertex = getAdjUnvisitedVertex(peek());
//未找到相邻顶点
if(unvisitedVertex == -1) {
pop();
} else {
lstVertices[unvisitedVertex]->visited = true;
displayVertex(unvisitedVertex);
push(unvisitedVertex);
}
}
//堆栈为空，搜索完成，重置已访问标志
for(i = 0;i < vertexCount;i++) {
lstVertices[i]->visited = false;
}
}
int main() {
int i, j;
for(i = 0; i < MAX; i++) // 设置邻接关系 {
for(j = 0; j < MAX; j++) // 将矩阵置零
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
