知识点

1.基本概念

注意：线性表可以是空表，树可以是空树，图不可以是空图，图可以没有边，但是至少要有一个顶点。

图(Graph)：图 G 是由两个集合 V(G)和 E(G)组成的,记为：G=(V,E)。
有向图：带箭头，有指定方向；无向图：没有箭头

子图：若有两个图G=(V,E),G1=(V1,E2)，若V1是V的子集且E2是E的子集，称G1是G的子图。

稀疏图和稠密图：有很少条边或弧（如e<nlog2n）的图称为稀疏图，反之称为稠密图。
完全图：

• 无向图中任意两点之间都存在边，称为无向完全图；无向完全图具有 n(n-1)/2 条边
• 有向图中任意两点之间都存在方向向反的两条弧，称为有向完全图；有向完全图具有 n(n-1)条弧

度、入度和出度：顶点的度为以该顶点为一个端点的边的数目

• 对于无向图，顶点的边数为度，度数之和是顶点边数的两倍
• 对于有向图，入度是以顶点为终点（即箭头所指方向），出度是以顶点为起点 （即箭尾巴所指方向）
• 有向图的全部顶点入度之和等于出度之和且等于边数。顶点的度等于入度与出度之和
• 注意：入度与出度是针对有向图来说的

2.图的存储结构

邻接矩阵

用一维数组存储图顶点信息，二维数组存储图中边信息。
无向图/有向图（不带权值）：接通标1，相反标0。
适合表示稠密图
n个顶点的连通图用邻接矩阵表示时，该矩阵至少有 2(n-1) 个非零元素

网（带权值）：∞表示无法到达；权值代表可以到达

邻接表

对图中的每个顶点建立一个单链表，存储该顶点所有邻接顶点及其相关信息。每一个单链表设有一个表头结点；适合表示稀疏图

---

逆邻接表：以顶点为终点，与邻接表相反。

十字链表

概念：是有向图的另一种链式存储结构，可以看成将有向图的邻接表和逆邻接表结合起来得到的一种链表。

---

---

	入度	出度
V1	2 0 ，3 0	0 1 ，0 2
V2	0 1 ，3 1	^
V3	3 2 ，0 2	20 ，2 3
V4	2 3	3 0 ，3 1 ，3 2

邻接多重链表

概念：是无向图的另一种链式存储结构。

3.图的遍历

通常有两条遍历图的路径：深度优先搜索和广度优先搜索

深度优先搜索遍历（DFS）

1. 从一个点开始，一直往下访问直到没有未访问元素，然后回退一步继续访问，直到全部访问。
2. 深度优先遍历通常借助栈来实现算法
3. 深度优先遍历类似于二叉树的先序遍历
4. [探究到底，一个接一个，不唯一]

---

广度优先搜索遍历（BFS）

• 广度优先搜索类似于树的层次遍历，是按照一种由近及远的方式访问图的顶点。在进行广度优先搜索时需要使用队列存储顶点信息。
• 广度优先遍历通常借助队列来实现算法

---

---

图的遍历生成树

深度优先生成树：所有顶点加上标有实箭头的边，构成一棵以v₁为根的树

广度优先生成树：所有顶点加上标有实箭头的边，构成一棵以v₁为根的树

---

4.图的应用

4.1最小生成树

普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法是两个利用MST性质构造最小生成树的算法

普里姆算法（Prim）

普利姆算法从始至终始终是一整棵树
算法的时间复杂度为O(n^2^)，与图中边数无关，该算法适合于稠密图。

---

克鲁斯卡尔算法(Kruskal)

按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路。
具体做法：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止。
时间复杂度为：O（elog₂e） 边数e越大，所耗费时间越长，则适合稀疏图

4.2最短路径

最短路径问题：如果从有向图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小

迪杰斯拉(Dijkstra)算法

弗洛伊德算法

省略

4.3拓扑排序

拓扑排序：（不唯一）找入度为零的点
条件：在有向无环情况下的图

1. 在有向图中选一个无前驱的顶点且输出它。
2. 从图中删除该顶点和所有以它为尾的弧。
3. 重复1和2，直至不存在无前驱的顶点。
4. 若此时输出的顶点数小于有向图中的顶点数，则说明有向图中存在环，否则输出的顶点序列即一个拓扑序列。

4.4关键路径

练习题

一、选择题

1.题目：在一个图中，所有顶点的度数之和等于图的边数的（　）倍。

A. 1/2
B. 1
C. 2
D. 4

