第8章 图
第8章 图
8-1 画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。试证明在n个顶点的无向完全图中，边的条数为n(n-1)/2。 【解答】 【证明】
1个顶点的 无向完全图
2个顶点的 无向完全图
3个顶点的 无向完全图 4个顶点的 无向完全图
5个顶点的 无向完全图
在有n个顶点的无向完全图中，每一个顶点都有一条边与其它某一顶点相连，所以每一个顶点有n-1
条边与其他n-1个顶点相连，总计n个顶点有n(n-1)条边。但在无向图中，顶点i到顶点j与顶点j到顶点i是同一条边，所以总共有n(n-1)/2条边。
8-2 右边的有向图是强连通的吗？请列出所有的简单路径。 【解答】
判断一个有向图是否强连通，要看从任一顶点出发是否能够回到该顶
B C E F A D 点。右面的有向图做不到这一点，它不是强连通的有向图。各个顶点自成强连通分量。
所谓简单路径是指该路径上没有重复的顶点。
从顶点A出发，到其他的各个顶点的简单路径有A→B，A→D→B，A→B→C，A→D→B→C，A→D，A→B→E，A→D→E，A→D→B→E，A→B→C→F→E，A→D→B→C→F→E，A→B→C→F，A→D→B→C→F。
从顶点B出发，到其他各个顶点的简单路径有B→C，B→C→F，B→E，B→C→F→E。 从顶点C出发，到其他各个顶点的简单路径有C→F，C→F→E。
从顶点D出发，到其他各个顶点的简单路径有D→B，D→B→C，D→B→C→F，D→E，D→B→E，D→B→C→F→E。
从顶点E出发，到其他各个顶点的简单路径无。 从顶点F出发，到其他各个顶点的简单路径有F→E。
8-3 给出右图的邻接矩阵、邻接表和邻接多重表表示。 【解答】
(1) 邻接矩阵
?0?0??0Edge???0?0???01001000100001000000101010?0??1??0?0??0??A B C D E F 96
第8章 图
(2) 邻接表
8-4 用邻接矩阵表示图时，若图中有1000个顶点，1000条边，则形成的邻接矩阵有多少矩阵元素？有多少非零元素？是否稀疏矩阵？ 【解答】
一个图中有1000个顶点，其邻接矩阵中的矩阵元素有10002 = 1000000个。它有1000个非零元素（对于有向图）或2000个非零元素（对于无向图），因此是稀疏矩阵。
8-5 用邻接矩阵表示图时，矩阵元素的个数与顶点个数是否相关？与边的条数是否相关？ 【解答】
用邻接矩阵表示图，矩阵元素的个数是顶点个数的平方，与边的条数无关。矩阵中非零元素的个数与边的条数有关。
8-6 有n个顶点的无向连通图至少有多少条边？有n个顶点的有向强连通图至少有多少条边？试举例说明。 【解答】
0 1 2 3 4 （入边表）
0 1 2 3 4 5
A B C D E F ∧ 0 1 ∧ 0 ∧ 1 2 ∧ 3 5 ∧ 3 ∧ （出边表）
0 1 2 3 4 5 A B C D E F ∧ 4 ∧ 1 2 5 ∧ 1 4 ∧ 3 ∧ 4 ∧ (3) 邻接多重表（十字链表）
data fin fout A B C D E ∧ 1 4 ∧ (B, E) 2 5 ∧ ∧ (C, F) 3 1 (D, B) 3 4 (D, E) 5 4 ∧ ∧ (F, E)
∧ i j ilink jlink 0 1 (A, B) 0 3 ∧ ∧ (A, D) 1 2 ∧ (B, C)
5 F 97
第8章 图
n个顶点的无向连通图至少有n-1条边，n个顶点的有向强连通图至少有n条边。例如：
特例情况是当n = 1时，此时至少有0条边。
8-7对于有n个顶点的无向图，采用邻接矩阵表示，如何判断以下问题： 图中有多少条边？任意两个顶点i和j之间是否有边相连？任意一个顶点的度是多少？ 【解答】
用邻接矩阵表示无向图时，因为是对称矩阵，对矩阵的上三角部分或下三角部分检测一遍，统计其中的非零元素个数，就是图中的边数。如果邻接矩阵中A[i][j] 不为零，说明顶点i与顶点j之间有边相连。此外统计矩阵第i行或第i列的非零元素个数，就可得到顶点i的度数。
8-8对于如右图所示的有向图，试写出：
(1) 从顶点①出发进行深度优先搜索所得到的深度优先生成树； (2) 从顶点②出发进行广度优先搜索所得到的广度优先生成树；
② ④ ① ③ ⑤
【解答】
② ④
② ④ (1) 以顶点①为根的深度优先生成树（不唯一）：② ③ ④ ⑤ ⑥
①
③
⑤
或
② ④ ①
③ ⑤
(2) 以顶点②为根的广度优先生成树：
① ③
⑤
8-9 试扩充深度优先搜索算法，在遍历图的过程中建立生成森林的左子女-右兄弟链表。算法的首部为
void Graph::DFS ( const int v, int visited [ ], TreeNode
为建立生成森林，需要先给出建立生成树的算法，然后再在遍历图的过程中，通过一次次地调用这
te mplate
//取第一个邻接顶点 //若邻接顶点存在
个算法，以建立生成森林。
98
第8章 图
} }
if ( vosited[w] == 0 ) {
//且该邻接结点未访问过
p = new TreeNode
//建立新的生成树结点 //若根*t还未链入任一子女 //新结点*p成为根*t的第一个子女 //否则新结点*p成为*q的下一个兄弟 //指针q总指示兄弟链最后一个结点 //从*q向下建立子树
{ t->setFirstChild ( p ); first = 0; }
else q->setNextSibling ( p ); q = p;
DFS_Tree ( w, visited, q ); }
w = GetNextNeighbor ( v, w );
//取顶点v排在邻接顶点w的下一个邻接顶点
下一个算法用于建立以左子女-右兄弟链表为存储表示的生成森林。
template
//从图的顶点v出发, 深度优先遍历图, 建立以左子女-右兄弟链表表示的生成森林T。 T.root = NULL; int n = NumberOfVertices ( ); TreeNode
//建立访问标记数组
//顶点个数
for ( int v = 0; v < n; v++ ) visited[v] = 0; for ( v = 0; v < n; v++ ) }
if ( visited[v] == 0 ) {
//逐个顶点检测 //若尚未访问过 //建立新结点*p
//原来是空的生成森林, 新结点成为根 //否则新结点*p成为*q的下一个兄弟
p = new TreeNode
DFS_Tree ( v, visited, p ); }
//建立以*p为根的生成树
8-10 用邻接表表示图时，顶点个数设为n，边的条数设为e，在邻接表上执行有关图的遍历操作时，时间代价是O(n*e)？还是O(n+e)？或者是O(max(n,e))？ 【解答】
在邻接表上执行图的遍历操作时，需要对邻接表中所有的边链表中的结点访问一次，还需要对所有的顶点访问一次，所以时间代价是O(n+e)。
8-11 右图是一个连通图，请画出
(1) 以顶点①为根的深度优先生成树； (2) 如果有关节点，请找出所有的关节点。
(3) 如果想把该连通图变成重连通图，至少在图中加几条边？ 如何加？ 【解答】
⑨ ① ③ ⑧ ⑦ ②
⑥ ⑤
⑩ ④
(1) 以顶点①为根的深度优先生成树：
99
第8章 图
⑩ ③ ① ⑨ ⑧ ⑦ ②
⑥ ⑤
④
(2) 关节点为 ①,②,③,⑦,⑧
(3) 至少加四条边 (1, 10), (3, 4), (4, 5), (5, 6)。从③的子孙结点⑩到③的祖先结点①引一条边，从②
的子孙结点④到根①的另一分支③引一条边，并将⑦的子孙结点⑤、⑥与结点④连结起来，可使其变为重连通图。
⑩ ⑨ ① ③ ⑧ ② ④ ⑦
⑥ ⑤
8-12试证明在一个有n个顶点的完全图中，生成树的数目至少有2n-1-1。 【证明】略
8-13 编写一个完整的程序，首先定义堆和并查集的结构类型和相关操作，再定义Kruskal求连通网络的最小生成树算法的实现。并以右图为例，写出求解过程中堆、并查集和最小生成树的变化。 【解答】
求解过程的第一步是对所有的边，按其权值大小建堆：
②
11
7
① 7
10 9
③ 5
⑤
8
6
④ ⑥
1 2 7 1 3 11 2 3 10 1 2 7 2 4 9 1 3 11 加(2, 4)
3 4 5 1 2 7 1 3 11 2 4 9 加(3, 4)
2 3 10 2 3 10 加(1, 2), (1, 3),
(2,3)
3 4 5 1 2 7 1 3 11 2 4 9 3 5 7 2 3 10 1 2 7 3 4 5 3 5 7 2 3 10 3 6 8 1 3 11 2 4 9 加(3, 5) 加(3, 6)
3 4 5 5 6 6 1 2 7 1 3 11 100
3 5 7 2 3 10 3 6 8 加(5, 6)
2 4 9
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构第八章作业提示在线全文阅读。
相关推荐：