你的位置：
首页
>
IT圈
>
中国农业大学_821数据结构_《数据结构》习题(7)
2024年6月2日发(作者：枚雪枫)
第7章 图及应用
一、问答题
1. 在一个图中，所有顶点的度数之和等于所有边数的多少倍？
2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的多少倍？
3. 对图7-1(a)和(b)所示的有向图，试回答：
(1) 每个顶点的入度和出度是多少；
(2) 给出它们的邻接矩阵、邻接表、逆邻接表和十字链表表示。
图7-1 有向图
4. 对图7-2所示的无向图，试回答：
(1) 给出邻接矩阵和邻接表的表示；
(2) 根据邻接表，给出从顶点v
1
作深度优先和广度优先遍历图中顶点的次序。
图7-2 无向图
5. 对图7-3(a)和(b)所示的无向图，画出其深度优先生成树和广度优先生成树。
图7-3 无向图
6. 对图7-4所示的带权无向图：
(1) 按照普里姆算法，从顶点v
1
出发生成最小生成树，按生成次序写出各条边；
(2) 按照克鲁斯卡尔算法，生成最小生成树，按生成次序写出各条边；
(3) 画出其最小生成树，并求出它的权值。
图7-4 带权无向图
7. 对图7-5所示的带权有向图，用迪杰斯特拉（Dijkstra）算法，试回答：
(1) 带权邻接矩阵arcs是什么？
2024年6月2日发(作者：枚雪枫)
第7章 图及应用
一、问答题
1. 在一个图中，所有顶点的度数之和等于所有边数的多少倍？
2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的多少倍？
3. 对图7-1(a)和(b)所示的有向图，试回答：
(1) 每个顶点的入度和出度是多少；
(2) 给出它们的邻接矩阵、邻接表、逆邻接表和十字链表表示。
图7-1 有向图
4. 对图7-2所示的无向图，试回答：
(1) 给出邻接矩阵和邻接表的表示；
(2) 根据邻接表，给出从顶点v
1
作深度优先和广度优先遍历图中顶点的次序。
图7-2 无向图
5. 对图7-3(a)和(b)所示的无向图，画出其深度优先生成树和广度优先生成树。
图7-3 无向图
6. 对图7-4所示的带权无向图：
(1) 按照普里姆算法，从顶点v
1
出发生成最小生成树，按生成次序写出各条边；
(2) 按照克鲁斯卡尔算法，生成最小生成树，按生成次序写出各条边；
(3) 画出其最小生成树，并求出它的权值。
图7-4 带权无向图
7. 对图7-5所示的带权有向图，用迪杰斯特拉（Dijkstra）算法，试回答：
(1) 带权邻接矩阵arcs是什么？