2.题目：具有n个顶点的有向图最多有（　）条边。

A. n
B. n(n-1)
C. n(n+1)
D. n²

3.题目：G是一个非连通无向图，共有28条边，则该图至少有（　）个顶点。

A. 7
B. 8
C. 9
D. 10

4.题目：在下列有关图的说法中正确的是(　)。

A. 在连通图中，顶点可以没有任何前驱和后继。
B. 具有 n 个顶点的无向图最多有 n(n-1)条边，最少有 n-1 条边。
C. 在无向图中，边的条数是结点度数之和。
D. 在有向图中，各顶点的入度之和等于各顶点的出度之和。

5.题目：在无向图中定义顶点的度为与它相关联的(　)的数目。

A. 顶点
B. 边
C. 权
D. 权值

6.题目：具有 n 个顶点且每一对不同的顶点之间都有一条边的无向图被称为(　)。

A. 无向完全图
B. 无向连通图
C. 无向强连通图
D. 无向树图

7.题目：一个有 n 个顶点的无向图最多有(　)条边。

A. n
B. n(n-1)
C. n(n-1)/2
D. 2n

8.题目：在一个具有 n 个顶点的有向图中，若所有顶点的出度之和为 s，则所有顶点的入度之和为(　)。

A. s
B. s-1
C. s+1
D. n

9.题目：有8个结点的无向连通图最少有（　）条边。

A. 5
B. 6
C. 7
D. 8

10.题目：n个顶点的连通图用邻接矩阵表示时，该矩阵至少有（　）个非零元素。

A. n
B. 2(n-1)
C. n/2
D. n_²

11.题目：带权有向图G用邻接矩阵 A 存储，则顶点 i 的入度等于A中(　)。

A. 第 i 行非∞的元素之和
B. 第 i 列非∞的元素之和
C. 第i行非∞且非0的元素个数
D. 第i列非∞且非0的元素个数

12.题目：对于一个具有 n 个顶点和 e 条边的无向图，若采用邻接矩阵表示，则该矩阵大小是( )。

A. n
B. (n-1)^2
C. n-1
D. n^2

13.题目：对于一个具有 n 个顶点和 e 条边的无向图，若采用邻接矩阵表示，矩阵中的非零元素个数是(　)。

A. e
B. 2e
C. e^2
D. n^2

14.题目：无向图的邻接矩阵是一个(　)。

A. 对称矩阵
B. 零矩阵
C. 上三角矩阵
D. 对角矩阵

15.题目：已知图的邻接矩阵如图1所示，则从顶点v0出发按深度优先遍历的结果是（　）。

A. 0 2 4 3 1 5 6
B. 0 1 3 6 5 4 2
C. 0 1 3 4 2 5 6
D. 0 3 6 1 5 4 2

16.题目：用邻接表表示图进行深度优先遍历时，通常借助（　）来实现算法。

A. 栈
B. 队列
C. 树
D. 图

17.题目：若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（　）图。

A. 非连通
B. 连通
C. 强连通
D. 有向

18.题目：已知图的邻接表如图2所示，则从顶点v0出发按深度优先遍历的结果是（　）。

A. 0 1 3 2
B. 0 2 3 1
C. 0 3 2 1
D. 0 1 2 3

19.题目：用邻接表表示图进行广度优先遍历时，通常借助（　）来实现算法。

A. 栈
B. 队列
C. 树
D. 图

20.题目：已知图的邻接表如图2所示，则从顶点v0出发按广度优先遍历的结果是（　）。

A. 0 1 3 2
B. 0 2 3 1
C. 0 3 2 1
D. 0 1 2 3

二、填空题

1.n个顶点的连通图至少有（　　　）条边。

2.在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i]等于（　　　）。

3.已知一个图的邻接矩阵表示，计算第i个结点的入度的方法是计算第i（　）数组元素中1的个数。

4.遍历图的基本方法有深度优先搜索和广度优先搜索，其中（　　　）优先搜索是一个递归过程。

5.进行深度优先遍历时需要使用（1）作为辅助数据结构，广度优先遍历时需要使用（2）作为辅助数据结构。

三、判断题

1.图的连通分量是无向图的极小连通子图。

A. 对
B. 错

2.图的深度优先搜索序列和广度优先搜索序列不是唯一的。

A. 对
B. 错

四、简答题

1.已知如图所示的有向图，请给出该图的:①每个顶点的入/出度；②邻接矩阵；③给出邻接表，通过邻接表如何得到顶点的出度？④给出逆邻接表，通过逆邻接表如何得到顶点的入度？

