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是什么？