C语言深度优先搜索代码
时间: 2023-07-25 07:04:05 浏览: 53
下面是一个使用C语言实现深度优先搜索算法的示例代码:
```c
#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTICES 100
bool visited[MAX_VERTICES]; // 记录节点是否被访问
int adjacencyMatrix[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵
void depthFirstSearch(int vertex, int numVertices) {
visited[vertex] = true;
printf("%d ", vertex);
for (int i = 0; i < numVertices; i++) {
if (adjacencyMatrix[vertex][i] && !visited[i]) {
depthFirstSearch(i, numVertices);
}
}
}
int main() {
int numVertices, numEdges;
printf("输入节点数和边数:");
scanf("%d %d", &numVertices, &numEdges);
// 初始化visited数组
for (int i = 0; i < MAX_VERTICES; i++) {
visited[i] = false;
}
// 初始化邻接矩阵
for (int i = 0; i < MAX_VERTICES; i++) {
for (int j = 0; j < MAX_VERTICES; j++) {
adjacencyMatrix[i][j] = 0;
}
}
printf("输入边的连接关系:\n");
for (int i = 0; i < numEdges; i++) {
int start, end;
scanf("%d %d", &start, &end);
adjacencyMatrix[start][end] = 1;
adjacencyMatrix[end][start] = 1; // 如果是有向图,去掉这一行
}
int startVertex;
printf("输入起始节点:");
scanf("%d", &startVertex);
printf("深度优先搜索结果:");
depthFirstSearch(startVertex, numVertices);
return 0;
}
```
以上代码实现了一个简单的深度优先搜索算法。用户需要输入节点数和边数,然后逐个输入边的连接关系。程序使用邻接矩阵来表示图的连接关系,其中1表示有连接,0表示没有连接。用户还需要输入起始节点,然后程序会输出从起始节点开始的深度优先搜索结果。
请注意,这只是一个基本的示例代码,可能需要根据具体问题的需求进行适当的修改。例如,可以根据实际情况添加节点的其他属性,或者根据需求进行路径记录等操作。