数据结构与算法--图（概念+练习题+解析）_给定一有向图的邻接表如下。从顶点v1出发按广度优先搜索法进行遍历,则得到的一种

概念：

有向图

在有向图中有以下几点结论：

1.所有顶点的度数之和等于边数的二倍。

2.所有顶点的入度之和等于出度之和。

3.n个顶点的有向完全图有n(n-1)条边。

4.n个顶点的强连通图至少有n条边。

无向图

在无向图中有以下几点结论：

1.所有顶点的度数之和等于边数的二倍。

2.n个顶点的无向完全图有n(n-1)/2条边。

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

完全图

也称简单完全图。假设一个图有n个顶点，那么如果任意两个顶点之间都有边的话，该图就称为完全图。

n个端点的完全图有n个端点以及n(n−1)/2条边，

连通图（特指无向图）

在一个无向图中，从每一个顶点到每一个其它顶点都存在一条路径，则此无向图是连通的。

极大连通子图是无向图的连通分量（极大连通子图也指无向图）。

有n个顶点的连通图最多有n(n-1)/2条边，最少有n-1条边。

强连通图（特指有向图）

在有向图G中，如果两个顶点u，v间有一条从u到v的有向路径，同时还有一条从v到u的有向路径，则称两个顶点强连通。

如果有向图G的每两个顶点都强连通，称G是一个强连通图。

有向非强连通图的极大强连通子图，称为强连通分量（环或一个结点）。

有n个顶点的强连通图最多有n(n-1)条边，最少有n条边。

极大是要求该连通子图包含其所有的边

极小是在保持连通的情况下使边数最少的子图

极大连通分量

极小连通分量

极大强连通分量

极小强连通分量

无向连通图所有顶点的度之和为偶数

在一个有向图中，所有顶点的入度与出度之和等于所有边之和的2倍

在任一有向图中，所有顶点的入度之和等于所有顶点的出度之和

如果无向图G必须进行两次广度优先搜索才能访问其所有结点，则G一定有2个连通分量

假设图中有n个顶点，e条边，则含有e=n(n-1)/2条边的无向图称作完全图，含有e=n(n-1)条弧的有向图称作

有向完全图

无向图：度

有向图：入度、出度

邻接矩阵（稠密图）

深度优先周游：时间复杂度O(n^2)，空间复杂度O(n)

无向图的邻接矩阵是对称的

有向图的邻接矩阵可以是对称的，也可以是不对称的

用邻接矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关，空间代价为O(n^2)（n为结

点个数）

邻接表（稀疏图）

深度优先周游：时间复杂度O(n+e)，空间复杂度O(n)

用邻接表存储图，占用的存储空间数与图中结点个数和边数都有关，有向图的空间代价为O(n+e)，无向图的

空间代价为O(n+2e)（n为结点个数，e为边数）

拓扑排序（有向无环图，DAG图）

若图G有环，则G不存在拓扑排序序列

拓扑排序序列不唯一

拓扑排序：（O(n+e)）

1、从有向图中选一个没有前驱的顶点并输出

2、从图中删除该顶点和所有以它为尾的弧

3、重复上述两步，直至全部顶点均已输出，或者当图中不存在无前驱的顶点为止

最短路径问题

单源最短路径（Dijkstra）（迪杰斯特拉）

时间复杂度O(n^2)

每对顶点之间的最短路径（Floyd）（弗洛伊德）

时间复杂度O(n^3)

最小生成树

Prim算法（普里姆）（稠密图）

通过每步添加一条边及其相连的顶点到一棵树，从而逐步生成最小生成树

时间复杂度O(n^2)

Kruskal算法（克鲁斯卡尔）（稀疏图）

维护一个森林，每一步把两棵树合并成一棵

时间复杂度O(eloge)

生成树

生成树：所有顶点均由边连接在一起，但不存在回路的图（极小连通子图）

一个有n个顶点的连通图的生成树有n-1条边（反之不成立）

