图的表示和遍历：表示：使用邻接链表（链表数组），每个链表表示一个顶点相邻的顶点。遍历：通过深度优先搜索（dfs）算法递归遍历各顶点及其相邻顶点。
C语言算法问答集：深入理解图算法
问题：如何在 C 语言中表示和遍历图？
代码：
立即学习“C语言免费学习笔记（深入）”；
// 使用邻接链表表示图typedef struct Node { int vertex; struct Node *next;} Node;typedef struct Graph { int num_vertices; Node **adj_list;} Graph;// 初始化图Graph* create_graph(int num_vertices) { Graph *graph = (Graph*)malloc(sizeof(Graph)); graph->num_vertices = num_vertices; graph->adj_list = (Node**)malloc(sizeof(Node*) * num_vertices); for (int i = 0; i adj_list[i] = NULL; } return graph;}// 添加边void add_edge(Graph *graph, int src, int dest) { Node *new_node = (Node*)malloc(sizeof(Node)); new_node->vertex = dest; new_node->next = graph->adj_list[src]; graph->adj_list[src] = new_node;}// 深度优先搜索void dfs(Graph *graph, int start) { int *visited = (int*)malloc(sizeof(int) * graph->num_vertices); for (int i = 0; i num_vertices; i++) { visited[i] = 0; } dfs_util(graph, start, visited);}void dfs_util(Graph *graph, int vertex, int *visited) { visited[vertex] = 1; printf("%d ", vertex); Node *current_node = graph->adj_list[vertex]; while (current_node != NULL) { if (!visited[current_node->vertex]) { dfs_util(graph, current_node->vertex, visited); } current_node = current_node->next; }}**实战案例：**考虑一个由 5 个顶点和 7 条边的无向图。以下是如何使用上述代码创建并遍历该图：
// 创建图
Graph *graph = create_graph(5);
// 添加边
add_edge(graph, 0, 1);
add_edge(graph, 0, 2);
add_edge(graph, 1, 4);
add_edge(graph, 2, 4);
add_edge(graph, 3, 4);
add_edge(graph, 3, 2);
add_edge(graph, 4, 1);
// 深度优先搜索
dfs(graph, 0);
输出结果：
0 2 4 1 3
以上就是C语言算法问答集：深入理解图算法的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1460842.html
微信扫一扫 
支付宝扫一扫 
