C语言数据结构与算法之深度、广度优先搜索
一、深度优先搜索（depth-first-search 简称：dfs）
1.1 遍历过程：
（1）从图中某个顶点v出发，访问v。
（2）找出刚才第一个被顶点访问的邻接点。访问该顶点。以这个顶点为新的顶点，重复此步骤，直到访问过的顶点没有未被访问过的顶点为止。
（3）返回到步骤（2）中的被顶点v访问的，且还没被访问的邻接点，找出该点的下一个未被访问的邻接点，访问该顶点。
（4）重复（2） （3） 直到每个点都被访问过，遍历结束。
例无权图：（默认为字母顺序）
（1）从顶点a出发，访问该图
（2）a的邻接点为bef 以b为顶点开始访问 b的邻接点有fdc
（3）b的所有的点均被访问结束，访问顶点c 顶点c还有f没有被访问
，结束遍历。
故遍历结果为 a->b->c->d->e->f
有向图：（默认为字母顺序）
（1）从顶点a出发，访问该图
（2）a 的出路顶点为b、d ，从顶点b 开始访问， b的出路只有e 结束此路；
（3）开始访问顶点d，d的出路为顶点c和f 此时所有顶点都被遍历了，结束；
故遍历结果为： a->b->e->d->c->f
1.2 算法描述
自然语言：从图中的某个顶点v出发，访问v，并将visited[v]的值为true。
一次检查v的所有邻接点w，如果visited[w]的值为flase，再从w出发进行递归遍历，直到图中的所有顶点都被访问过。
伪代码：
递归算法：
visited[mvnum] <-- false
count<--v,visited[v]<--true;
for(w<--firstadjvex(g,v);w>=0;w<--nextadjvex(g,v,w))
if(!visited[w] dfs[g,w]);
采用邻接矩阵表示：
//输入图g(v,e),w表示v的邻接点
//输出邻接矩阵
count<--v; visited[v]<--true;
for(w<--0;w<g.vexnum;w++)
if( (g.arcs[v][w]!=0)&&(!visited[w]) )
dfs(g,w);
采用邻接表：
count<--v; visited[v]<--true;
p<--g.vertices[v].firstarc;
while(p!=null) do
w<--p->adjvex;
if(!visited[w]) do dfs(g,w)
p<-- p->nextarc;
1.3用途：检查图的连通性和无环性
1.4总结：每个顶点至多进一次队列。遍历图的过程实质上市通过边找邻接点的过程。因此dfs时间复杂度，当用邻接矩阵表示图时为o(n2),其中n为图中的顶点数，当以邻接表做图的存储结构时，时间复杂度为o(e)这里e为 图中的边数，因此，当以邻接表为存储结构时，dfs时间复杂度为o(n+e)。
二、广度优先搜索（breadth-first-search 简称：bfs）
2.1遍历过程如下：
（1）从图中某个顶点v出发，访问v。
（2）依次访问v邻接各个未访问过的的所有顶点
（3）接着从这些邻接顶点中继续访问它们的邻接顶点，遵循原则 先被访问的顶点的邻接点 先于 后被访问的顶点的邻接点 被访问。重复（3）步骤，直至所有的顶点都被访问过。
这里的“先被访问的顶点的邻接点 ”指的是在第二步骤先访问的顶点然后再先访问他的邻接点，包括后来的第三步骤也是这个意思，均为上一步骤 先访问的顶点然后再先访问他的邻接点。
例：图还是上面的那张无权图
我们按照字母abcdef这样的顺序来排列
（1）以a为顶点，开始遍历
（2）a的三个邻接点bef
（3）根据字母顺序 从点b开始访问 b的临界点有cd 此时，所有的顶点均被访问
故，遍历后的结果为 a ->b-> e-> f-> c-> d
若为有向图
（1）根据字母顺序，先从顶点a开始访问
（2）看顶点a的出路，邻接点为b，d 。根据字母顺序，下一个顶点从b开始
（3）顶点b的出路为e ，且e没有出路了，故此路结束
（4）回到和b点同一级的 还有顶点d还没有被访问 d的出路有两条，分别为邻接点c 和f ，此时所有的顶点都被访问过。
故 遍历后的顺序为 a->b->d->e->c->f
2.2算法描述
自然语言：从图 中的某个顶点v出发，访问v，并将visited[v]的值为true，然后将v进队
只要队列不空，则重复下述处理：
队头顶点u出队
依次检查u的所有邻接点w，如果visited[w]的值为false，则访问w，并将visited[w]的数值为true，然后将w入队；
伪代码： //bfs算法描述
//输入：图g=<v,e>
//输出：图g的bfs遍历后的先后次序
visited[v] <--true
initqueue(q);
enqueue(q,v);
while(!queueempty(q)) do
dequeue(q,u);
for(w <--firstadjvex(g,u);w>=0;w<--nextadjvex(g,u,w))
if(!visited[w]) do
count<<w; visited[w] <--true;
enqueue（q,w);
2.3用途：计算最短路径问题
2.4.总结：每个顶点至多进一次队列。遍历图的过程实质上市通过边找邻接点的过程。因此bfs时间复杂度，当用邻接矩阵表示图时为o(n2),其中n为图中的顶点数，当以邻接表做图的存储结构时，时间复杂度为o(e)这里e为 图中的边数，因此，当以邻接表为存储结构时，bfs时间复杂度为o(n+e)。
具体的代码实现如下所示：
#include<stdio.h>
#define n 20
#define true 1
#define false 0
int visited[n]; /*访问标志数组*/
typedef struct /*队列的定义*/
{
int data[n];
int front,rear;
}queue;
typedef struct /*图的邻接矩阵*/
{
int vexnum,arcnum;
char vexs[n];
int arcs[n][n];
}
graph;
void creategraph(graph *g); /*建立一个无向图的邻接矩阵*/
void dfs(int i,graph *g); /*从第i个顶点出发深度优先搜索*/
void tdfs(graph *g); /*深度优先搜索整个图*/
void bfs(int k,graph *g); /*从第k个顶点广度优先搜索*/
void tbfs(graph *g); /*广度优先搜索整个图*/
void init_visit(); /*初始化访问标识数组*/
/*建立一个无向图的邻接矩阵*/
void creategraph(graph *g)
{
int i,j;
char v;
g->vexnum=0;
g->arcnum=0;
i=0;
printf("\n输入顶点序列(以#结束)：\n");
while ((v=getchar())!='#')
{
g->vexs[i]=v; /*读入顶点信息*/
i++;
}
g->vexnum=i; /*顶点数目*/
for (i=0;i<g->vexnum;i++) /*邻接矩阵初始化*/
for (j=0;j<g->vexnum;j++)
g->arcs[i][j] = 0;/*（1）-邻接矩阵元素初始化为0*/
printf("\n输入边的信息(顶点序号,顶点序号)，以(-1,-1)结束：\n");
scanf("%d,%d",&i,&j); /*读入边(i,j)*/
while (i!=-1) /*读入i为－1时结束*/
{
g->arcs[i][j] = 1; /*（2）-i,j对应边等于1*/
g->arcnum++;
scanf("%d,%d",&i,&j);
}
}/* creategraph */
/*（3）---从第i个顶点出发深度优先搜索，补充完整算法*/
void dfs(int i,graph *g)
{
int j;
printf("%c", g->vexs[i]);
visited[i] = true;
for (j = 0; j < g->vexnum; j++)
if (g->arcs[i][j] == 1 && !visited[j])
dfs(j, g);
}/* dfs */
/*深度优先搜索整个图*/
void tdfs(graph *g)
{
int i;
printf("\n从顶点%c开始深度优先搜索序列：",g->vexs[0]);
for (i=0;i<g->vexnum;i++)
if (visited[i] != true) /*（4）---对尚未访问过的顶点进行深度优先搜索*/
dfs(i,g);
printf("\n");
}/*tdfs*/
/*从第k个顶点广度优先搜索*/
void bfs(int k,graph *g)
{
int i,j;
queue qlist,*q;
q=&qlist;
q->rear=0;
q->front=0;
printf("%c",g->vexs[k]);
visited[k]=true;
q->data[q->rear]=k;
q->rear=(q->rear+1)%n;
while (q->rear!=q->front) /*当队列不为空，进行搜索*/
{
i=q->data[q->front];
q->front=(q->front+1)%n;
for (j=0;j<g->vexnum;j++)
if ((g->arcs[i][j]==1)&&(!visited[j]))
{
printf("%c",g->vexs[j]);
visited[j]=true;
q->data[q->rear] = j; /*（5）---刚访问过的结点入队*/
q->rear = (q->rear + 1) % n; /*（6）---修改队尾指针*/
}
}
}/*bfs*/
/*广度优先搜索整个图*/
void tbfs(graph *g)
{
int i;
printf("\n从顶点%c开始广度优先搜索序列：",g->vexs[0]);
for (i=0;i<g->vexnum;i++)
if (visited[i]!=true)
bfs(i,g); /*从顶点i开始广度优先搜索*/
printf("\n");
}/*tbfs*/
void init_visit() /*初始化访问标识数组*/
{
int i;
for (i=0;i<n;i++)
visited[i]=false;
}
int main()
{
graph ga;
int i,j;
printf("***********图邻接矩阵存储和图的遍历***********\n");
printf("\n1-输入图的基本信息：\n");
creategraph(&ga);
printf("\n2-无向图的邻接矩阵：\n");
for (i=0;i<ga.vexnum;i++)
{
for (j=0;j<ga.vexnum;j++)
printf("%3d",ga.arcs[i][j]);
printf("\n");
}
printf("\n3-图的遍历：\n");
init_visit(); /*初始化访问数组*/
tdfs(&ga); /*深度优先搜索图*/
init_visit();
tbfs(&ga); /*广度优先搜索图*/
return 0;
}
运行结果（输入的为本节中一直用到的无向图）
深度和广度查找不同之处在于对顶点的访问顺序不同。
第一次写博客，应该还是有点问题的（虽然也查了一些资料~.~）
ball ball you can point my errors! thanks a lot !
参考资料：
《数据结构（c语言版）》 严蔚敏 李冬梅 吴伟民著 人民邮电出版社
《程序设计中实用的数据结构 》 王建德 吴永辉著 人民邮电出版社