深度優先遍歷與廣度優先遍歷算法的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