图的深度优先遍历c语言
时间: 2023-09-28 07:03:46 浏览: 52
下面是一个使用邻接表实现图的深度优先遍历的 C 语言代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// 定义邻接表结构体
typedef struct Node {
int vertex;
struct Node* next;
} Node;
// 定义图结构体
typedef struct Graph {
int num_vertices;
Node** adj_lists;
bool* visited;
} Graph;
// 创建新节点
Node* create_node(int v) {
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->vertex = v;
new_node->next = NULL;
return new_node;
}
// 创建图
Graph* create_graph(int num_vertices) {
Graph* graph = (Graph*)malloc(sizeof(Graph));
graph->num_vertices = num_vertices;
graph->adj_lists = (Node**)malloc(num_vertices * sizeof(Node*));
graph->visited = (bool*)malloc(num_vertices * sizeof(bool));
for (int i = 0; i < num_vertices; i++) {
graph->adj_lists[i] = NULL;
graph->visited[i] = false;
}
return graph;
}
// 添加边
void add_edge(Graph* graph, int src, int dest) {
// 添加 src -> dest 的边
Node* new_node = create_node(dest);
new_node->next = graph->adj_lists[src];
graph->adj_lists[src] = new_node;
// 添加 dest -> src 的边
new_node = create_node(src);
new_node->next = graph->adj_lists[dest];
graph->adj_lists[dest] = new_node;
}
// 深度优先遍历
void dfs(Graph* graph, int vertex) {
graph->visited[vertex] = true;
printf("%d ", vertex);
Node* adj_list = graph->adj_lists[vertex];
while (adj_list != NULL) {
int adj_vertex = adj_list->vertex;
if (!graph->visited[adj_vertex]) {
dfs(graph, adj_vertex);
}
adj_list = adj_list->next;
}
}
int main() {
int num_vertices = 5;
Graph* graph = create_graph(num_vertices);
// 添加边
add_edge(graph, 0, 1);
add_edge(graph, 0, 2);
add_edge(graph, 1, 2);
add_edge(graph, 1, 3);
add_edge(graph, 2, 3);
add_edge(graph, 2, 4);
add_edge(graph, 3, 4);
// 从第一个节点开始遍历
printf("深度优先遍历结果:");
dfs(graph, 0);
return 0;
}
```
该代码中创建了邻接表来存储图,实现了创建图、添加边、深度优先遍历等操作。在深度优先遍历中,首先将当前节点标记为已访问,然后遍历该节点的所有邻居节点,如果邻居节点未被访问,则递归遍历该邻居节点,直到所有节点都被遍历完毕。