在生成树中再加一条边必然形成回路

生成树中任意两个顶点间的路径是唯一的

一个图可以有许多棵不同的生成树

最小生成树不唯一

拓扑排序

步骤：

①在有向图中选一个没有前驱的顶点且输出之

②从图中删除该顶点和所有以它为尾的弧

深度优先搜索（Depth First Search，DFS）

广度优先搜索（Breadth First Search，BFS）

求最短路径算法（Dijkstra算法）

求最小生成树算法（Prim算法，Krukal算法）

判断题：

1、无向连通图所有顶点的度之和为偶数。

T

2、无向连通图边数一定大于顶点个数减1。

F

3、用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。

F 用邻接表法存储图，占用的存储空间数与图中结点个数和边数都有关。

用邻接表法存储有向图的空间代价为O(n+e)，存储无向图的空间代价为O(n+2e)（n为结点个数，e为边数）。

4、用邻接矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。

T 用邻接矩阵法存储图的空间代价为O(n^2)（n为结点个数）。

5、在一个有向图中，所有顶点的入度与出度之和等于所有边之和的2倍。

T

6、在任一有向图中，所有顶点的入度之和等于所有顶点的出度之和。

T

7、如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则G一定有2个连通分量。

T

8、Prim 算法是维护一个森林，每一步把两棵树合并成一棵。

F Prim 算法是通过每步添加一条边及其相连的顶点到一棵树，从而逐步生成最小生成树。

9、Kruskal 算法是维护一个森林，每一步把两棵树合并成一棵。

T

10、Kruskal 算法是通过每步添加一条边及其相连的顶点到一棵树，从而逐步生成最小生成树。

F Kruskal 算法是维护一个森林，每一步把两棵树合并成一棵。

11、Prim 算法是通过每步添加一条边及其相连的顶点到一棵树，从而逐步生成最小生成树。

T

12、无向连通图至少有一个顶点的度为1。

F 一个三角形形状的无向连通图，顶点的度都为2。

13、用一维数组G[]存储有4个顶点的无向图如下：

G[] = { 0, 1, 0, 1, 1, 0, 0, 0, 1, 0 }

则顶点2和顶点0之间是有边的。

T

0 1 2 3

0 0

1 1 0

2 1 1 0

3 0 0 1 0

选择题：

1、下面关于图的存储的叙述中，哪一个是正确的？

A.用相邻矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关

B.用相邻矩阵法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关

C.用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关

D.用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关

A

用邻接表法存储图，占用的存储空间数与图中结点个数和边数都有关。

用邻接矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。

2、关于图的邻接矩阵，下列哪个结论是正确的？

A.有向图的邻接矩阵总是不对称的

B.有向图的邻接矩阵可以是对称的，也可以是不对称的

C.无向图的邻接矩阵总是不对称的

D.无向图的邻接矩阵可以是不对称的，也可以是对称的

B

有向图的邻接矩阵不一定对称。

无向图的邻接矩阵一定对称。

3、设N个顶点E条边的图用邻接表存储，则求每个顶点入度的时间复杂度为：

A.O(N)

B.O(N^2)

C.O(N+E)

D.O(N×E)

C

用邻接表法存储有向图的空间代价为O(n+e)，存储无向图的空间代价为O(n+2e)（n为结点个数，e为边数）。

用邻接矩阵法存储图的空间代价为O(n^2)（n为结点个数）。

4、在任一有向图中，所有顶点的入度之和与所有顶点的出度之和的关系是：

A.相等

B.大于等于

C.小于等于

D.不确定

A

5、下面给出的有向图中，有__个强连通分量。

A.1 ({0,1,2,3,4})

B.1 ({1,2,3,4})

C.2 ({1,2,3,4}, {0})

D.5 ({0}, {1}, {2}, {3}, {4})

C

环或一个结点。

6、给定一个有向图的邻接表如下图，则该图有__个强连通分量。

A.4 {{0, 1, 5}, {2}, {3}, {4}}

