题目内容
（请给出正确答案）
[主观题]
通过对无向图进行先深搜索，可以判断该图是否是连通图，或找出图的连通分量及先深生成树。
提问人：网友shys111
发布时间：2022-01-07
题目内容
（请给出正确答案）
如搜索结果不匹配，请 您可能会需要：
安装简答题APP，拍照搜题省时又省心！
更多“通过对无向图进行先深搜索，可以判断该图是否是连通图，或找出图…”相关的问题
第5题
对下图所示的无向图，从顶点V1开始进行深度遍历，可得到顶点访问序列是（ ）。 
A、1 2 4 3 5 7 6
B、1 2 4 3 5 6 7
C、1 2 4 5 6 3 7
D、1 2 3 4 5 7 6
第6题
阅读下列函数说明和C代码，
[说明]
所谓货郎担问题，是指给定一个无向图，并已知各边的权，在这样的图中，要找一个闭合回路，使回路经过图中的每一个点，而且回路各边的权之和最小。
应用贪婪法求解该问题，程序先计算由各点构成的所有边的长度(作为边的权值)，按长度大小对各边进行排序后，按贪婪准则从排序后的各边中选择组成回路的边，贪婪准则使得边的选择按各边长度从小到大选择。
函数中使用的预定义符号如下：
define M 100
typedef struct{/*x为两端点p1、p2之间的距离，p1、p2所组成边的长度*/
float x；
int p1，p2；
}tdr；
typedef struct{/*p1、p2为和端点相联系的两个端点，n为端点的度*/
int n，p1，p2；
}tr；
typedef struct{/*给出两点坐标*/
float x，y；
}tpd；
typedef int tl[M]；
int n=10；
[函数]
float distance(tpd a，tpd b)；/*计算端点a、b之间的距离*/
void sortArr(tdr a[M]，int m)；
/*将已经计算好的距离关系表按距离大小从小到大排序形成排序表，m为边的条数*/
int isCircuit(tr r[M]，int i，int j)；
/*判断边(i，j)选入端点关系表r[M]后，是否形成回路，若形成回路返回0*/
void selected(tr r[M]，int i，int j)；/*边(i，j)选入端点关系表r*/
void course(tr r [M]，tl l[M])；/*从端点关系表r中得出回路轨迹表*/
void exchange(tdr a[M]，int m，int b)；
/*调整表排序表，b表示是否可调，即是否有长度相同的边存在*/
void travling(tpd pd [M]，int n，float dist，tl locus[M])
/*dist记录总路程*/
{
tdr dr[M]；/*距离关系表*/
tr r[M]；/*端点关系表*/
int i，j，k，h，m；/*h表示选入端点关系表中的边数*/
int b；/*标识是否有长度相等的边*/
k=0；
/*计算距离关系表中各边的长度*/
for(i=1；i＜n； i++){
for(j=i+1；J＜=n；j++){
k++;
dr[k]．x=(1);
dr[k]．pl=i;
dr[k]．p2=j;
}
}
m=k；
sortArr(dr，m)；/*按距离大小从小到大排序形成排序表*/
do{
b=1;
dist=0；
k=h=0：
do{
k++；
i=dr[k]．p1；
j=dr[k]．p2；
if((r(i]．n＜=1)&&(r[j]．n＜=1)){/*度数不能大于2*/
if (2) {
/*若边(i，j)加入r后形成回路，则不能加入*/
(3);
h++；
dist+=dr[k]．x；
}else if (4) {
/*最后一边选入r成回路，则该边必须加入且得到解*/
selected(r，i，j)；
h++：
dist+=dr[k]．x;
}
}
}while((k !=n) && (h !=n))；
if(h==n){/*最后一边选入构成回路，完成输出结果*/
course(r，locus)；
}else(/*找不到解，调整dr，交换表中边长相同的边在表中的顺序，并将b置0*/
(5);
}
}while(!b);
}
(1)
