第7章 图
一、单选题 01-10 CBBCC BAACB 11-20 DAADB ACACB 21-30 DCDAD BCBAD 二、填空题 01、入度
2
02、n-1 04、出度 07、有向
03、邻接矩阵、邻接表 05、n
08、将邻接矩阵的第i行全部置0 10、第i行第j列的元素是否为0 15、出度 18、错误
04、深度、广度
06、O(n)、O(n+e) 11、O(n)、O(elog2e) 13、递增 16、n
三、简答题
19、2(n-1)
2
09、矩阵第i列非0元素之和
14、0 17、0 20、存在
12、克鲁斯卡尔(Kruskal)、普里姆(Prim)
01、3个，分别是：a,bce,dfg 02、
03、普里姆算法产生边的序列：(1,3),(3,4),(4,6),(6,5),(5,2)
克鲁斯卡尔算法产生边的序列：(4,6),(1,3),(4,3),(6,5),(2,5) 04、v1,v2,v3,v4
v1,v3,v2,v4 v2,v1,v3,v4
05、(1) 每个顶点的入/出度 (2) 邻接矩阵
(3) 邻接表 (4) 逆邻接表
06、(1)邻接矩阵为：
V Vex lowcost Vex lowcost Vex lowcost Vex lowcost Vex lowcost Vex lowcost Vex lowcost Vex lowcost b a 4 a 4 0 c a 3 0 d a e a f a g a h a ∞ c 5 c 5 d 4 0 U {a} V-U {b,c,d,e,f,g,h} ∞ ∞ c 5 a ∞ b 9 d 7 ∞ ∞ a a {a,c} {b,d,e,f,g,h} ∞ ∞ a a 0 c 5 {a,c,b} {d,e,f,g,h} ∞ ∞ d 6 d 6 g 2 0 0 d 5 d 5 0 0 0 0 {a,c,b,d} {e,f,g,h} 0 0 0 d 7 {a,c,b,d,h} {e,f,g} 0 0 0 d 7 0 {a,c,b,d,h,g} {f,e} 0 0 0 f 3 0 {a,c,b,d,h,g,f} {e} 0 0 0 0 0 0 0 {a,c,b,d,h,g,f,e} { } 最小生成树
07、邻接表为：
fg(2)?ac(3)?fe(3)?ab(4)?dh(4)?bd(5)?dg(5) 08、
09、
a?c：2(a,c) a?f：6(a,c,f) a?e：10(a,c,e) a?d：11(a,c,f,d) a?g：14(a,c,f,d,g) a?b：15(a,b)
10、和上题类似，求解过程略。
11、
1，2，3，6，5，4 1，3，2，6，5，4 1，3，6，2，5，4 12、
FALSE //初始化为未访问
DSFTree(G, p->adjvex) //从相邻结点往下继续深度搜索 p=p->next //下一个未访问的相邻结点
四、算法设计题
01、编写编历算法，完成对图的深度优先搜索和广度优先搜索。 深度优先搜索：课本P169算法7.4和算法7.5
广度优先搜索：课本P170算法7.6
02、编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。 解：Status Build_AdjList(ALGraph &G) //输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表 { InitALGraph(G); scanf(\
if(v<0) return ERROR; //顶点数不能为负 G.vexnum=v; scanf(\
if(a<0) return ERROR; //边数不能为负 G.arcnum=a; for(m=0;m G.vertices[m].data=getchar(); //输入各顶点的符号 for(m=1;m<=a;m++) { t=getchar();h=getchar(); //t为弧尾,h为弧头 if((i=LocateVex(G,t))<0) return ERROR; if((j=LocateVex(G,h))<0) return ERROR; //顶点未找到 p=(ArcNode*)malloc(sizeof(ArcNode)); if(!G.vertices.[i].firstarc) G.vertices[i].firstarc=p; else { for(q=G.vertices[i].firstarc;q->nextarc;q=q->nextarc); q->nextarc=p; } p->adjvex=j;p->nextarc=NULL; }//while return OK; }//Build_AdjList 03、试在邻接矩阵存储结构上实现图的基本操作：DeleteArc(G,v,w) ，即删除一条边的操作。(如果要删除所有从第i个顶点出发的边呢？ 提示： 将邻接矩阵的第i行全部置0 ) 解：//本题中的图G均为有向无权图。 Status Delete_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上删除边(v,w) { if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; if(G.arcs[i][j].adj) { G.arcs[i][j].adj=0; G.arcnum--; } return OK; }//Delete_Arc
