图 - 邻接表深度优先遍历(C语言)
16lz
2021-04-08
#include <stdio.h>#include <stdlib.h># define MAX 100// 边节点typedef struct enode { int adIndex; // 节点下标 int weight; // 权,本代码中并未用到 struct enode *next; // 下一个节点}ENODE, *PE;// 顶点typedef struct vnode { char name; PE firstEdge; // 单链表}VNODE, *PV, VLIST[MAX];// 图(网)typedef struct graph { VLIST vlist; int numVnodes, numEdges;}GRAPH, *PG;// 保存已遍历顶点int visited[MAX];void create(PG);void traverse_dfs(GRAPH);void dfs(GRAPH, int);void dfs(GRAPH graph, int i){ PE p; // 先标识并打印顶点 printf("%c ", graph.vlist[i].name); visited[i] = 1; // 递归遍历与该顶点边有关的边节点 p = graph.vlist[i].firstEdge; while (p) { if (!visited[p->adIndex]) { dfs(graph, p->adIndex); } // 犯了个错,下面这句加到上面括号中,会导致回退的时候进入死循环 p = p->next; }}void traverse_dfs(GRAPH graph){ int i; // 初始化所有顶点为未访问状态 for (i=0; i<graph.numVnodes; i++) { visited[i] = 0; } // 开始遍历 for (i=0; i<graph.numVnodes; i++) { if (!visited[i]) { dfs(graph, i); } } }void create(PG g){ int i, j, k; PE e; printf("请输入顶点数和边数:\n"); scanf("%d %d", &g->numVnodes, &g->numEdges); getchar(); // 根据顶点数创建顶点表(VLIST一维数组) printf("请一次性输入顶点的值: "); for (i=0; i<g->numVnodes; i++) { scanf("%c", &g->vlist[i].name); g->vlist[i].firstEdge = NULL; } // 边节点单链表填充(创建边) for (k=0; k<g->numEdges; k++) { printf("请输入第%d条边(vi, vj)对应下标:\n", k+1); scanf("%d %d", &i, &j); // 创建i的边表节点j(双向) e = (PE)malloc(sizeof(ENODE)); e->adIndex = j; e->next = g->vlist[i].firstEdge; // 头插法 g->vlist[i].firstEdge = e; // 创建j的边表节点i(双向) e = (PE)malloc(sizeof(ENODE)); e->adIndex = i; e->next = g->vlist[j].firstEdge; g->vlist[j].firstEdge = e; } printf("create edge done.\n");}int main(void){ GRAPH graph; create(&graph); printf("深度优先遍历结果: "); traverse_dfs(graph); putchar('\n'); return 0;}
output
说明:
和上一篇中图一样,但是深度遍历的结果不一样(填充边时使用头插法导致遍历切入点不一样导致)
[root@8be225462e66 c]# gcc dfs_adList.c && ./a.out请输入顶点数和边数:8 9请一次性输入顶点的值: ABCDEFGH请输入第1条边(vi, vj)对应下标:0 1请输入第2条边(vi, vj)对应下标:1 2请输入第3条边(vi, vj)对应下标:2 5请输入第4条边(vi, vj)对应下标:1 4请输入第5条边(vi, vj)对应下标:0 4请输入第6条边(vi, vj)对应下标:0 3请输入第7条边(vi, vj)对应下标:3 6请输入第8条边(vi, vj)对应下标:6 4请输入第9条边(vi, vj)对应下标:6 7create edge done.深度优先遍历结果: A D G H E B C F[root@8be225462e66 c]#
©著作权归作者所有:来自51CTO博客作者sndapk的原创作品,如需转载,请注明出处,否则将追究法律责任每一份赞赏源于懂得
赞赏
0人进行了赞赏支持
更多相关文章
- 图 -邻接表广度优先遍历(C语言)
- 图 - 邻接矩阵广度优先遍历(C语言)
- vue实现tab选项卡
- C语言练习题
- 开眼界!Python 遍历文件可以这样做!
- 2021-04-02:给定一个正方形或者长方形矩阵matrix,实现zigzag打印。
- Python基础教程:5种方法实现反转字符串
- 关于HashMap的一些思考
- Web前端遍历对象应该如何操作呢?