关于深度优先搜索DFS和广度优先搜索BFS算法的实现
关于深度优先搜索DFS和广度优先搜索BFS算法的实现 这是一道百度笔试
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
,深度优先搜索是从图中某个顶点v出发,访问此顶点,然后依次从v的未访问的邻接点出发深度优先遍历图,直至图中所有和v相通的顶
点都被访问到;若此时图中尚有未被访问的顶点,则另选一个未被访问的顶点作
为起始点,重复上述过程,直至图中所有定点都被访问到为止。 广度优先搜索是从图中某顶点v出发,在访问v之后依次访问v的各个未被访问的邻接点,然后分别从这些邻接点出发依次访问他们的邻接点,并使“先被访问
的邻接点”先与“后被访问的邻接点访问”,直至图中所有已被访问过的邻接点
的邻接点都被访问到为止。
C++实现代码如下
#include
using namespace std;
#define MAX_VERTEX_NUM 20
bool visited[MAX_VERTEX_NUM];
struct Graph //无向图
{
char vex[MAX_VERTEX_NUM];
int vexnum,arcnum;
int arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//1表示相邻,0表示不相邻
};
struct QNode
{
int data;
QNode *next;
};
struct LinkQueue
{
QNode *front;
QNode *rear;
};
int (*VisitFunc)(Graph G,int v);
int LocateVex(Graph G,char v) //返回顶点所在位置 {
int i;
for(i=0;i>G.vexnum >>G.arcnum ; int i;
cout<<"输入顶点字符"<>G.vex[i];
}
int j;
for(i=0;i>v1>>v2;
i=LocateVex(G,v1);
j=LocateVex(G,v2);
G.arc[i][j]=1;
G.arc[j][i]=1;
}
return 0;
}
int Visit(Graph G,int v)//访问顶点
{
cout<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 ) return 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
本文档为【关于深度优先搜索DFS和广度优先搜索BFS算法的实现】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。