题目内容
（请给出正确答案）
设G是一个有n个顶点的有向图,从顶点i发出的边的最小费用记为min(i).
(1)证明图G的所有前缀为x[1,i]的旅行售货员问路的费用至少为:
式中,a(u,v)是边(u,v)的费用.
(2)利用上述结论设计一个高效的上界函数,重写旅行售货员问题的回溯法,并与主教材中的算法进行比较.
简答题官方参考答案
（由简答题聘请的专业题库老师提供的解答）
更多“设G是一个有n个顶点的有向图,从顶点i发出的边的最小费用记为min（i).（1)证明图G的所有前缀为x[1”相关的问题
(1)证明旅行售货员回路的费用不超过
.
(2)在旅行售货员问题的回溯法中,用上面的界作为bestc的初始值,重写该算法,并尽可能地简化代码.
A、V1,V2,V3,V4,V7,V6,V5
B、V1,V5,V4,V7,V6,V2,V3
C、V1,V5,V6,V4,V7,V2,V3
D、V1,V5,V4,V7,V6,V3,V2
(1)如果ADJ是图G=(V，E)的邻接矩阵，INC是关联矩阵，试说明在什么条件下将有ADJ=lNC×INCT-I，其中，INC是矩阵INC的转置矩阵，I是单位矩阵。两个nxn的矩阵的乘积C=A×B定义为
公式中的“∪”定义为按位加，“∩”定义为按位乘。
(2)设用邻接矩阵表示的图的定义如下。
试仿照上述定义，建立用关联矩阵表示的图的结构。
(3)以关联矩阵为存储结构，实现图的DFS的递归算法。
define MaxNum 50 //图的最大顶点数
typedef struct node{
int adjvex; //邻接点域
struct node*next; //链指针域
}EdgeNode; //边表结点结构描述
typedef struct{
char vertex; //顶点域
EdgeNode*firstedge;//边表头指针
}VertexNode; //顶点表结点结构描述
typedef struet{
VertexNode adjlist[MaxNum];//邻接表
int n,e; //图中当前的顶点数和边数
}ALGraph; //邻接表结构描述
下列算法输出图G的深度优先生成树(或森林)的边。阅读算法，并在空缺处填入合适的内容，使其成为一个完整的算法。
typedef enum{FALSE,TRUE}Boolean;
Boolean visited[MaxNurn];
void DFSForest(ALGraph*G){
int i;
for(i=0;i＜G—＞n;i++)visited[i]= (1) ;
for(i=0;i＜G—＞n;i++)if(!visited[i])DFSTree(G,i);
}
void DFSTree(ALGraph*G,int i){
EdgeNode*p;
visited[i]=TRUE;
p=G—＞adjlist[i].firstedge;
while(p!=NULL){
if(!visited[p—＞adjvex]){
printf("＜%c,%c",G—＞adjlist[i].vertex,
G—＞adjlist[p—＞adjvex].vertex);
(2) ;
}
(3) ;
}
}
A、O(n)
B、O(e)
C、O(n+e)
D、O(n2)
警告：系统检测到您的账号存在安全风险
为了保护您的账号安全，请在“简答题”公众号进行验证，点击“官网服务”-“账号验证”后输入验证码“”完成验证，验证成功后方可继续查看答案！
)