B.3 {{2}, {4}, {0, 1, 3, 5}}

C.1 {0, 1, 2, 3, 4, 5}

D.1 {0, 5, 1, 3}

B

环或一个结点。

7、对于一个具有N个顶点的无向图，要连通所有顶点至少需要多少条边？

A.N−1

B.N

C.N+1

D.N/2

A

8、一个有N个顶点的强连通图至少有多少条边？

A.N−1

B.N

C.N+1

D.N(N−1)

B

9、对于有向图，其邻接矩阵表示比邻接表表示更易于：

A.求一个顶点的入度

B.求一个顶点的出边邻接点

C.进行图的深度优先遍历

D.进行图的广度优先遍历

A

邻接矩阵用空间换取时间，对于查询度会比邻接表更快，因为邻接表查入度时候需要遍历所有节点。

10、在用邻接表表示有N个结点E条边的图时，深度优先遍历算法的时间复杂度为：

A.O(N)

B.O(N+E)

C.O(N^2)

D.O(N^2×E)

B

利用邻接矩阵存储的图的遍历的时间复杂度为O(n^2)。

利用邻接表存储的图的遍历的时间复杂度为O(n+e)。

n为结点数，e为边数。

11、给定一有向图的邻接表如下。从顶点V1出发按深度优先搜索法进行遍历，则得到的一种顶点序列为：

A.V1,V2,V3,V5,V4

B.V1,V3,V4,V5,V2

C.V1,V4,V3,V5,V2

D.V1,V2,V4,V5,V3

B

深度优先搜索法

1 3 4 5 2

12、已知一个图的邻接矩阵如下，则从顶点V1出发按深度优先搜索法进行遍历，可能得到的一种顶点序列为：

A.V1,V2,V3,V4,V5,V6

B.V1,V2,V4,V5,V6,V3

C.V1,V3,V5,V2,V4,V6

D.V1,V3,V5,V6,V2,V4

B

深度优先搜索法

1→2→3→5

2→1→4

3→1→5→6

4→2→5

5→1→3→4→6

6→3→5

1 2 4 5 3 6

1 2 4 5 6 3

1 3 5 4 2 6

1 3 5 6 4 2

......

13、如果从无向图的任一顶点出发进行一次深度优先搜索可访问所有顶点，则该图一定是：

A.连通图

B.完全图

C.有回路的图

D.一棵树

A

14、给定一有向图的邻接表如下。从顶点V1出发按广度优先搜索法进行遍历，则得到的一种顶点序列为：

A.V1,V2,V3,V4,V5

B.V1,V2,V3,V5,V4

C.V1,V3,V2,V4,V5

D.V1,V4,V3,V5,V2

C

广度优先搜索法

1 3 2 4 5

15、已知一个图的邻接矩阵如下，则从顶点V1出发按广度优先搜索法进行遍历，可能得到的一种顶点序列为：

A.V1,V2,V3,V5,V4,V6

B.V1,V2,V4,V5,V6,V3

C.V1,V3,V5,V2,V4,V6

D.V1,V3,V5,V6,V4,V2

A

广度优先搜索法

1→2→3→5

2→1→4

3→1→5→6

4→2→5

5→1→3→4→6

6→3→5

1 2 3 5 4 6

16、图的广度优先遍历类似于二叉树的：

A.先序遍历

B.中序遍历

C.后序遍历

D.层次遍历

D

17、我们用一个有向图来表示航空公司所有航班的航线。下列哪种算法最适合解决找给定两城市间最经济的飞行路线问题？

A.Dijkstra算法

B.Kruskal算法

C.深度优先搜索

D.拓扑排序算法

A

两城市间最经济的飞行路线问题→最短路径问题→Dijkstra算法

18、数据结构中Dijkstra算法用来解决哪个问题？

A.关键路径

B.最短路径

C.拓扑排序

D.字符串匹配

B

最短路径问题。

