图的深度优先搜索遍历用C语言怎么编写
时间: 2023-08-17 10:04:20 浏览: 50
要在C语言中实现深度优先搜索遍历,需要先定义一个图的数据结构。一种常见的表示方法是邻接表(adjacency list),即使用一个数组来存储每个顶点的邻接表(即与该顶点相邻的顶点列表)。具体实现步骤如下:
1. 定义一个图的结构体,包括顶点数和边数信息,以及存储邻接表的数组。
```
typedef struct Graph {
int V; // 顶点数
int E; // 边数
int **adj; // 邻接表数组
} Graph;
```
2. 定义一个创建图的函数,根据输入的顶点数和边数,以及每条边的起点和终点,构建邻接表。
```
Graph *createGraph(int V, int E) {
Graph *G = (Graph *)malloc(sizeof(Graph));
G->V = V;
G->E = E;
G->adj = (int **)malloc(V * sizeof(int *));
for (int i = 0; i < V; i++) {
G->adj[i] = (int *)malloc(V * sizeof(int));
for (int j = 0; j < V; j++) {
G->adj[i][j] = 0;
}
}
for (int i = 0; i < E; i++) {
int u, v;
scanf("%d %d", &u, &v);
G->adj[u][v] = 1; // 添加边
G->adj[v][u] = 1;
}
return G;
}
```
3. 定义一个深度优先搜索函数,用于遍历图中的所有顶点。首先标记当前顶点为已访问,然后依次访问该顶点的邻接顶点,如果邻接顶点未被访问过,则递归调用深度优先搜索函数。
```
void DFS(Graph *G, int v, int *visited) {
visited[v] = 1; // 标记当前顶点为已访问
printf("%d ", v); // 输出当前顶点
for (int i = 0; i < G->V; i++) {
if (G->adj[v][i] && !visited[i]) { // 如果i是v的邻接点且未被访问过
DFS(G, i, visited); // 递归访问i
}
}
}
```
4. 在主函数中调用创建图和深度优先搜索函数,完成图的遍历。
```
int main() {
int V, E;
scanf("%d %d", &V, &E);
Graph *G = createGraph(V, E);
int *visited = (int *)malloc(V * sizeof(int));
for (int i = 0; i < V; i++) {
visited[i] = 0;
}
for (int i = 0; i < V; i++) {
if (!visited[i]) { // 如果顶点i未被访问过
DFS(G, i, visited); // 从i开始进行深度优先搜索
}
}
return 0;
}
```
以上是一个简单的图的深度优先搜索遍历程序,仅供参考。在实际应用中,需要根据具体需求进行修改和优化。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)