Question

图的深度和广度优先遍历

题目描述

给定一个无向连通图，顶点编号从0到n-1，用深度优先搜索(DFS)和广度优先搜索(BFS)遍历，输出从某个顶点出发的遍历序列。(同一个结点的同层邻接点，节点编号小的优先遍历）

输入

第一行是三个整数k，m，t（0＜k＜100，0＜m＜(k-1)*k/2，0＜t＜k），表示有m条边，k个顶点，t为遍历的起始顶点。 下面的m行，每行是空格隔开的两个整数u，v，表示一条连接u，v顶点的无向边。

输出

两行，每行为用空格隔开的k个整数，对应一组数据，分别表示DFS和BFS的遍历结果。

样例输入
6 7 0
0 3
0 4
1 4
1 5
2 3
2 4
3 5
样例输出
0 3 2 4 1 5
0 3 4 2 5 1
提示

分别用邻接矩阵和邻接表实现

做好了最少追加50分，决不食言，急需啊，谢谢各位大大了

Answer 1

#include<iostream>
#define elemtype int
using namespace std;
const int n=8;//图中顶点数
const int e=15;// 图中的边数
const int max=1000;
int visited[n+1];//访问标志数组，为0表示未访问，为1表示已访问
int dist[n];//dist[i]存放从v到顶点i的最短路径
struct graph{//定义图的数据类型
elemtype v[n+1];//存放顶点信息v1，v2。。。vn，不使用v[0]存储空间
int arcs[n+1][n+1];//邻接矩阵
int w;//权值
};
int path[n];// path[i]存放在最短路径上从顶点i到前一点的顶点号
//该数组的作用是各点到指定始点的路径链成一条仿真链
int s[n];//s[i]=1表示顶点i的最短路径已经求出，s[i]=0表示未求出

void creat(){ //建立邻接矩阵
int i,j,k,w;
graph g;
cout<<"请输入"<<n<<"个顶点信息"<<endl;
for(k=1;k<=n;k++)
cin>>g.v[k];
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
g.arcs[i][j];
for(k=1;k<=e;k++){
cout<<"请输入第"<<k<<"条边，共"<<e<<"条边";
cin>>i>>j;
cout<<endl;
g.arcs[i][j]=1;
g.arcs[j][i]=1;
}
}
void dfs(int i, graph g){//从顶点i出发进行深度优先搜索遍历
int j;

cout<<g.v[i]<<" ";
visited[i]=1;
for(j=1;j<=n;j++)
if(g.arcs[i][j]==1&&!visited[j])
dfs(j,g);
}
void bfs(int i, graph g){//从顶点i出发进行广度优先搜索遍历
int q[n+1];//q为队列
int f,r,j;//f、r分别为队头、队尾指针
f=r=0;//初始化队列
cout<<g.v[i]<<" ";//输出访问顶点
visited[i]=1;//标记已访问的顶点
r++;q[r]=i;//入队
while(f<r){
f++;i=q[f];//出队列
for(j=1;j<=n;j++)
if((g.arcs[i][j]==1&&!visited[j])){
cout<<g.v[j]<<" ";
visited[j]=1;
r++;q[r]=j;//入队列
}

}
}
void shortestpath(const int v, graph g)
{ int i, j, k ,wm,max;
for(i=0;i<n;i++) //按网的邻接矩阵确定各顶点最短路径的初值
{dist[i]= g.arcs[v][i];
if (i!=v && dist[i]<max) path[i]= v; else path[i]= -1;
s[i]=0;
};
s[v]=1; dist[v]=0; //将顶点v本身排除在外
for(k=0;k<n-1;k++) //求其他n-1个顶点的最短路径
{ wm=max; j=v;
for(i=0;i<n;i++) //确定当前最短路径wm及顶点的序号J
if (!s[i] && dist[i] < wm)
{j=i;wm= dist[i];}
s[j]=1;
for(i=0;i<n;i++) //更新未确定最短路径各顶点的当前最短路径
if (!s[i] && dist[j] + g.arcs[j][i]< dist[i])
{dist[i] = dist[j] +g.arcs[j][i];
path[i] = j;
}
}
}
int main(){
int i,j,v;
int yn=1;
graph g;
creat();
for(i=1;i<=n;i++){
for(j=1;j<=n;j++)
cout<<g.arcs[i][j]<<" ";
cout<<endl;
}
while(yn==1){
for(i=1;i<=n;i++)
visited[i]=0;
cout<<"请输入深度优先搜索开始访问的顶点:";
cin>>i;
cout<<endl;
cout<<"从"<<i<<"出发的深度优先搜索遍历序列为"<<endl;
dfs(i,g);
cout<<endl<<"继续进行深度优先搜索吗";
cin>>yn;
}
yn=1;
while(yn==1){
for(i=1;i<=n;i++)
visited[i]=0;
cout<<"请输入广度优先搜索开始访问的顶点:";
cin>>i;
cout<<endl;
cout<<"从"<<i<<"出发的广度优先搜索遍历序列为"<<endl;
dfs(i,g);
cout<<endl<<"继续进行广度优先搜索吗";
cin>>yn;
}
cout<<"请输入顶点v的值:";
cin>>v;
shortestpath(v,g);
cout<<dist[v];
system("pause");
return 0;
}