深度优先遍历与广度优先遍历算法的C语言达成
发布时间：2021-11-20 18:22:11 所属栏目：教程 来源：互联网
导读：深度优先遍历算法(Depth-first-search)，重点关注的是图的连通性(connectivity)，即从图中给定的一点都能访问到哪些点。不仅如此，在遍历这些点的过程中，通过记录访问次序，可以实现其他功能，比如测试该图是否有闭环等。 广度优先遍历算法(Breadth-first-s
|
深度优先遍历算法(Depth-first-search)，重点关注的是图的连通性(connectivity)，即从图中给定的一点都能访问到哪些点。不仅如此，在遍历这些点的过程中，通过记录访问次序，可以实现其他功能，比如测试该图是否有闭环等。 广度优先遍历算法(Breadth-first-search)，是为了寻找两个节点之间的最短路径。如果把图中每一点看作是一个乒乓球，每一条边都用线连起来，那么提起图中的某一点，即可形成一棵广度优先遍历树。 在学习C的过程中，Valgrind是一个很好的工具，用来测试有没有内存泄漏，对提高自己的代码质量有很大的帮助！ 具体代码如下： graph.h #ifndef H_GRAPH #define H_GRAPH typedef struct _node { char *data; char flag; struct _node **adjacency_nodes; int alength; } vertex; typedef struct _graph { vertex **node_list; int length; } graph; #endif dfs.h #ifndef H_DFS #define H_DFS #include "graph.h" char **pre, **post; int explore(vertex *); int previsit(vertex *); int postvisit(vertex *); int dfs(graph *); int explore(vertex *node) { if (node->flag == 1) return; previsit(node); int i = 0; while (i++ < node->alength) { explore(*node->adjacency_nodes++); } postvisit(node); } int previsit(vertex *node) { *pre = (char *)malloc(sizeof(char)); *pre++ = node->data; } int postvisit(vertex *node) { *post = (char *)malloc(sizeof(char)); *post++ = node->data; node->flag = 1; } int dfs(graph *list) { int i = 0; while (i++ < list->length && (*list->node_list)->flag == 0 ) explore(*list->node_list++); } #endif  （编辑：南通站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
