图的遍历
图的两种遍历方法：DFS和BFS
dfs遍历代码（教材上的）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
//深度优先遍历算法 #include "graph.cpp" int visited[MAXV]={0}; void DFS(AdjGraph *G,int v) { ArcNode *p; visited[v]=1; //置已访问标记 printf("%d ",v); //输出被访问顶点的编号 p=G->adjlist[v].firstarc; //p指向顶点v的第一条弧的弧头结点 while (p!=NULL) { if (visited[p->adjvex]==0) //若p->adjvex顶点未访问,递归访问它 DFS(G,p->adjvex); p=p->nextarc; //p指向顶点v的下一条弧的弧头结点 } } int main() { AdjGraph *G; int A[MAXV][MAXV]={{0,1,0,1,1},{1,0,1,1,0}, {0,1,0,1,1},{1,1,1,0,1},{1,0,1,1,0}}; int n=5, e=8; CreateAdj(G,A,n,e); //建立《教程》中图8.1(a)的邻接表 printf("图G的邻接表:\n"); DispAdj(G); //输出邻接表G printf("深度优先序列(递归):");DFS(G,2);printf("\n"); DestroyAdj(G); //销毁邻接表 return 1; } |
bfs遍历代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
typedef struct { ElemType data[MaxSize]; int front,rear; //队首和队尾指针 } SqQueue; void InitQueue(SqQueue *&q) { q=(SqQueue *)malloc (sizeof(SqQueue)); q->front=q->rear=0; } void DestroyQueue(SqQueue *&q) { free(q); } bool QueueEmpty(SqQueue *q) { return(q->front==q->rear); } bool enQueue(SqQueue *&q,ElemType e) { if ((q->rear+1)%MaxSize==q->front) //队满上溢出 return false; q->rear=(q->rear+1)%MaxSize; q->data[q->rear]=e; return true; } bool deQueue(SqQueue *&q,ElemType &e) { if (q->front==q->rear) //队空下溢出 return false; q->front=(q->front+1)%MaxSize; e=q->data[q->front]; return true; } //--------------------------------------------------------- void BFS(AdjGraph *G,int v) { int w,i; ArcNode *p; SqQueue *qu; //定义环形队列指针 InitQueue(qu); //初始化队列 int visited[MAXV]; //定义顶点访问标志数组 for (i=0;i<G->n;i++) visited[i]=0; //访问标志数组初始化 printf("%2d",v); //输出被访问顶点的编号 visited[v]=1; //置已访问标记 enQueue(qu,v); while (!QueueEmpty(qu)) //队不空循环 { deQueue(qu,w); //出队一个顶点w p=G->adjlist[w].firstarc; //指向w的第一个邻接点 while (p!=NULL) //查找w的所有邻接点 { if (visited[p->adjvex]==0) //若当前邻接点未被访问 { printf("%2d",p->adjvex); //访问该邻接点 visited[p->adjvex]=1; //置已访问标记 enQueue(qu,p->adjvex); //该顶点进队 } p=p->nextarc; //找下一个邻接点 } } printf("\n"); } int main() { AdjGraph *G; int A[MAXV][MAXV]={{0,1,0,1,1},{1,0,1,1,0}, {0,1,0,1,1},{1,1,1,0,1},{1,0,1,1,0}}; int n=5, e=8; CreateAdj(G,A,n,e); //建立《教程》中图8.1(a)的邻接表 printf("图G的邻接表:\n"); DispAdj(G); //输出邻接表G printf("广度优先序列:");BFS(G,2);printf("\n"); DestroyAdj(G); //销毁邻接表 return 1; } |
图的遍历的应用
基于深度优先遍历的应用
假设图采用邻接表存储，设计一个算法，判断无向图g是否连通。若连通返回true，否则返回false
只需要设计一个函数，将visited数组初始化为0，然后调用dfs函数，从任何一个顶点开始遍历，只会遍历一遍visited数组，当我们发现有值为0的元素就说明该图是不连通的，因为有顶点没有被访问到
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
//【例8.3】的算法:判断无向图G是否连通 #include "graph.cpp" int visited[MAXV]; //全局数组 void DFS(AdjGraph *G,int v) //深度优先遍历算法 { ArcNode *p; visited[v]=1; //置已访问标记 printf("%d ",v); //输出被访问顶点的编号 p=G->adjlist[v].firstarc; //p指向顶点v的第一个邻接点 while (p!=NULL) { if (visited[p->adjvex]==0) //若p->adjvex顶点未访问,递归访问它 DFS(G,p->adjvex); p=p->nextarc; //p指向顶点v的下一个邻接点 } } bool Connect(AdjGraph *G) //判断无向图G的连通性 { int i; bool flag=true; for (i=0;i<G->n;i++) //visited数组置初值 visited[i]=0; DFS(G,0); //调用前面的中DSF算法,从顶点0开始深度优先遍历 for (i=0;i<G->n;i++) if (visited[i]==0) { flag=false; break; } return flag; } int main() { AdjGraph *G; int A[MAXV][MAXV]={{0,1,0,1,1},{1,0,1,1,0}, {0,1,0,1,1},{1,1,1,0,1},{1,0,1,1,0}}; int n=5, e=8; CreateAdj(G,A,n,e); //建立《教程》中图8.1(a)的邻接表 printf("图G的邻接表:\n"); DispAdj(G); //输出邻接表G printf("\n图G%s连通的\n",(Connect(G)?"是":"不是")); DestroyAdj(G); //销毁邻接表 return 1; } |
设计一个算法判断从顶点u到v是否存在简单路径
稍微改动一下dfs函数，增加两个形参，v和has，其中has表示判断，v则表示终点，dfs起点从u开始，中间添加条件判断语句，当u等于v时候，则找到了。参数中，u不断变换，就是dfs的带入顶点，v则一直不变
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
//【例8.4】的算法:判断图G中从顶点u到v是否存在简单路径 #include "graph.cpp" int visited[MAXV]; //全局数组 void ExistPath(AdjGraph *G,int u,int v,bool &has) { //has表示u到v是否有路径,初值为false int w; ArcNode *p; visited[u]=1; //置已访问标记 if (u==v) //找到了一条路径 { has=true; //置has为true并返回 return; } p=G->adjlist[u].firstarc; //p指向顶点u的第一个邻接点 while (p!=NULL) { w=p->adjvex; //w为顶点u的邻接点 if (visited[w]==0) //若w顶点未访问,递归访问它 ExistPath(G,w,v,has); p=p->nextarc; //p指向顶点u的下一个邻接点 } } int main() { AdjGraph *G; int A[MAXV][MAXV]={{0,1,0,1,1},{1,0,1,1,0}, {0,1,0,1,1},{1,1,1,0,1},{1,0,1,1,0}}; int n=5, e=8; CreateAdj(G,A,n,e); //建立《教程》中图8.1(a)的邻接表 printf("图G的邻接表:\n"); DispAdj(G); //输出邻接表G bool has=false; int u=0, v=3; ExistPath(G,u,v,has); printf("\n图G中顶点%d到顶点%d%s路径\n\n",u,v,(has?"有":"没有")); DestroyAdj(G); //销毁邻接表 return 1; } |
设计一个算法，输出从顶点u到v的一条简单路径（假设从顶点u到v至少有一条简单路径）
和上面的一样，稍微修改一下dfs函数，增加一个path数组类型的形参，和d形参（表示路径长度），和v形参（终点）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
//【例8.5】的算法:输出图G中从顶点u到v的一条简单路径 #include "graph.cpp" int visited[MAXV]; //全局数组 void FindaPath(AdjGraph *G,int u,int v,int path[],int d) { //d表示path中的路径长度，初始为-1 int w,i; ArcNode *p; visited[u]=1; d++; path[d]=u; //路径长度d增1，顶点u加入到路径中 if (u==v) //找到一条路径后输出并返回 { for (i=0;i<=d;i++) printf("%d ",path[i]); printf("\n"); return; } p=G->adjlist[u].firstarc; //p指向顶点u的第一个邻接点 while (p!=NULL) { w=p->adjvex; //邻接点的编号为w if (visited[w]==0) FindaPath(G,w,v,path,d); p=p->nextarc; //p指向顶点u的下一个邻接点 } } int main() { AdjGraph *G; int A[MAXV][MAXV]={{0,1,0,1,1},{1,0,1,1,0}, {0,1,0,1,1},{1,1,1,0,1},{1,0,1,1,0}}; int n=5, e=8; CreateAdj(G,A,n,e); //建立《教程》中图8.1(a)的邻接表 printf("图G的邻接表:\n"); DispAdj(G); //输出邻接表G int u=0, v=3; int path[MAXV]; printf("\n图G中顶点%d到顶点%d的一条简单路径为:",u,v); FindaPath(G,u,v,path,-1); DestroyAdj(G); //销毁邻接表 return 1; } |
设计一个算法，输出从顶点u到v的所有条简单路径（假设从顶点u到v至少有一条简单路径
采用回溯法
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
//【例8.6】的算法:输出图G中从顶点u到v的所有简单路径 #include "graph.cpp" int visited[MAXV]; //全局数组 void FindAllPath(AdjGraph *G,int u,int v,int path[],int d) { //d表示path中的路径长度，初始为-1 int w,i; ArcNode *p; d++; path[d]=u; //路径长度d增1，顶点u加入到路径中 visited[u]=1; //置已访问标记 if (u==v && d>=0) //找到一条路径则输出 { for (i=0;i<=d;i++) printf("%2d",path[i]); printf("\n"); } p=G->adjlist[u].firstarc; //p指向顶点u的第一个邻接点 while (p!=NULL) { w=p->adjvex; //w为顶点u的邻接点 if (visited[w]==0) //若w顶点未访问,递归访问它 FindAllPath(G,w,v,path,d); p=p->nextarc; //p指向顶点u的下一个邻接点 } visited[u]=0; //恢复环境,使该顶点可重新使用 } int main() { AdjGraph *G; int A[MAXV][MAXV]={{0,1,0,1,1},{1,0,1,1,0}, {0,1,0,1,1},{1,1,1,0,1},{1,0,1,1,0}}; int n=5, e=8; CreateAdj(G,A,n,e); //建立《教程》中图8.1(a)的邻接表 printf("图G的邻接表:\n"); DispAdj(G); //输出邻接表G int u=0, v=3; int path[MAXV]; printf("\n图G中顶点%d到顶点%d的所有简单路径:\n",u,v); FindAllPath(G,u,v,path,-1); DestroyAdj(G); //销毁邻接表 return 1; } |
设计一个算法，输出图g中从顶点u到v的长度为l的所有简单路径
增加一个形参l，在判断语句中增加d==l即可，形参l为指定长度
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
//【例8.7】的算法:输出图G中从顶点u到v的长度为l的所有简单路径 #include "graph.cpp" int visited[MAXV]; void PathAll(AdjGraph *G,int u,int v,int l,int path[],int d) { //d表示path中的路径长度，初始为-1 int w,i; ArcNode *p; visited[u]=1; d++; path[d]=u; //路径长度d增1，顶点u加入到路径中 if (u==v && d==l) //输出一条路径 { printf(" "); for (i=0;i<=d;i++) printf("%d ",path[i]); printf("\n"); } p=G->adjlist[u].firstarc; //p指向顶点u的第一个邻接点 while (p!=NULL) { w=p->adjvex; //w为u的邻接点 if (visited[w]==0) //若该顶点未标记访问,则递归访问之 PathAll(G,w,v,l,path,d); p=p->nextarc; //p指向顶点u的下一个邻接点 } visited[u]=0; //恢复环境：使该顶点可重新使用 } int main() { int path[MAXV]; int u=1,v=4,l=3; int n=5, e=8; int A[MAXV][MAXV]={ {0,1,0,1,1}, {1,0,1,1,0}, {0,1,0,1,1}, {1,1,1,0,1}, {1,0,1,1,0}}; AdjGraph *G; CreateAdj(G,A,n,e); //建立图8.1(a)的邻接表 for (int i=0;i<n;i++) //visited数组置初值 visited[i]=0; printf("图G:\n");DispAdj(G);//输出邻接表 printf("从顶点%d到%d的所有长度为%d路径:\n",u,v,l); PathAll(G,u,v,l,path,-1); printf("\n"); DestroyAdj(G); //销毁邻接表 return 1; } |
教材还有两个应用，太难这里不写了，看看以后刷题要是遇到该类问题，后面再补
基于广度优先遍历的应用
