数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究使用C语言实现深度优先搜索(DFS)
深度优先搜索(DFS) 是一种遍历图并访问所有节点然后再返回的算法，它可以确定是否存在两节点之间的路径。
算法
以下是深度优先搜索(DFS)的实现算法：
步骤1 − 初始栈为空。
步骤2 − 如果要访问的节点不在栈中，则将其压入栈中并标记为已访问。
步骤3 − 然后，检查当前节点是否与我们的搜索条件匹配。
步骤3.1 − 如果匹配，则完成。
步骤4 − 否则，我们需要访问当前节点的所有相邻节点。
步骤4.1 − 然后以任意顺序访问所有这些类型的节点，并继续搜索。
步骤5 − 如果所有相邻节点都已访问，则成为死胡同。
步骤6 − 我们返回到先前访问的节点，并将最近的节点从栈中弹出。
步骤7 − 如果所有节点都已搜索完毕，或者我们得到答案，则算法终止。
深度优先搜索(DFS)的C语言程序实现
以下是深度优先搜索(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;
};
//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
更新于：2024年6月25日
6K+ 次浏览
广告