广度优先遍历算法(Breadth-first-search)，是为了寻找两个节点之间的最短路径。如果把图中每一点看作是一个乒乓球，每一条边都用线连起来，那么提起图中的某一点，即可形成一棵广度优先遍历树。
在学习C的过程中，Valgrind是一个很好的工具，用来测试有没有内存泄漏，对提高自己的代码质量有很大的帮助！
具体代码如下：
graph.h
[cpp]
#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
[cpp]
#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
queue.h
[cpp]
#ifndef H_QUEUE
#define H_QUEUE
#include
typedef struct _nodes {
vertex *data;
struct _nodes *next;
} node;
typedef struct _queue {
int length;
node *front;
node *end;
} queue;
int push(queue *, vertex *);
int pop(queue *);
int push(queue *q, vertex *v)
{
node *element;
element = (node *)malloc(sizeof(node));
element->data = v;
element->next = NULL;
if (q->length == 0)
{
q->front = element;
q->end = element;
}
else
{
node *temp;
temp = q->front;
while (temp->next != NULL)
temp = temp->next;
temp->next = element;
q->end = element;
}
q->length++;
}
int pop(queue *q)
{
if (q->length == 0) return -1;
node *temp;
temp = q->front;
q->front = q->front->next;
q->length--;
if (q->length == 1)
q->end = NULL;
free(temp);
}
#endif
bfs.h
[cpp]
#ifndef H_BFS
#define H_BFS
#include "graph.h"
#include "queue.h"
#include
int bfs(graph *);
int bfs(graph *g)
{
queue q;
q.length = 0;
push(&q, g->node_list[0]);
int i;
vertex *temp;
temp = g->node_list[0];
while (q.length > 0)
{
if (temp->alength > 0)
{
for (i = 0; i < temp->alength; i++)
push(&q, temp->adjacency_nodes[i]);
temp = temp->adjacency_nodes[0];
}
pop(&q);
}
}
#endif