没有合适的资源?快使用搜索试试~ 我知道了~
第8章习题(图).doc
需积分: 9 0 下载量 100 浏览量
2021-06-27
14:50:35
上传
评论
收藏 263KB DOC 举报
温馨提示
试读
16页
图
资源推荐
资源详情
资源评论
第 8 章 图
第8章 图
8-1 画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。试证明在n个顶点的无向完全图
中,边的条数为n(n-1)/2。
【解答】
【证明】
在有n个顶点的无向完全图中,每一个顶点都有一条边与其它某一顶点相连,所以每一个顶点有n-1条
边与其他n-1个顶点相连,总计n个顶点有n(n-1)条边。但在无向图中,顶点i到顶点j与顶点j到顶点i是同一
条边,所以总共有n(n-1)/2条边。
8-2 右边的有向图是强连通的吗?请列出所有的简单路径。
【解答】
判断一个有向图是否强连通,要看从任一顶点出发是否能够回到该顶 点
右面的有向图做不到这一点,它不是强连通的有向图。各个顶点自成强连通 分
量。
所谓简单路径是指该路径上没有重复的顶点。
从顶点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) 邻接矩阵
96
1 个顶点的
无向完全图
2 个顶点的
无向完全图
3 个顶点的
无向完全图
4 个顶点的
无向完全图
5 个顶点的
无向完全图
A
B
C
D
E
F
A
B
C
D
E
F
第 8 章 图
(2) 邻接表
(3) 邻接多重表(十字链表)
8-4 用邻接矩阵表示图时,若图中有1000个顶点,1000条边,则形成的邻接矩阵有多少矩阵元素?有多少
非零元素?是否稀疏矩阵?
【解答】
一个图中有1000个顶点,其邻接矩阵中的矩阵元素有1000
2
= 1000000个。它有1000个非零元素(对于
有向图)或2000个非零元素(对于无向图),因此是稀疏矩阵。
8-5 用邻接矩阵表示图时,矩阵元素的个数与顶点个数是否相关?与边的条数是否相关?
【解答】
用邻接矩阵表示图,矩阵元素的个数是顶点个数的平方,与边的条数无关。矩阵中非零元素的个数
与边的条数有关。
8-6 有n个顶点的无向连通图至少有多少条边?有n个顶点的有向强连通图至少有多少条边?试举例说明。
【解答】
n个顶点的无向连通图至少有n-1条边,n个顶点的有向强连通图至少有n条边。例如:
97
0 A
1 B
2 C
3 D
4 E
5 F
1
0 A
1 B
2 C
3 D
4 E
5 F
3
2 4
5
1
4
4
0 3
1
0
1 3 5
2
∧
∧
∧
∧
∧
∧
∧
∧
∧
∧
∧
∧
(出边表)
(入边表)
0 A
1 B
2 C
3 D
4 E
5 F
data fin fout
i j ilink jlink
0 1 (A, B)
0 3 (A, D)
1 2 (B, C)
1 4 (B, E)
2 5 (C, F)
3 1 (D, B)
3 4 (D, E)
5 4 (F, E)
∧
∧
∧
∧
∧
∧
∧
∧
∧
∧
①
② ③
④
⑤
或
①
② ③
④
⑤
①
② ③
④
⑤
①
② ③
④
⑤
第 8 章 图
特例情况是当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<int> * t ) 其中,指针t指向生成森林上具有图顶
点v信息的根结点。(提示:在继续按深度方向从根v的某一未访问过的邻接顶点w向下遍历之前,建立子
女结点。但需要判断是作为根的第一个子女还是作为其子女的右兄弟链入生成树。)
【解答】
为建立生成森林,需要先给出建立生成树的算法,然后再在遍历图的过程中,通过一次次地调用这
个算法,以建立生成森林。
te mplate<Type> void Graph<Type> :: DFS_Tree ( const int v, int visited [ ], TreeNode<Type> *t ) {
//从图的顶点v出发, 深度优先遍历图, 建立以t (已在上层算法中建立)为根的生成树。
Visited[v] = 1; int first = 1; TreeNode<Type> * p, * q;
int w = GetFirstNeighbor ( v ); //取第一个邻接顶点
while ( w != -1 ) { //若邻接顶点存在
if ( vosited[w] == 0 ) { //且该邻接结点未访问过
p = new TreeNode<Type> ( GetValue (w) ); //建立新的生成树结点
if ( first == 1 ) //若根*t还未链入任一子女
98
第 8 章 图
{ t->setFirstChild ( p ); first = 0; } //新结点*p成为根*t的第一个子女
else q->setNextSibling ( p ); //否则新结点*p成为*q的下一个兄弟
q = p; //指针q总指示兄弟链最后一个结点
DFS_Tree ( w, visited, q ); //从*q向下建立子树
}
w = GetNextNeighbor ( v, w ); //取顶点v排在邻接顶点w的下一个邻接顶点
}
}
下一个算法用于建立以左子女-右兄弟链表为存储表示的生成森林。
template<Type> void Graph<Type> :: DFS_Forest ( Tree<Type> & T ) {
//从图的顶点v出发, 深度优先遍历图, 建立以左子女-右兄弟链表表示的生成森林T。
T.root = NULL; int n = NumberOfVertices ( ); //顶点个数
TreeNode<Type> * p, * q;
int * visited = new int [ n ]; //建立访问标记数组
for ( int v = 0; v < n; v++ ) visited[v] = 0;
for ( v = 0; v < n; v++ ) //逐个顶点检测
if ( visited[v] == 0 ) { //若尚未访问过
p = new TreeNode<Type> ( GetValue ( v ) ); //建立新结点*p
if ( T.root == NULL ) T.root = p; //原来是空的生成森林, 新结点成为根
else q-> setNextSibling ( p ); //否则新结点*p成为*q的下一个兄弟
q = p;
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
⑩ ① ②
③ ④ ⑤
⑥
⑦
⑧
⑨
剩余15页未读,继续阅读
资源评论
lhh5356
- 粉丝: 0
- 资源: 40
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功