19、使用迪杰斯特拉（Dijkstra）算法求下图中从顶点1到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是：

A.5, 2, 3, 4, 6

B.5, 2, 3, 6, 4

C.5, 2, 4, 3, 6

D.5, 2, 6, 3, 4

B

1→5 : 4

1→2 : 5

1→3 : 7

1→6 : 9

1→4 : 11

20、任何一个带权无向连通图的最小生成树——

A.是唯一的

B.是不唯一的

C.有可能不唯一

D.有可能不存在

B

最小生成树不唯一。

21、给定有权无向图的邻接矩阵如下，其最小生成树的总权重是：

A.10

B.11

C.12

D.14

D

1 2 3 4 5

1 0

2 4 0

3 10 9 0

4 3 5 8 0

5 2 6 7 1 0

1+2+4+7=14

22、对下图进行拓扑排序，可以得到不同的拓扑序列的个数是：

A.4

B.3

C.2

D.1

B

拓扑排序的步骤：

①在有向图中选一个没有前驱的顶点且输出之

②从图中删除该顶点和所有以它为尾的弧

a e b c d

a b c e d

a b e c d

23、使用迪杰斯特拉（Dijkstra）算法求下图中从顶点1到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是：

A.6, 7, 5, 3, 2, 4

B.6, 2, 5, 7, 3, 4

C.2, 3, 4, 5, 6, 7

D.2, 4, 3, 6, 5, 7

A

1→6 : 5

1→2 : 35

1→6→7 : 7

1→6→5 : 13

1→6→3 : 17

1→6→7→5 : 11

1→6→3→2 : 18

1→6→7→4 : 19

1→6→3→4 : 20

1→6 : 5

1→6→7 : 7

1→6→7→5 : 11

1→6→3 : 17

1→6→3→2 : 18

1→6→7→4 : 19

6 7 5 3 2 4

24、下列关于无向连通图特征的叙述中，正确的是：

1. 所有顶点的度之和为偶数

2. 边数大于顶点个数减1

3. 至少有一个顶点的度为1

A.只有1

B.只有2

C.1和2

D.1和3

A

有n个顶点的连通图最多有n(n-1)/2 条边（完全图），最少有n-1条边（单链表）。

2.边数等于顶点个数*2，只有两个顶点的无向连通图，边数等于顶点个数减1

3.三角形形状的无向连通图（完全图），三个顶点的度都为2

25、给出如下图所示的具有 7 个结点的网 G，采用Prim算法，从4号结点开始，给出该网的最小生成树。下列哪个选项给出了正确的树结点收集顺序？

A.4501362

B.4526301

C.4561023

D.4563201

D

从4号结点开始

4 →5:1

4 5 →6:2

4 5 6 →3:2

4 5 6 3 →2:4 4 5 6 3 →1:4

4 5 6 3 2 →0:3 4 5 6 3 1 →0:1

4 5 6 3 2 0 →1:1 4 5 6 3 1 0 →2:3

4 5 6 3 2 0 1 4 5 6 3 1 0 2

26、将一个 10×10 的对称矩阵 M 的上三角部分的元素 mi,j（1≤i≤j≤10）按列优先存入C语言的一维数组 N 中，元素 m7,2在 N在中的下标是：

A.15

B.16

C.22

D.23

C

在第1+2+3+4+5+6+2=23个存储单元

下标为23-1=22

0

1 2

3 4 5

8 9 10 11

12 13 14 15 16

17 18 19 20 21 22

23 22

27、修改递归方式实现的图的深度优先搜索（DFS）算法，将输出（访问）顶点信息的语句移动到退出递归前（即执行输出语句后立即退出递归）。采用修改后的算法遍历有向无环图 G，若输出结果中包含 G 中的全部顶点，则输出的顶点序列是 G 的：

A.拓扑有序序列

B.逆拓扑有序序列

C.广度优先搜索序列

D.深度优先搜索序列

B

倒序输出拓扑序列，即输出逆拓扑序列。

