深度优先搜索算法实现
前言：
在描述DFS实现原理之前首先需要搞清楚图的基本存储方式或结构，这里讲述两种：邻接矩阵和邻接表
邻接矩阵
存储方式采用两个数组来表示图：一个一维数组存储图中结点信息，一个二维数组即邻接矩阵存储图中的边或弧的信息 注：图分为有向图、无向图，如果每条边上带有权则称之为网 使用邻接矩阵存储图可以轻松实现查找顶点邻接点的操作，但是若是统计图中边或弧的数量，则需要按行和列对每个元素进行判断，同时使用*两个数组分别存储顶点信息和关系信息，花费比较大
邻接矩阵创建图
typedef char VertexType;
typedef int EdgeType;
#define MAXVEX 100 //最大顶点数
#define INFINITY 65535 //代表无穷
typedef struct{
VertexType vexs[MAXVEX];
EdgeType arc[MAXVEX][MAXVEX];
int numVertex, numEdges;
}MGraph;
void CreateGraph(MGraph *G){
int i, j, k, w;
printf("输入定点数和边数: \n");
scanf("%d, %d", &G->numVertex, &G->numEdges);
for(int i = 0; i < G->numVertex; i++){//输入顶点，建立顶点表
scanf(&G->vexs[i]);
}
for(int i = 0; i < G->numVertex; i++){//邻接矩阵初始化
for(int j = 0; j < G->numVertex; j++){
G->aarc[i][j] = INFINTY;
}
}
for(k = 0; k < G->numEdges; k++){
printf("输入边<Vi, Vj>上的下标 i和j以及权w: \n");
scanf("%d, %d, %d", &i, &j, &w);
G->arc[i][j] = w;
G->arc[i][j] = G->arc[j][i];//无向图对称
}
}
邻接表
- 图中的顶点由一个一维数组存储，每个数据元素还需存储指向第一个邻接顶点的指针，以便查找该顶点的边信息
- 图中每个顶点v的所有邻接顶点构成一个线性表，由于邻接点个数不定，故而采用单链表 ## DFS基本思想描述： 首先访问某一个起始顶点v，然后有v出发，访问与v邻接且未被访问的任意结点w1，再访问与w1邻接且未被访问的任一顶点w2，...重复上述过程。当不能继续向下访问时，依次会退到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该顶点继续上述搜索过程，直到途中所有顶点均被访问过为止。 ## 算法导论中的伪码描述：
//u 为 v 的先辈或父母。
DFS(G)
1 for each vertex u ∈ V [G]
2 do color[u] ← WHITE
3 π[u] ← NIL
//第1-3行，把所有顶点置为白色，所有π 域被初始化为NIL, π[u]即为u的前驱顶点，初始化
4 time ← 0 //复位时间计数器
5 for each vertex u ∈ V [G]
6 do if color[u] = WHITE
7 then DFS-VISIT(u) //调用DFS-VISIT访问u，u成为深度优先森林中一棵新的树
//第5-7行，依次检索V中的顶点，发现白色顶点时，调用DFS-VISIT访问该顶点。
//每个顶点u 都对应于一个发现时刻d[u]和一个完成时刻f[u]。
DFS-VISIT(u)
1 color[u] ← GRAY //u 开始时被发现，置为灰色
2 time ← time +1 //time 递增
3 d[u] ← time //记录u被发现的时间
4 for each v ∈ Adj[u] //检查并访问 u 的每一个邻接点 v Adj[u]b表示u所有的邻接点
5 do if color[v] = WHITE //如果v 为白色，则递归访问v。
6 then π[v] ← u //置u为 v的先辈
7 DFS-VISIT(v) //递归深度，访问邻结点v
8 color[u] ← BLACK //u 置为黑色，表示u及其邻接点都已访问完成
9 f [u] ← time ← time +1 //访问完成时间记录在f[u]中。
//完
/*第1-3行，5-7行循环占用时间为O（V），此不包括调用DFS-VISIT的时间。
对于每个顶点v(-V，过程DFS-VISIT仅被调用1次，因为只有对白色顶点才会调用此过程。
第4-7行，执行时间为O（E）。
因此，总的执行时间为O(V+E)。*/
DFS的c代码实现（采用的是邻接表结构建的图）
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#define MaxNum 10
struct enode /*定义表结点结构*/
{
int adjvex; //对应的是结点的序号0,1,2。。。
struct enode* next;
}enode;
struct vnode /*定义顶点结点结构*/
{
char vertex;
struct enode* firstedge;
}vnode;
struct ALGraph /*定义图结构*/
{
struct vnode adjlist[MaxNum];//存储的是结点的名称如v1，v2。。。
int n, e;
}ALGraph;
int locate_vex(struct ALGraph*G, char vex)//定位定点vex在有向图中G中的序号位置
{
int i;
for(i = 0; i < G->n; i++)
{
if(G->adjlist[i].vertex == vex)
return i;
}
}
void createGraph(struct ALGraph* G)
{
int i, j, k;
char vex1, vex2;
struct enode * s;
printf("\n请输入有向图的顶点名称：");
for(i = 0; i < G->n; i++)
{
scanf_s("\n%c", &G->adjlist[i].vertex);
G->adjlist[i].firstedge = NULL;
}
printf("\n请输入有向图的每条弧的弧尾顶点和弧头顶点名称：");
for (k = 0; k < G->e; k++)
{
printf("\n请输入第%d条弧的弧尾顶点名称：", k+1);
scanf_s("\n%c", &vex1);
printf("\n请输入第%d条弧的弧头顶点名称：", k+1);
scanf_s("\n%c", &vex2);
i = locate_vex(G, vex1);
j = locate_vex(G, vex2);
s = (struct enode*)malloc(sizeof(struct enode));
s->adjvex = j;
s->next = G->adjlist[i].firstedge;
G->adjlist[i].firstedge = s;
}
}
void outGraph(struct ALGraph* G)//输出图结构
{
int i, j;
struct enode* s;
printf("\n\n有向图有%d个顶点", G->n);
for (int i = 0; i < G->n; i++)
{
printf("%c", G->adjlist[i].vertex);
}
printf("\n\n有向图有%d个弧", G->e);
for (int i = 0; i < G->n; i++)
{
printf("\n%c->", G->adjlist[i].vertex);
s = G->adjlist[i].firstedge;
while (s)
{
printf("%c ", G->adjlist[s->adjvex].vertex);
s = s->next;
}
}
}
int visited[MaxNum];
void DFS(struct ALGraph *G, int i)//从n个结点中任意选取一个开始遍历
{
struct enode *p;
printf("访问顶点%c", G->adjlist[i].vertex);
visited[i] = 1;
p = G->adjlist[i].firstedge;
while(p)
{
if(!visited[p->adjvex])
{
DFS(G, p->adjvex);
}
p = p->next;
}
}
void DFSTraverse(struct ALGraph *G)
{
int i;
for(i = 0; i < G->n; i++)
{
visited[i] = 0;
}
printf("\n");
for(i = 0; i < G->n; i++)
{
if(!visited[i])
{
DFS(G, i);
}
}
}
void main()
{
struct ALGraph alg;
printf("\n有向图存储结构。。。");
printf("\n请输入有向图的顶点数目：");
scanf_s("%d",&alg.n);
printf("\n请输入有向图的弧数目：");
scanf_s("%d",&alg.e);
createGraph(&alg);
outGraph(&alg);
DFSTraverse(&alg);
getch();
}
BFS
BFS(G, s)
for each vertex u ∈ V [G] - {s}
do color[u] ← WHITE
d[u] ← ∞
π[u] ← NIL
//除了源顶点s之外，第1-4行置每个顶点为白色，置每个顶点u的d[u]为无穷大，
//置每个顶点的父母为NIL。
color[s] ← GRAY
//第5行，将源顶点s置为灰色，这是因为在过程开始时，源顶点已被发现。
d[s] ← 0 //将d[s]初始化为0。
π[s] ← NIL //将源顶点的父顶点置为NIL。
Q ← Ø //队列为空，初始化
ENQUEUE(Q, s) //入队
//第8、9行，初始化队列Q，使其仅含源顶点s。
while Q ≠ Ø
do u ← DEQUEUE(Q) //出队
//第11行，确定队列头部Q头部的灰色顶点u，并将其从Q中去掉。
for each v ∈ Adj[u] //for循环考察u的邻接表中的每个顶点v
do if color[v] = WHITE
then color[v] ← GRAY //置为灰色
d[v] ← d[u] + 1 //距离被置为d[u]+1
π[v] ← u //u记为该顶点的父母
ENQUEUE(Q, v) //插入队列中
color[u] ← BLACK //u 置为黑色
//12-18行就是检查完顶点u的邻接链表中的所有顶点后，将u置为灰色
下面我将以更为直观的图示来分析： 图片后面补充。。
