深度优先遍历与广度优先遍历算法的C语言实现

深度优先遍历算法（Depth-first-search），重点关注的是图的连通性（connectivity），即从图中给定的一点都能访问到哪些点。不仅如此，在遍历这些点的过程中，通过记录访问次序，可以实现其他功能，比如测试该图是否有闭环等。广度优先遍历算法（Breadth-first-search），是为了寻找两个节点之间的最短路径。如果把图中每一点看作是一个乒乓球，每一条边都用线连起来，那么提起图中的某一点，即可形成一棵广度优先遍历树。在学习C的过程中，Valgrind是一个很好的工具，用来测试有没有内存泄漏，对提高自己的代码质量有很大的帮助！具体代码如下：graph.h#ifndef H_GRAPH
#define H_GRAPHtypedef struct _node {
char *data;
char flag;
struct _node **adjacency_nodes;
int alength;
} vertex;typedef struct _graph {
vertex **node_list;
int length;
} graph;#endifdfs.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