28、已知无向图 G 如下所示，使用克鲁斯卡尔（Kruskal）算法求图 G 的最小生成树，加入到最小生成树中的边依次是：

A.(b,f), (b,d), (a,e), (c,e), (b,e)

B.(b,f), (b,d), (b,e), (a,e), (c,e)

C.(a,e), (b,e), (c,e), (b,d), (b,f)

D.(a,e), (c,e), (b,e), (b,f), (b,d)

A

Kruskal算法：依次选权值最小的边加入最小生成树（加入边后不能形成环），直至所有结点都加入最小生成树。

29、给定如下有向图，该图的拓扑有序序列的个数是：

A.1

B.2

C.3

D.4

A

A B C D E F

30、使用 Dijkstra 算法求下图中从顶点 1 到其余各顶点的最短路径，将当前找到的从顶点 1 到顶点 2、3、4、5 的最短路径长度保存在数组 dist 中，求出第二条最短路径后，dist 中的内容更新为：

A.26、3、14、6

B.25、3、14、6

C.21、3、14、6

D.15、3、14、6

C

第一次求能直接到达各顶点的边的权值，后续依次增加边数求权值。

1→2:26

1→5→2:21

1→3:3

1→4:∞

1→5→4:14

1→5:6

31、一个有n个顶点的简单有向图最多有 （ ） 条边

A.n

B.n(n-1)

C.n(n-1)/2

D.2n

B

有向完全图

在有向图中有以下几点结论：

1.所有顶点的度数之和等于边数的二倍。

2.所有顶点的入度之和等于出度之和。

3.n个顶点的有向完全图有n(n-1)条边。

4.n个顶点的强连通图至少有n条边。

32、图的遍历(广度优先)

对下图进行广度优先遍历，得到的序列不可能为 ▁▁▁▁▁ 。

A.BCFADE

B.DCEFBA

C.AFEBCD

D.CDFBAE

A

A→D:∞

33、拓扑排序

▁▁▁▁▁ 是下面 AOV 网的一个拓扑序列。

A.BDACFEG

B.ACBDFEG

C.ABDCFEG

D.CDEABFG

B

A B C D E F G

A B C D F E G

A C B D E F G

A C B D F E G

34、对于无向图 G=(V,E), 下列选项中， 正确的是：

A.当 ∣V∣>∣E∣ 时，G 一定是连通的

B.当 ∣V∣<∣E∣ 时，G 一定是连通的

C.当 ∣V∣=∣E∣−1 时，G 一定是不连通的

D.当∣V∣>∣E∣+1 时，G 一定是不连通的

D

有n个顶点的连通图最多有n(n-1)/2条边，最少有n-1条边。

n - 1 < e < n ( n - 1 ) / 2

D.∣V∣>∣E∣+1 → e < n - 1 → 一定不连通

35、假设我们掌握了从各种不同案件中推导出的疑犯关系，即“A 与 B 属于同一团伙”的信息若干条，要求列出规模最大的那个团伙的所有成员。以下哪种算法最合适解决这个问题？

A.并查集

B.深度优先搜素

C.多源最短路算法

D.最小生成树算法

B

”A 与 B 属于同一团伙”的信息若干条，

列出规模最大的那个团伙的所有成员，

即求拓扑序列。

可以使用深度优先搜索对有向无环图进行拓扑排序。

36、假设我们掌握了从各种不同案件中推导出的疑犯关系，即“A 与 B 属于同一团伙”的信息若干条，要求判断是否所有嫌犯都属于同一个团伙。以下哪种算法不能解决这个问题？

A.并查集

B.广度优先搜索

C.最小生成树算法

D.拓扑排序算法

D

”A 与 B 属于同一团伙”的信息若干条，

判断是否所有嫌犯都属于同一个团伙，

即判断一个图是否连通。

可以使用DFS（广度优先搜索）、BFS（深度优先搜索）（求最小生成树算法使用深度优先搜索）和并查集。