6-3数据结构考题-图的深度优先搜索
6-3 数据结构考题 - 图的深度优先搜索 (25 分)
以邻接矩阵作存储结构，编写程序对给定的⽆向图（图中包含n个顶点，编号为0⾄n-1）进⾏深度优先遍历，并在遍历的过程中计算图G的连通分量个数。
邻接矩阵的类型描述
#define MaxVexNum 20 //最⼤顶点数⽬
typedef struct
{int arcs[MaxVexNum][MaxVexNum];
int vexnum, arcnum;求好看的电影
}AMGraph;
本题限定在遍历过程中，如果同时出现多个待访问的顶点，则优先选择编号最⼩的⼀个进⾏访问，以顶点0为遍历起点。
下⾯给出了 图的深度优先搜索 函数的⼤部分内容，但缺少了⼀部分（以下划线____标识出来的部分）。
请先将以下代码中画横线的部分补充完整，然后将完整的函数DFS,DFSTraver 以及相关全局变量的定义 提交系统，完成题⽬要求的功能。
函数接⼝定义：
bool visited[MaxVerNum];
void DFS(MGraph G,int v)
插花比赛{
int w;
cout<<v<<' ';
visited[v]= ____ ;
for( w=0; w< ____ ; w++)
{
if( G.arcs[ ____ ][ ____ ]==1)
{
if( ____ )
____ ;
}
}
}
int n=0;
void DFSTraver(MGraph G)
{
int v;
for(v=0;v< ____ ;v++)
visited[v]= ____ ;
for(v=0;v< ____ ;v++)
{
if( ____ )
{
DFS(G, ____ );
____ ;
}
长荡湖水街}
}
其中：
void DFS(MGraph G,int v) 是从 v 出发深度优先搜索图的连通分量 的函数
void DFSTraver(MGraph G) 是深度优先搜索图函数
int n=0; ⽤来记录连通分量个数
测试主程序样例：
// 创建⽆向图
void CreateUDG(MGraph &G)
{
int i,j,k;int v1,v2;
cin>>G.vexnum>>G.arcnum;
for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
G.arcs[i][j]=0;
for(k=1;k<=G.arcnum;k++)
{
cin>>v1>>v2;
G.arcs[v1][v2]=G.arcs[v2][v1]=1;
}
}
int main()
{
MGraph G;
CreateUDG(G);
DFSTraver(G);
cout<<endl<<n<<endl;
return0;
}
输⼊格式:
第⼀⾏输⼊图的顶点数和边数。
接下来每⾏代表⼀条边，输⼊边依附的两个顶点的编号。各边输⼊先后次序⽆要求。
输出格式
输出分2⾏
第⼀⾏ 深度优先遍历序列。序列中每个顶点编号后跟⼀个空格。
第⼆⾏ 连通分量个数
对于下⾯给出的⽆向图G
输⼊样例:
9 8
0 1
0 2
1 3土建类
3 4
2 5
2 6
5 6
7 8
结尾⽆空⾏
输出样例:
0 1 3 4 2 5 6 7 8
2
千钓一发结尾⽆空⾏
C：
bool visited[MaxVerNum];
void DFS(MGraph G,int v)
{
int w;
cout << v <<' ';
visited[v]=1;
for(w =0; w < G.vexnum; w++) {
if(G.arcs[v][w]==1)
{
if(visited[w]==0)
DFS(G,w);
}
}
中至>雅思核心词汇}
int n =0;
void DFSTraver(MGraph G)
美好的选择作文600字
{
int v;
for(v =0; v < G.vexnum; v++) visited[v]=0;
for(v =0; v < G.vexnum; v++) {
if(visited[v]==0)
{
DFS(G, v);
n++;
}
}
}
