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

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

深度优先遍历算法(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