2.请对下列无向带权图：①给出邻接矩阵②d、f顶点的度

3.根据邻接矩阵回答：①邻接矩阵表示的图的类型②根据邻接矩阵画出图G

4.给定下列网G，给出网G的邻接矩阵。

答案解析

一、单选题解析

1.答案： C
解析： 在图中，每条边连接两个顶点，为每个顶点的度数贡献1。因此，所有顶点的度数之和是边数的两倍。

2.答案： B
解析： 在有向图中，每个顶点最多可以发出(n-1)条边指向其他顶点。因此，n个顶点的有向图最多有n(n-1)条边。

3.答案： C
解析： 8个顶点的完全无向图最多有8*7/2=28条边。要构成一个非连通图（至少有两个连通分量），顶点数必须多于8个，因此至少需要9个顶点。

4.答案： D
解析： 在有向图中，每条边有一个起点（贡献一个出度）和一个终点（贡献一个入度），因此所有顶点的入度之和等于所有顶点的出度之和。

5.答案： B
解析： 顶点的度定义为与该顶点相关联的边的数目。

6.答案： A
解析： 任意两个不同顶点之间都存在一条边的无向图称为无向完全图。

7.答案： C
解析： 在无向完全图中，任意两个顶点之间有一条边，总边数为组合数C(n,2) = n(n-1)/2。

8.答案： A
解析： 理由同第4题，有向图中所有顶点的出度之和等于所有顶点的入度之和。

9.答案： C
解析： n个顶点的无向连通图至少需要构成一棵生成树，其边数为n-1。8个顶点至少需要7条边。

10.答案： B
解析： n个顶点的连通图至少有(n-1)条边。在邻接矩阵中，每条无向边会对称地出现在两个位置（A[i][j]和A[j][i]），因此至少有2(n-1)个非零元素。

11.答案： D
解析： 在带权有向图的邻接矩阵中，第i列元素表示其他顶点到顶点i的边。顶点i的入度就是这些边中存在的（即权值非∞且非0）的个数。0通常表示顶点到自身的权值，不计入入度。

12.答案： D
解析： 邻接矩阵是一个n阶方阵，大小为n×n。

13.答案： B
解析： 无向图的每条边在邻接矩阵中会对称地出现两次（A[i][j]和A[j][i]），因此非零元素个数是边数的两倍，即2e。

14.答案： A
解析： 对于无向图，A[i][j] = A[j][i]，因此邻接矩阵是对称矩阵。

15.答案： C
解析： 根据常见的深度优先遍历（DFS）逻辑，从v0出发，优先访问第一个相邻且未访问的顶点，图中所示邻接矩阵对应的DFS序列为0,1,3,4,2,5,6。

16.答案： A
解析： 深度优先遍历（DFS）通常使用栈（或递归调用栈）来保存待访问的路径，以便回溯。

17.答案： B
解析： 从一个顶点出发的DFS能访问所有顶点，意味着该图是连通的（任意两个顶点之间有路径）。

18.答案： D
解析： 根据所给邻接表，从v0出发，DFS优先访问邻接表中的第一个邻居，因此遍历顺序为0,1,2,3。

19.答案： B
解析： 广度优先遍历（BFS）通常使用队列来管理待访问的顶点。

20.答案： D
解析： 从v0出发，BFS先访问所有直接邻居，因此遍历顺序为0,1,2,3。

二、填空题解析

1.答案： n-1
解析： n个顶点的连通图至少需要构成一棵生成树，其边数为n-1。

2.答案： 1
解析： 无向图的邻接矩阵是对称矩阵。

3.答案： 列
解析： 在有向图的邻接矩阵中，第i列元素表示其他顶点到顶点i的边，其和即为顶点i的入度。

4.答案： 深度
解析： 深度优先搜索（DFS）天然适合用递归实现。

5.答案： (1) 栈（或堆栈） (2) 队（或队列）
解析： DFS常用栈（递归栈或显式栈），BFS常用队列。

三、判断题解析

1.答案： 错
解析： 连通分量是极大连通子图（即不能再加入其他顶点和边而保持连通），不是“极小”。

2.答案： 对
解析： 从同一顶点出发，若存在多个相邻顶点，访问顺序不同会导致不同的遍历序列。此外，起点选择不同也会导致序列不同。

四、简答题

1.

2.(1)

(2)
d的度是6
f的度是3
该顶点这一行非无穷的个数

3.