1.编写程序,创建无向图并实现图的深度优先搜索。C语言
时间: 2024-03-08 22:51:11 浏览: 14
以下是一个简单的C语言程序,用于创建无向图并实现深度优先搜索。
```c
#include<stdio.h>
#include<stdlib.h>
#define MAX 100
int visited[MAX];
int graph[MAX][MAX];
int n;
void DFS(int vertex) {
visited[vertex] = 1;
printf("%d ", vertex);
for(int i = 0; i < n; i++) {
if(graph[vertex][i] && !visited[i]) {
DFS(i);
}
}
}
int main() {
printf("Enter the number of vertices: ");
scanf("%d", &n);
printf("Enter the adjacency matrix:\n");
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
scanf("%d", &graph[i][j]);
}
}
printf("DFS Traversal: ");
for(int i = 0; i < n; i++) {
if(!visited[i]) {
DFS(i);
}
}
printf("\n");
return 0;
}
```
程序首先要求用户输入无向图的顶点数。然后,用户将被要求输入邻接矩阵,该矩阵将用于表示图的边缘。最后,程序将执行深度优先搜索并输出遍历顺序。
在DFS函数中,我们首先将当前顶点标记为已访问,并输出该顶点的值。接下来,我们遍历所有与该顶点相邻的顶点,并对未访问的顶点递归地调用DFS函数。
请注意,我们使用全局数组visited和graph来跟踪访问状态和图的边缘。在主函数中,我们调用DFS函数来遍历所有未访问的顶点。