关于深度优先搜索DFS和广度优先搜索BFS算法的实现

1、关于深度优先搜索DFS和广度优先搜索BFS算法的实现 这是一道百度笔试题， 深度优先搜索是从图中某个顶点 v 出发，访问此顶点， 然 后依次从 v 的未访问的邻接点出发深度优先遍历图， 直至图中所有和 v 相通的顶 点都被访问到； 若此时图中尚有未被访问的顶点， 则另选一个未被访问的顶点作 为起始点，重复上述过程，直至图中所有定点都被访问到为止。广度优先搜索是从图中某顶点 v 出发，在访问 v 之后依次访问 v 的各个未被访问 的邻接点，然后分别从这些邻接点出发依次访问他们的邻接点， 并使“先被访问 的邻接点”先与“后被访问的邻接点访问”， 直至图中所有已被访问过的邻接点 的邻接点都被访问到为

2、止。C+实现代码如下#include<iostream>using namespace std;#define MAX_VERTEX_NUM 20bool visitedMAX_VERTEX_NUM;struct Graph / 无向图char vexMAX_VERTEX_NUM;int vexnum,arcnum;int arcMAX_VERTEX_NUMMAX_VERTEX_NUM;表示相邻，0 表示不相邻;struct QNodeint data;QNode *next;struct LinkQueueQNode *front;QNode *rear;int (*VisitF

3、unc)(Graph G,int v);int LocateVex(Graph G,char v) / 返回顶点所在位置int i;for(i=0;i<G.vexnum;i+)if(v=G.vex i) return i;return 0;int CreateGraph(Graph &G) / 创建无向图cout<<" 输入顶点数和边数： "<<endl; cin>>G.vexnum >>G.arcnum ; int i;cout<<" 输入顶点字符 "<<endl;

4、for(i=0;i<G.vexnum ;i+) cin>>G.vexi; int j;for(i=0;i<G.vexnum;i+) for(j=0;j<G.vexnum;j+)G.arcij=0; char v1,v2; int k; cout<<" 输入相邻的两顶点 "<<endl; for(k=0;k<G.arcnum;k+) cin>>v1>>v2; i=LocateVex(G,v1); j=LocateVex(G,v2);G.arcij=1;G.arcji=1; return 0;i

5、nt Visit(Graph G,int v)/ 访问顶点 cout<<G.vexv<<" " return 1;的第一个邻接点的下一个邻接点int FirstAdjVex(Graph G,int v) /v int j;for(j=v+1;j<G.vexnum;j+) if(G.arcvj=1) return j; return 0; int NextAdjVex(Graph G,int v,int w)/v int j;for(j=w+1;j<G.vexnum ;j+)if(G.arcvj=1) return j;return 0;v

6、oid DFS(Graph G,int v)visitedv=true;VisitFunc(G,v);int w;for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w) if(!visitedw) DFS(G,w);深度优先搜索void DFSTraverse(Graph G,int(*Visit)(Graph G,int v)/ VisitFunc=Visit;int v;for(v=0;v<G.vexnum;v+)visitedv=false;for(v=0;v<G.vexnum;v+)if(!visitedv) DFS(G,v);int In

7、itQueue(LinkQueue &Q) / 初始化队列Q.front =Q.rear=new QNode;if(!Q.front)return 0;return 1;int EnQueue(LinkQueue &Q,int v)/ 入队列QNode *p=new QNode;if(!p) return 0;p->data =v;p->next =NULL;Q.rear->next =p;Q.rear=p;return 1;int DeQueue(LinkQueue &Q,int &v)/出队列 if(Q.front =Q.rear ) re

8、turn 0;QNode *p=Q.front ->next ; v=p->data ;Q.front ->next =p->next ; if(Q.rear =p)Q.rear =Q.front; delete p;return 1;bool QueueEmpty(LinkQueue Q)/ 队列是否为空 if(Q.front =Q.rear ) return true; return false;广度优先搜索void BFSTraverse(Graph G,int (*Visit)(Graph G,int v)/ int v;int w,u; for(v=0;v&l

9、t;G.vexnum ;v+) visitedv=false; LinkQueue Q;InitQueue(Q); for(v=0;v<G.vexnum;v+) if(!visitedv) visitedv=true;Visit(G,v);EnQueue(Q,v); while(!QueueEmpty(Q) DeQueue(Q,u); for(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w) if(!visitedw) visitedw=true;Visit(G,w);EnQueue(Q,w);int main()Graph G;CreateGraph(G);/*for(int i=0;i<G.vexnum ;i+)for(int j=0;j<G.vexnum ;j+) cout<<G.arc ij<<"