有向图的深度优先遍历c
时间: 2023-10-16 08:18:15 浏览: 53
以下是一个使用 C 语言实现的有向图的深度优先遍历算法:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
typedef struct node {
int vertex;
struct node* next;
} Node;
Node* graph[MAX_VERTICES] = { NULL };
int visited[MAX_VERTICES] = { 0 };
void add_edge(int u, int v) {
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->vertex = v;
new_node->next = graph[u];
graph[u] = new_node;
}
void depth_first_search(int vertex) {
visited[vertex] = 1;
printf("%d ", vertex);
Node* current = graph[vertex];
while (current != NULL) {
int next_vertex = current->vertex;
if (!visited[next_vertex]) {
depth_first_search(next_vertex);
}
current = current->next;
}
}
int main() {
int num_vertices, num_edges;
scanf("%d %d", &num_vertices, &num_edges);
for (int i = 0; i < num_edges; i++) {
int u, v;
scanf("%d %d", &u, &v);
add_edge(u, v);
}
int start_vertex;
scanf("%d", &start_vertex);
depth_first_search(start_vertex);
return 0;
}
```
在这个实现中,我们使用邻接表来表示有向图,并且使用一个布尔数组 `visited` 来记录每个顶点是否已经被访问过。在深度优先遍历的过程中,我们从起始顶点开始,遍历它的所有未被访问过的邻居,并递归地对每个邻居进行深度优先遍历,直到图中所有顶点都被访问过为止。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)