图的辅导炼习愿及解答 (一)单项选释题 1.在一个具有个顶点的有向图中，若所有顾点的出度数之和为s,则所有项点的入 度数之和为( . As B s-1 C s+l Dn 2在一个具有■个项点的有向图中，若所有项点的出度数之和为“，则所有顶点的度 数之和为( 。 As B5s-1 C stl D 2s 3在一个具有。个项点的无向图中，若具有©条边，则所有项点的度数之和为() C nte 02e 4在一个具有个顶点的无向完全图中，则所含的边数为( . A n B n(n-1) Cn(-1)/2 Dnn*1)/2 5在一个具有个顶点的有向完全图中，则所含的边数为( B n(n-1) Cn(m-1)/2 Dn(+1)/2 6在一个无权图中，若两顾点之间的路径长度为k,则该路径上的顶点数为( A k B ktl C k+2 D 2k 7.对于一个具有个顶点的无向连通图。它包含的连通分量的个数为()。 C n D n+l 8若一个图中包含有k个连通分量，若要按型深度优先搜索的方法访问所有顶点，则 必類调用( )次深度优先搜素调历的算法。 Ak B1 C k-1 D k+1 9.若要肥个顶点连接为一个连通图，则至少需要()条边。 B+1 C n-1 D 2n 10,在一个具有个项点和。条边的无向图的忽接矩阵中，表示边存在的元素（又移为 有效元素)的个数为(》. A n B nxe C e D 2xe 11,在一个具有n个顶点和。条边的有向图的邻接矩阵中，表示边存在的元素个数为 A n B nxe C e D 2xe 1
1 图的辅导练习题及解答 （一）单项选择题 1. 在一个具有 n 个顶点的有向图中，若所有顶点的出度数之和为 s，则所有顶点的入 度数之和为( )。 A s B s-1 C s+1 D n 2. 在一个具有 n 个顶点的有向图中，若所有顶点的出度数之和为 s，则所有顶点的度 数之和为( )。 A s B s-1 C s+1 D 2s 3. 在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的度数之和为( )。 A n B e C n+e D 2e 4. 在一个具有 n 个顶点的无向完全图中，则所含的边数为( )。 A n B n(n-1) C n(n-1)/2 D n(n+1)/2 5. 在一个具有 n 个顶点的有向完全图中，则所含的边数为( )。 A n B n(n-1) C n(n-1)/2 D n(n+1)/2 6. 在一个无权图中，若两顶点之间的路径长度为 k，则该路径上的顶点数为( )。 A k B k+1 C k+2 D 2k 7. 对于一个具有 n 个顶点的无向连通图，它包含的连通分量的个数为( )。 A 0 B 1 C n D n+1 8. 若一个图中包含有 k 个连通分量，若要按照深度优先搜索的方法访问所有顶点，则 必须调用( )次深度优先搜索遍历的算法。 A k B 1 C k-1 D k+1 9. 若要把 n 个顶点连接为一个连通图，则至少需要( )条边。 A n B n+1 C n-1 D 2n 10. 在一个具有 n 个顶点和 e 条边的无向图的邻接矩阵中，表示边存在的元素（又称为 有效元素）的个数为( )。 A n B ne C e D 2e 11. 在一个具有 n 个顶点和 e 条边的有向图的邻接矩阵中，表示边存在的元素个数为 ( )。 A n B ne C e D 2e
12.在一个具有n个项点和e条边的无向图的邻接表中，边结点的个数为()。 A n B nxe Ce D2×e 13,在一个具有个顶点和e条边的有向图的忽接表中，保存项点单链表的表头指针向 量的大小至少为( A n B 2n C e D 2e 14,在一个无权图的忽接表表示中，每个边结点至少包含《 )域。 AIB2 C3 D4 5.对于一个有向图，若一个项点的度为k1。出度为k2。则对应邻接表中该顶点单链 表中的边结点数为()。 A kl B k2 C kl-k2 D kl+k2 16.对于一个有向图，若一个顶点的度为k1。出度为k2。则对应逆邻接表中该项点单 性表中的边结点数为( 》。 A kl B k2 C kl-k2 D kl+k2 7.对于一个无向图，下面( )种说法是正确的， A每个项点的入度等于出度 B每个项点的度等于其入度与出度之和 C每个顶点的入度为D D每个顾点的出度为0 18,在一个有向图的忽接表中，每个暖点单桂表中结点的个数等于该顶点的( A出边数 B入边数 C度数 D度数减1 19.若一个图的边集为，B),A,C口，B,),C,月，D,D,D,F)》,则从顶点A开始对 该图进行深度优先搜索，得到的顶点序列可能为( A A.B.C.F.D.E B A.C.F.D.E.B C AB,D.C.F.E E A,B,D.F,E,C 0,若一个图的边集为{A,盼，，C,B,D),CF月，D,D,D,F)】,则从项点A开始对 该图进行广度优先搜索，得到的项点序列可能为( AA且，C,D.E,F B A,B.C.F,D.E C AB.D.C.E.F D A.C.B.F,D.E 21.若一个图的边集为{1,2)，(1,4>.2,5).3,1>，3,5>，，则从顶点1开始对 该图进行深度优先搜索，得到的顶点序列可能为()。 A1.2,5,4.3 B1.2,3,4,5 2
2 12. 在一个具有 n 个顶点和 e 条边的无向图的邻接表中，边结点的个数为( )。 A n B ne C e D 2e 13. 在一个具有 n 个顶点和 e 条边的有向图的邻接表中，保存顶点单链表的表头指针向 量的大小至少为( )。 A n B 2n C e D 2e 14. 在一个无权图的邻接表表示中，每个边结点至少包含( )域。 A 1 B 2 C 3 D 4 15. 对于一个有向图，若一个顶点的度为 k1，出度为 k2，则对应邻接表中该顶点单链 表中的边结点数为( )。 A k1 B k2 C k1-k2 D k1+k2 16. 对于一个有向图，若一个顶点的度为 k1，出度为 k2，则对应逆邻接表中该顶点单 链表中的边结点数为( )。 A k1 B k2 C k1-k2 D k1+k2 17. 对于一个无向图，下面( )种说法是正确的。 A 每个顶点的入度等于出度 B 每个顶点的度等于其入度与出度之和 C 每个顶点的入度为 0 D 每个顶点的出度为 0 18. 在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的( )。 A 出边数 B 入边数 C 度数 D 度数减 1 19．若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，则从顶点 A 开始对 该图进行深度优先搜索，得到的顶点序列可能为( )。 A A,B,C,F,D,E B A,C,F,D,E,B C A,B,D,C,F,E E A,B,D,F,E,C 20. 若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，则从顶点 A 开始对 该图进行广度优先搜索，得到的顶点序列可能为( )。 A A,B,C,D,E,F B A,B,C,F,D,E C A,B,D,C,E,F D A,C,B,F,D,E 21. 若一个图的边集为{,,,,,}，则从顶点 1 开始对 该图进行深度优先搜索，得到的顶点序列可能为( )。 A 1,2,5,4,3 B 1,2,3,4,5
C1.2,5.34 D14,3,25 22.若一个图的边集为{《1,2)，《1,4).2.5>.3,1>，3,5>.》，则从项点1开始对 该图进行深度优先搜索，得到的项点序列可能为()， A1,2,3.45 B1,2,4,35 C1.2,4.5.3 D1.4,2.5.3 3,由一个具有n个顶点的连通图生成的最小生成树中。具有( )条边。 A n B n-1 C n+l D 2xm 2L.已知一个无向图的边集为[0.1)3，(0,2到5，(0.3》6，(1,010.2.3)2(2.409， (3,4)8剧。则该图的最小生成树的权为()。 A43 B16C18 023 25.已知一个无向图的边集为[(0,1)3，(0.2)5，(0.3》6，(1,010，(2,3)2，(2.09， (3,4)8剧，则该图的最小生成树的边集为()， A10,1)3.0.2)50,3)6.(3.4)8 B{0,103.0,2)50,3)6,2.3)2到 C{2,3)20,2)5(3,408,0,3)6l D{2,3020,2)53,408,0103 5.已知一个有向图的边集为{a,b),(a,c>,《a,d》.b,d》,,e>,d,e>》,则由该图产 生的一种可能的拓扑序列为( A a.b.c.d.e B a.b,d.e,b C a.c,h,e,d D a.c,d,b.e (二)填空题 1,在一个图中，所有原点的度数之和等于所有边数的 倍 2.在一个具有n个顶点的无向完全图中，包含有 条边。在一个具有n个顶点 的有向完全图中，包含有条边。 3,己知一个连通图的边集为1(1,2)3(1,3)6，(1,4》8,23》4,2,5)10，(3,5)12
3 C 1,2,5,3,4 D 1,4,3,2,5 22. 若一个图的边集为{,,,,,}，则从顶点 1 开始对 该图进行深度优先搜索，得到的顶点序列可能为( )。 A 1,2,3,4,5 B 1,2,4,3,5 C 1,2,4,5,3 D 1,4,2,5,3 23. 由一个具有 n 个顶点的连通图生成的最小生成树中，具有( )条边。 A n B n-1 C n+1 D 2n 24. 已知一个无向图的边集为{(0,1)3, (0,2)5, (0,3)6, (1,4)10, (2,3)2, (2,4)9, (3,4)8}，则该图的最小生成树的权为( )。 A 43 B 16 C 18 D 23 25. 已知一个无向图的边集为{(0,1)3, (0,2)5, (0,3)6, (1,4)10, (2,3)2, (2,4)9, (3,4)8}，则该图的最小生成树的边集为( )。 A {(0,1)3,(0,2)5,(0,3)6,(3,4)8} B {(0,1)3,(0,2)5,(0,3)6,(2,3)2} C {(2,3)2,(0,2)5,(3,4)8,(0,3)6} D {(2,3)2,(0,2)5,(3,4)8,(0,1)3} 26. 已知一个有向图的边集为{,,,,,}，则由该图产 生的一种可能的拓扑序列为( )。 A a,b,c,d,e B a,b,d,e,b C a,c,b,e,d D a,c,d,b,e （二）填空题 1．在一个图中，所有顶点的度数之和等于所有边数的________倍。 2．在一个具有 n 个顶点的无向完全图中，包含有________条边，在一个具有 n 个顶点 的有向完全图中，包含有________条边。 3．已知一个连通图的边集为{(1,2)3, (1,3)6, (1,4)8, (2,3)4, (2,5)10, (3,5)12
(4,5)2},则度为3的厦点个数有个。 4.假定一个有向图的顶点集为a,b,c,d,e,f},边集为Ka,c>,,(c,D,(d,c> 《e,b),《e,D小，则出度为0的项点个数为一，入度为1的项点个数为 5在一个具有n个顶点的无向图中，要连通所有顶点则至少需要条边。 6。表示图的两种存销结构为 7.在一个连通图中存在着 个连通分量。 8,图中的一条路径长度为k,该路径所含的顶点数为 9若一个图的顶点集为{a,b,G,d,e.f1。边集为(a,b),(ac),6,c,(d,e},则该图 含有个违通分量， 10.一个图的边集为{0,1>3,0,250.3)5，(0.4>10，4,2.4>2.】，则从 顶点V。到顶点V:共有条简单路径。 11.一个图的边集为{0,1>3，(0,2>5,0,3)5，(0,4D10,1,2D4,2.D2,36>],则从 项点。到顶点V,的最复路径长度为一· 12,于一个具有■个顶点的图。若采用邻接矩阵表示，则矩降大小至少为 13.对于一个具有n个项点和e条边的有向图和无向图，在其对应的邻接表中，所含边 结点的个数分别为一和一 14,在有向图的忽接表和逆邻接表表示中，每个暖点邻接表分别链接着该顶点的所有 和 结点。 15.对于一个具有n个项点和0条边的无向图，当分别采用忽接矩阵和邻接表表示封， 求任一顶点度数的时间复柔性分别为和 16,假定一个图具有m个暖点和e条边，则采用邻接矩阵和邻接表表示时，其相应的空 间复杂性分别为和一· 17,对用邻接矩阵表示的图进行任一种着历时，其算法的时间复杂性为一·对用 邻接表表示的图进行任一种追历时，其算法的时间复杂性为。 18.一个图的边集为{a,c),(a,e),6,e),(c,d),(d.e)},从顶点a出发进行深度优先 搜索追历得到的项点序列为 ,从顺点a出发进行广度优先搜索遍历得到的顶点 序列为 19一个图的边集为a,c>,a,e》,c,D,dc>,e,b>,e,Dl,从顶点a出发进行深 度优先搜案据历得到的项点序列为 ,从原点出发进行广度优先搜索遍历得到 4
4 (4,5)2}，则度为 3 的顶点个数有________个。 4．假定一个有向图的顶点集为{a,b,c,d,e,f}，边集为{, , , , , }，则出度为 0 的顶点个数为________，入度为 1 的顶点个数为________。 5. 在一个具有 n 个顶点的无向图中，要连通所有顶点则至少需要________条边。 6．表示图的两种存储结构为__________和__________。 7．在一个连通图中存在着________个连通分量。 8．图中的一条路径长度为 k，该路径所含的顶点数为________。 9. 若一个图的顶点集为{a,b,c,d,e,f}，边集为{(a,b),(a,c),(b,c),(d,e)}，则该图 含有________个连通分量。 10．一个图的边集为{3,5,5,10,4,2,6>}，则从 顶点 V0 到顶点 V4 共有________条简单路径。 11．一个图的边集为{3,5,5,10,4,2,6>}，则从 顶点 V0 到顶点 V4 的最短路径长度为________。 12. 对于一个具有 n 个顶点的图，若采用邻接矩阵表示，则矩阵大小至少为 ________________。 13．对于一个具有 n 个顶点和 e 条边的有向图和无向图，在其对应的邻接表中，所含边 结点的个数分别为________和________。 14. 在有向图的邻接表和逆邻接表表示中，每个顶点邻接表分别链接着该顶点的所有 ________和________结点。 15．对于一个具有 n 个顶点和 e 条边的无向图，当分别采用邻接矩阵和邻接表表示时， 求任一顶点度数的时间复杂性分别为________和________。 16. 假定一个图具有 n 个顶点和 e 条边，则采用邻接矩阵和邻接表表示时，其相应的空 间复杂性分别为________和________。 17. 对用邻接矩阵表示的图进行任一种遍历时，其算法的时间复杂性为________，对用 邻接表表示的图进行任一种遍历时，其算法的时间复杂性为________。 18．一个图的边集为{(a,c),(a,e),(b,e),(c,d),(d,e)}，从顶点 a 出发进行深度优先 搜索遍历得到的顶点序列为____________，从顶点 a 出发进行广度优先搜索遍历得到的顶点 序列为____________。 19. 一个图的边集为{,,,,,}，从顶点 a 出发进行深 度优先搜索遍历得到的顶点序列为____________，从顶点 a 出发进行广度优先搜索遍历得到
的项点序列为 20.图的 优先瘦索遍历算法是一种递归算法，图的优先搜索海历算法 需要使用队列。 21,对于一个具有n个项点和。条边的连通图，其生成树中的顶点数和边数分别为 和 22,己知一个连通图的边集为{(1,2)3(1,3)6(1.408,2,3)4,2,5)10(35)12 (,5)2引，该图的最小生成树的权为一· 23。若一个连通图中每个边上的权值均不同，则得到的最小生成树是（唯一/ 不唯一)的。 24.根据图的存储结构速行某种次序的游历，得到的顶点序列是一《唯一/不唯 一)的. 25.己知一个连通图的边集为(1,2)3《1,3)6(1.408，(2,3)4,2,5)10(3,5)12 (4,5)}，若从顶点V,出发，按围普里鲜算法生成的最小生成树的过程中，依次得到的各条 边为 26.假定一个有向图的边集为a,c>,(a,>,《c,f),,》,对该图进行 拓补排序得到的顶点序列为 (三)应用思 1.对于一个无向图6一1()，假定采用邻接库表示，试分别写出从顶点出发按深度 优先瘦素遍历得到的顶点序列和按广度优先搜素历得到的顶点序列。 深度优先搜索序列： 广度优先艘索序判： 注：每一种序列都是唯一的，因为都是在存储结构上得到的 2对于一个有向图616)，假定采用邻接表表示，并且假定每个项点单链表中的边结 点是按出边忽接点序号从大到小的次序链接的，试分别写出从溪点。出发拔深度优先搜素 海历得到的厦点序列和按广度优先搜索遍历得到的顶点序列。 深度优先被索序列： 广度优先被索序列： 注：每一种序列都是难一的，。因为都是在存储结构上得到的
5 的顶点序列为____________。 20. 图的________优先搜索遍历算法是一种递归算法，图的________优先搜索遍历算法 需要使用队列。 21. 对于一个具有 n 个顶点和 e 条边的连通图，其生成树中的顶点数和边数分别为 ________和________。 22. 已知一个连通图的边集为{(1,2)3, (1,3)6, (1,4)8, (2,3)4, (2,5)10, (3,5)12, (4,5)2}，该图的最小生成树的权为________。 23．若一个连通图中每个边上的权值均不同，则得到的最小生成树是________（唯一/ 不唯一）的。 24．根据图的存储结构进行某种次序的遍历，得到的顶点序列是________（唯一/不唯 一）的。 25．已知一个连通图的边集为{(1,2)3, (1,3)6, (1,4)8, (2,3)4, (2,5)10, (3,5)12, (4,5)2}，若从顶点 V1 出发，按照普里姆算法生成的最小生成树的过程中，依次得到的各条 边为_______________。 26．假定一个有向图的边集为{,,,,,}，对该图进行 拓扑排序得到的顶点序列为________。 （三）应用题 1. 对于一个无向图 6-1(a)，假定采用邻接矩阵表示，试分别写出从顶点 v0 出发按深度 优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。 深度优先搜索序列： 广度优先搜索序列： 注：每一种序列都是唯一的，因为都是在存储结构上得到的。 2. 对于一个有向图 6-1(b)，假定采用邻接表表示，并且假定每个顶点单链表中的边结 点是按出边邻接点序号从大到小的次序链接的，试分别写出从顶点 v0 出发按深度优先搜索 遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。 深度优先搜索序列： 广度优先搜索序列： 注：每一种序列都是唯一的，因为都是在存储结构上得到的
0 2 (a) 图61 3.已知一个无向图的忽接矩阵如图62()所示，试写出从原点%出发分别进行深度优 先和广度优先瘦索遍历得到的项点序列， 深度优先整索序列： 广度优先被索序列： 4,己知一个无向图的忽接表如图62)所示，试写出从顶点出发分别进行深度优先 和广度优先搜索遍历得到的顶点序列。 深度优先被索序列： 广度优先搜索序列： 0123458 32 0001100 0 4 10000101 3 21001010 2 0 3101 0011 5G2日0☒ 01000 0 6 0011000 3+ 2 6010110 431 (a) 图6-2 5已知一个有向图的邻接矩阵如图6-☒()所示，试写出从项点出发分别进行深度优 先和广度优先搜索追历得到的项点序列。 深度优先艘索序列： 广度优先被索序列： 6,己知一个有向图的忽接表如图63)所示，试写出从项点出发分别进行深度优先
6 图 7-25 图 6-1 3．已知一个无向图的邻接矩阵如图 6-2(a)所示，试写出从顶点 v0 出发分别进行深度优 先和广度优先搜索遍历得到的顶点序列。 深度优先搜索序列： 广度优先搜索序列： 4．已知一个无向图的邻接表如图 6-2(b)所示，试写出从顶点 v0 出发分别进行深度优先 和广度优先搜索遍历得到的顶点序列。 深度优先搜索序列： 广度优先搜索序列： (a) (b) 图 6-2 5. 已知一个有向图的邻接矩阵如图 6-3(a)所示，试写出从顶点 v0 出发分别进行深度优 先和广度优先搜索遍历得到的顶点序列。 深度优先搜索序列： 广度优先搜索序列： 6．已知一个有向图的邻接表如图 6-3(b)所示，试写出从顶点 v0 出发分别进行深度优先
和广度优先搜索考历得到的项点序列， 深度优先被索序列： 广度优先搜索序列： 0123456 2日3□1 00111000 10000100 20000010 5 30010011 2□66 0000001 6A 0000001 60100000 A (a) 6) 图6-3 (四)算法设计题 1.编写一个算法，求出邻接矩库表示的无向图中序号为山的顶点的度数。 int degreel (GraphTpAk ga,int numh) 2.编写一个算法，求出邻接矩阵表示的有向图中序号为b的顶点的度数。 int degree2(GraphTpA&ga,int mumh) 3编写一个算法。求出邻接表表示的无向图中序号为u山的项点的度数。 int degree3(GraphTpl&gl,int nunb) 4.编写一个算法。求出邻接表表示的有向图中序号为中的溪点的度数。 int degree4(GraphTpL&gl,int nunb) 5。编写一个算法，求出一个用邻接知阵表示图的所有顶点的最大出度值。 int maxCutDegree(GraphTpk ga) 》
7 和广度优先搜索遍历得到的顶点序列。 深度优先搜索序列： 广度优先搜索序列： (a) (b) 图 6-3 （四）算法设计题 1. 编写一个算法，求出邻接矩阵表示的无向图中序号为 numb 的顶点的度数。 int degree1(GraphTpA& ga, int numb) 2. 编写一个算法，求出邻接矩阵表示的有向图中序号为 numb 的顶点的度数。 int degree2(GraphTpA& ga, int numb) 3. 编写一个算法，求出邻接表表示的无向图中序号为 numb 的顶点的度数。 int degree3(GraphTpL& gl, int numb) 4. 编写一个算法，求出邻接表表示的有向图中序号为 numb 的顶点的度数。 int degree4(GraphTpL& gl, int numb) 5．编写一个算法，求出一个用邻接矩阵表示图的所有顶点的最大出度值。 int maxOutDegree(GraphTpA& ga)
练习题参考解答 (一)单选择题 1.A 2.D 3.D 4.C 5.B 6.B 7.B 8.A 9.C 10.011.C 12.0 13.A14.B 15.B 18.C17.A 18.A 19.B 20.D21.A 22.C23.B 24.C 25.D 26.A (二)填空题 1.2 2n(m-1D/2m(n-1) 34 4.24 5.n-1 6邻接矩阵邻接表 7.1 8.k+1 9.3 10.4 11.7 12.nn 13.200 14,出边入边 15.0(nl0(e/m 16.0(n）0+e) 17.0m)0(ej 18.a,c,d,e,b a.c.e,d.b (答案不难一) 19.a.c.f,e,b,d a.c,e,f,b,d (答案不唯一) 20,深度广度 21,n-1 22.17 23.唯一 24.唯一 25.(1.3)3.2,3)4.1.408.4.5)2 26.a,e.b,d.c.f (答案不难一） (三)应用题 1.深度优先搜素序列：0,1,28,3,4,5,6,7.9 广度优先搜索序列：0,1,4,2,7,38,6,5,9 2深度优先搜素序列：0,4.7,5,836,1,2 广度优先搜素序列：04,3,1,7,56,2,8 3深度优先搜索序列：0,2,3,5,6.1.4 广度优先搜素序列：0,2,3,5,6.1.4 4深度优先授素序列：0,3,6,4,1,52 8
8 练习题参考解答 （一）单项选择题 1. A 2. D 3. D 4. C 5. B 6. B 7. B 8. A 9. C 10. D 11. C 12. D 13. A 14. B 15. B 16. C 17. A 18. A 19. B 20. D 21. A 22. C 23. B 24. C 25. D 26. A （二）填空题 1. 2 2. n(n-1)/2 n(n-1) 3. 4 4. 2 4 5. n-1 6. 邻接矩阵 邻接表 7. 1 8. k+1 9. 3 10. 4 11. 7 12. n n 13. 2e e 14. 出边 入边 15. O(n) O(e/n) 16. O(n2 ) O(n+e) 17. O(n2 ) O(e) 18. a,c,d,e,b a,c,e,d,b (答案不唯一) 19. a,c,f,e,b,d a,c,e,f,b,d (答案不唯一) 20. 深度 广度 21. n n-1 22. 17 23. 唯一 24. 唯一 25. (1,3)3,(2,3)4,(1,4)8,(4,5)2 26. a,e,b,d,c,f (答案不唯一) （三）应用题 1. 深度优先搜索序列：0,1,2,8,3,4,5,6,7,9 广度优先搜索序列：0,1,4,2,7,3,8,6,5,9 2. 深度优先搜索序列：0,4,7,5,8,3,6,1,2 广度优先搜索序列：0,4,3,1,7,5,6,2,8 3. 深度优先搜索序列：0,2,3,5,6,1,4 广度优先搜索序列：0,2,3,5,6,1,4 4. 深度优先搜索序列：0,3,6,4,1,5,2
广度优先搜素序列：0,3,26,5,4.1 5深度优先搜索序列：0,1,4,6,2,5,3 广度优先擅素序列：0,1,23,4,56 6深度优先搜素序列：0,2.56,1,4,3 广度优先搜索序列：0,2,3,1,5,64 (四)算法设计题 1. /根据无向图的邻接矩阵求出序号为u山的顶点的度数 int degreel(GraphTpl ga,int numb) int j.d-0: for(j=0:Kga.vexmum;j++) if (ga.ares [numb][j]:=0 ga.ares[numb][j]!=MAXINT) d+: return d: 1 2 /根据有向图的邻接矩阵求出序号为u山的顶点的度数 int degree2(GraphTpA话ga,nt nunb》 int i,j.d=0: /求出顶点u山的出度 for(j=0;Kga.vexmun:j++) if (ga.ares [numb][j]!-0 A&ga.ares[nunb][j]!"MAXINT) d+: /求出璞点u山的入度 for(i=0:i<ga.vexmum:1++) if (ga.ares[i][nurb]!-0 &ga.ares[i][nunb]!=MAXINT) d+: /返目项点ub的度 9
9 广度优先搜索序列：0,3,2,6,5,4,1 5. 深度优先搜索序列：0,1,4,6,2,5,3 广度优先搜索序列：0,1,2,3,4,5,6 6. 深度优先搜索序列：0,2,5,6,1,4,3 广度优先搜索序列：0,2,3,1,5,6,4 （四）算法设计题 1. //根据无向图的邻接矩阵求出序号为 numb 的顶点的度数 int degree1(GraphTpA& ga, int numb) { int j,d=0; for(j=0; j<ga.vexnum; j++) if(ga.ares[numb][j]!=0 && ga.ares[numb][j]!=MAXINT) d++; return d; } 2. //根据有向图的邻接矩阵求出序号为 numb 的顶点的度数 int degree2(GraphTpA& ga, int numb) { int i,j,d=0; //求出顶点 numb 的出度 for(j=0; j<ga.vexnum; j++) if(ga.ares[numb][j]!=0 && ga.ares[numb][j]!=MAXINT) d++; //求出顶点 numb 的入度 for(i=0; i<ga.vexnum; i++) if(ga.ares[i][numb]!=0 && ga.ares[i][numb]!=MAXINT) d++; //返回顶点 numb 的度
return d; 1 3 /根据无向图的邻接表求出序号为如h的顶点的度数 int degree3(GraphTpLA gl,int nunb) int d=0; AreNodeTp*p=gl.adjlist [numb]: while(p!"NULL){ d++: p=p->nextare: return d; 4 /根据有向图的邻接表求出序号为h的顶点的度数 int degree(GraphTpLA gl,int nurb) int d-0; /求出膜点动的出度 AreNodeTp*p=gl.adjlist [numb]: while(p!=NULL){ d+t; p=p->nextare: ∥求出顶点u山的入度 int i; for(i=0:i<gl.vexmun:1++) p=gl.adjlist[i]: while(p!-NULL) 0
10 return d; } 3. //根据无向图的邻接表求出序号为 numb 的顶点的度数 int degree3(GraphTpL& gl, int numb) { int d=0; AreNodeTp* p=gl.adjlist[numb]; while(p!=NULL) { d++; p=p->nextare; } return d; } 4. //根据有向图的邻接表求出序号为 numb 的顶点的度数 int degree4(GraphTpL& gl, int numb) { int d=0; //求出顶点 numb 的出度 AreNodeTp* p=gl.adjlist[numb]; while(p!=NULL) { d++; p=p->nextare; } //求出顶点 numb 的入度 int i; for(i=0; i<gl.vexnum; i++) { p=gl.adjlist[i]; while(p!=NULL) {