图的遍历
和树的遍历类似,图的遍历也是从图中某一顶点出发,按照某种方法对图中所有顶点访问且仅访问一次。图的遍历又比树的遍历复杂得多。因为图的任一顶点都可能和其余的顶点相邻接。所以在访问了某个顶点之后,可能沿着某条路径搜索之后,又回到该顶点上。根据搜索路径的方向,通常有两条遍历图的路径:深度优先搜索和广度优先搜索。它们对无向图和有向图都适用。
深度优先搜索
概念
深度优先搜索遍历类似于树的先序遍历,是树的先序遍历的推广
深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。讲通俗一点,深度优先搜索其实像在走迷宫,遇到一个岔路口,先选则一条路,当发现这条路是死路时,又返回岔路口选择第二条路,直至找到出口。
过程
对于一个连通图,深度优先搜索遍历过程:
1.从图中某个顶点v出发,访问v;
2.找出刚刚访问过的顶点的第一个未被访问的邻接点,访问该顶点。以该顶点为新顶点,重复该步骤,直至刚访问过的顶点没有未被访问的邻接点为止;(递归思想)
3.返回前一个访问过的且仍有未被访问的邻接点的顶点,找出该顶点的下一个未被访问的邻接点,访问该顶点;
4.重复第2、3步骤,直至图中所有顶点都被访问过,搜索结束。
遍历过程具体如下图:
(1)从顶点v1出发,访问v1;
(2)在访问顶点v1之后,选择第一个未被访问的邻接点v2,访问v2。以v2为新顶点,重复此步,访问v4,v8,v5。在访问v5之后,由于v5的邻接点都已被访问,此步结束;
(3)搜索从v5回到v8,由于同样的理由,搜索继续回到v4,v2直到v1,此时由于v1的另一个邻接点未被访问,则又从v1到v3,再继续进行下去。
由此得到的顶点访问序列为:
v1 -> v2 -> v4 -> v8 -> v5 -> v3 -> v6 -> v7
(访问的具体过程如下图)
算法实现
深度优先搜索过程遍历连通图是一个递归过程,为了在遍历过程中便于区分顶点是否已被访问,需要附设访问标志数组visited[n],其初值为“false”,一旦某个顶点被访问,则其相应的分量置为”true”。代码如下:
#define MaxVertices 100
#define MAX_VERTEX_NUM 10
typedef struct node{ //边表
int adjvex;
struct node* next;
}EdgeNode;
typedef struct{ //顶点表
int vertex;
EdgeNode* edgenext;
}VertexNode;
typedef VertexNode AdjList[MaxVertices];
typedef struct{
AdjList adjlist;
int n,e;
}AdjMatrix;
int visited[MAX_VERTEX_NUM];
void DFS(AdjMatrix *G, int v) {
EdgeNode *p;
printf("->%c",G->adjlist[v].vertex);
visited[v]=1;
p=G->adjlist[v].edgenext;
while (p) {
if(!visited[p->adjvex]) DFS(G,p->adjvex);
p=p->next;
}
} //从第v个顶点出发DFS
void DFSTraverse(AdjMatrix *G) {
int v;
for(v=0;v<G->n;++v)
visited[v]=0;
for(v=0;v<G->n;++v)
if(!visited[v]) DFS(G,v);//递归调用
printf("\n\n");
}//DFSTraverse
广度优先搜索
概念
广度优先搜索遍历类似于树的按层次遍历的过程。广度优先搜索算法(又称宽度优先搜索)是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。其别名又叫BFS,属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。
过程
对于连通图(图如上深度搜索的连通图)
1.从图中某个顶点出发,访问v;
2.依次访问v的各个未曾访问过的邻接点;
3.分别从这些邻接点出发依次访问它们的邻接点,并使“先被访问的顶点的邻接点”先于“后被访问的邻接点”被访问。重复步骤3,直至图中所有已被访问的顶点的邻接点都被访问到。
具体的例子如下图:
(1)从顶点v1出发,访问v1;
(2)依次访问v1的各个未被访问过的邻接点v2和v3;
(3)依次访问v2的各个邻接点v4和v5,以及v3的邻接点v6和v7,最后访问v4的邻接点v8。由于这些顶点的邻接点均已被访问,并且图中所有顶点都被访问,由此完成了图的遍历。得到顶点的访问序列为:
v1 -> v2 -> v3 -> v4 -> v5 -> v6 -> v7 -> v8
(具体访问过程如下图)
算法实现
广度优先搜索的特点是:尽可能先对横向进行搜索。设x和y是两个相继被访问过的顶点,若当前以x为出发点进行搜索,则在访问x的所有未被访问过的邻接点之后,紧接着是以y为出发点进行横向搜索,并对搜索到的y的邻接点中尚未被访问的顶点进行访问。也就是说,先访问的顶点其邻接点亦先被访问。为此,算法实现时需要引进队列保存已被访问过的顶点。
#define bool char
#define true 1
#define false 0//定义bool类型的数
bool visited[100];//访问标志数组,其初值为"false"
//bool为一种数据类型,其值只有两个true和false,只有在面向对象的语言中有这种类型的数据类型,在c语言中不存在,但是我们可以自己定义
typedef char VerTexType;//假设顶点的数据类型为字符型
typedef int ArcType;//假设边的权值类型为整型
struct AMGraph{
VerTexType vexs[100];//顶点表
ArcType arcs[100][100];//;邻接矩阵
int vexnum,arcnum;//图的当前点数和边数
};
void create(CyQueue *q) {
q->base=(dataType *)malloc(Maxsize*sizeof(dataType));
if(!q->base) {
printf("Space allocation failed!\n");
return;
}
q->front=q->rear=0;
return;
}
void EnQueue(CyQueue *q,dataType value) {
if((q->rear+1)%Maxsize==q->front)
{
printf("Cyclic Queue is Full!\n");
return;
}
q->base[q->rear]=value;
q->rear=(q->rear+1)%Maxsize;
return;
}
void DeQueue(CyQueue *q,dataType *value) {
if(q->front==q->rear)
{
printf("Cyclic Queue is Empty!\n");
return;
}
*value=q->base[q->front];
q->front=(q->front+1)%Maxsize;
return;
}
int QueueEmpty(CyQueue *q) {
if (q->front==q->rear)//队列为空返回1,不为空返回0
{
return 1;
}
return 0;
}
void BFS(struct AMGraph *G,int i) {
int j;
CyQueue q;
create(&q); //1.设置起始点
printf("%c",G->Vertex[i]);//1.输出起始结点
visited[i]=1;//2.将已访问的结点标志成1
EnQueue(&q,i);//3.将第一个结点入队
//2.由起始点开始,对后续结点进行操作
while(!QueueEmpty(&q))//队列非空
{
DeQueue(&q,&i);
for(j=0;j<G->vexnum;j++) {
if(G->AdjMatrix[i][j]==1&&visited[j]==0) {
printf("%c",G->Vertex[j]);//输出符合条件的顶点
visited[j]=1;//设置成已访问状态1
EnQueue(&q,j);//入队
}
}
}
}
总结
深度优先搜索算法的实现运用的主要是回溯法,类似于树的先序遍历算法。
广度优先搜索算法借助队列的先进先出的特点,类似于树的层次遍历。