概念：

有向圖

在有向圖中有以下幾點結(jié)論：

1.所有頂點的度數(shù)之和等于邊數(shù)的二倍。

2.所有頂點的入度之和等于出度之和。

3.n個頂點的有向完全圖有n(n-1)條邊。

4.n個頂點的強(qiáng)連通圖至少有n條邊。

無向圖

在無向圖中有以下幾點結(jié)論：

1.所有頂點的度數(shù)之和等于邊數(shù)的二倍。

2.n個頂點的無向完全圖有n(n-1)/2條邊。

3.n個頂點的連通圖至少有n-1條邊。

完全圖

也稱簡單完全圖。假設(shè)一個圖有n個頂點，那么如果任意兩個頂點之間都有邊的話，該圖就稱為完全圖。

n個端點的完全圖有n個端點以及n(n?1)/2條邊，

連通圖（特指無向圖）

在一個無向圖中，從每一個頂點到每一個其它頂點都存在一條路徑，則此無向圖是連通的。

極大連通子圖是無向圖的連通分量（極大連通子圖也指無向圖）。

有n個頂點的連通圖最多有n(n-1)/2條邊，最少有n-1條邊。

強(qiáng)連通圖（特指有向圖）

在有向圖G中，如果兩個頂點u，v間有一條從u到v的有向路徑，同時還有一條從v到u的有向路徑，則稱兩個頂點強(qiáng)連通。

如果有向圖G的每兩個頂點都強(qiáng)連通，稱G是一個強(qiáng)連通圖。

有向非強(qiáng)連通圖的極大強(qiáng)連通子圖，稱為強(qiáng)連通分量（環(huán)或一個結(jié)點）。

有n個頂點的強(qiáng)連通圖最多有n(n-1)條邊，最少有n條邊。

極大是要求該連通子圖包含其所有的邊

極小是在保持連通的情況下使邊數(shù)最少的子圖

極大連通分量

極小連通分量

極大強(qiáng)連通分量

極小強(qiáng)連通分量

無向連通圖所有頂點的度之和為偶數(shù)

在一個有向圖中，所有頂點的入度與出度之和等于所有邊之和的2倍

在任一有向圖中，所有頂點的入度之和等于所有頂點的出度之和

如果無向圖G必須進(jìn)行兩次廣度優(yōu)先搜索才能訪問其所有結(jié)點，則G一定有2個連通分量

假設(shè)圖中有n個頂點，e條邊，則含有e=n(n-1)/2條邊的無向圖稱作完全圖，含有e=n(n-1)條弧的有向圖稱作

有向完全圖

無向圖：度

有向圖：入度、出度

鄰接矩陣（稠密圖）

深度優(yōu)先周游：時間復(fù)雜度O(n^2)，空間復(fù)雜度O(n)

無向圖的鄰接矩陣是對稱的

有向圖的鄰接矩陣可以是對稱的，也可以是不對稱的

用鄰接矩陣法存儲圖，占用的存儲空間數(shù)只與圖中結(jié)點個數(shù)有關(guān)，而與邊數(shù)無關(guān)，空間代價為O(n^2)（n為結(jié)

點個數(shù)）

鄰接表（稀疏圖）

深度優(yōu)先周游：時間復(fù)雜度O(n+e)，空間復(fù)雜度O(n)

用鄰接表存儲圖，占用的存儲空間數(shù)與圖中結(jié)點個數(shù)和邊數(shù)都有關(guān)，有向圖的空間代價為O(n+e)，無向圖的

空間代價為O(n+2e)（n為結(jié)點個數(shù)，e為邊數(shù)）

拓?fù)渑判颍ㄓ邢驘o環(huán)圖，DAG圖）

若圖G有環(huán)，則G不存在拓?fù)渑判蛐蛄?/h5>

拓?fù)渑判蛐蛄胁晃ㄒ?/h5>

拓?fù)渑判颍海∣(n+e)）

1、從有向圖中選一個沒有前驅(qū)的頂點并輸出

2、從圖中刪除該頂點和所有以它為尾的弧

3、重復(fù)上述兩步，直至全部頂點均已輸出，或者當(dāng)圖中不存在無前驅(qū)的頂點為止

最短路徑問題

單源最短路徑（Dijkstra）（迪杰斯特拉）

時間復(fù)雜度O(n^2)

每對頂點之間的最短路徑（Floyd）（弗洛伊德）

時間復(fù)雜度O(n^3)

最小生成樹

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

通過每步添加一條邊及其相連的頂點到一棵樹，從而逐步生成最小生成樹

時間復(fù)雜度O(n^2)

Kruskal算法（克魯斯卡爾）（稀疏圖）

維護(hù)一個森林，每一步把兩棵樹合并成一棵

時間復(fù)雜度O(eloge)

生成樹

生成樹：所有頂點均由邊連接在一起，但不存在回路的圖（極小連通子圖）

一個有n個頂點的連通圖的生成樹有n-1條邊（反之不成立）

在生成樹中再加一條邊必然形成回路

生成樹中任意兩個頂點間的路徑是唯一的

一個圖可以有許多棵不同的生成樹

最小生成樹不唯一

拓?fù)渑判?/h5>

步驟：

①在有向圖中選一個沒有前驅(qū)的頂點且輸出之

②從圖中刪除該頂點和所有以它為尾的弧

深度優(yōu)先搜索（Depth First Search，DFS）

廣度優(yōu)先搜索（Breadth First Search，BFS）

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

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

判斷題：

1、無向連通圖所有頂點的度之和為偶數(shù)。

T

2、無向連通圖邊數(shù)一定大于頂點個數(shù)減1。

F

3、用鄰接表法存儲圖，占用的存儲空間數(shù)只與圖中結(jié)點個數(shù)有關(guān)，而與邊數(shù)無關(guān)。

F 用鄰接表法存儲圖，占用的存儲空間數(shù)與圖中結(jié)點個數(shù)和邊數(shù)都有關(guān)。

用鄰接表法存儲有向圖的空間代價為O(n+e)，存儲無向圖的空間代價為O(n+2e)（n為結(jié)點個數(shù)，e為邊數(shù)）。

4、用鄰接矩陣法存儲圖，占用的存儲空間數(shù)只與圖中結(jié)點個數(shù)有關(guān)，而與邊數(shù)無關(guān)。

T 用鄰接矩陣法存儲圖的空間代價為O(n^2)（n為結(jié)點個數(shù)）。

5、在一個有向圖中，所有頂點的入度與出度之和等于所有邊之和的2倍。

T

6、在任一有向圖中，所有頂點的入度之和等于所有頂點的出度之和。

T

7、如果無向圖G必須進(jìn)行兩次廣度優(yōu)先搜索才能訪問其所有頂點，則G一定有2個連通分量。

T

8、Prim 算法是維護(hù)一個森林，每一步把兩棵樹合并成一棵。

F Prim 算法是通過每步添加一條邊及其相連的頂點到一棵樹，從而逐步生成最小生成樹。

9、Kruskal 算法是維護(hù)一個森林，每一步把兩棵樹合并成一棵。

T

10、Kruskal 算法是通過每步添加一條邊及其相連的頂點到一棵樹，從而逐步生成最小生成樹。

F Kruskal 算法是維護(hù)一個森林，每一步把兩棵樹合并成一棵。

11、Prim 算法是通過每步添加一條邊及其相連的頂點到一棵樹，從而逐步生成最小生成樹。

T

12、無向連通圖至少有一個頂點的度為1。

F 一個三角形形狀的無向連通圖，頂點的度都為2。

13、用一維數(shù)組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、下面關(guān)于圖的存儲的敘述中，哪一個是正確的？

A.用相鄰矩陣法存儲圖，占用的存儲空間數(shù)只與圖中結(jié)點個數(shù)有關(guān)，而與邊數(shù)無關(guān)

B.用相鄰矩陣法存儲圖，占用的存儲空間數(shù)只與圖中邊數(shù)有關(guān)，而與結(jié)點個數(shù)無關(guān)

C.用鄰接表法存儲圖，占用的存儲空間數(shù)只與圖中結(jié)點個數(shù)有關(guān)，而與邊數(shù)無關(guān)

D.用鄰接表法存儲圖，占用的存儲空間數(shù)只與圖中邊數(shù)有關(guān)，而與結(jié)點個數(shù)無關(guān)

A

用鄰接表法存儲圖，占用的存儲空間數(shù)與圖中結(jié)點個數(shù)和邊數(shù)都有關(guān)。

用鄰接矩陣法存儲圖，占用的存儲空間數(shù)只與圖中結(jié)點個數(shù)有關(guān)，而與邊數(shù)無關(guān)。

2、關(guān)于圖的鄰接矩陣，下列哪個結(jié)論是正確的？

A.有向圖的鄰接矩陣總是不對稱的

B.有向圖的鄰接矩陣可以是對稱的，也可以是不對稱的

C.無向圖的鄰接矩陣總是不對稱的

D.無向圖的鄰接矩陣可以是不對稱的，也可以是對稱的

B

有向圖的鄰接矩陣不一定對稱。

無向圖的鄰接矩陣一定對稱。

3、設(shè)N個頂點E條邊的圖用鄰接表存儲，則求每個頂點入度的時間復(fù)雜度為：

A.O(N)

B.O(N^2)

C.O(N+E)

D.O(N×E)

C

用鄰接表法存儲有向圖的空間代價為O(n+e)，存儲無向圖的空間代價為O(n+2e)（n為結(jié)點個數(shù)，e為邊數(shù)）。

用鄰接矩陣法存儲圖的空間代價為O(n^2)（n為結(jié)點個數(shù)）。

4、在任一有向圖中，所有頂點的入度之和與所有頂點的出度之和的關(guān)系是：

A.相等

B.大于等于

C.小于等于

D.不確定

A

5、下面給出的有向圖中，有__個強(qiáng)連通分量。

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

環(huán)或一個結(jié)點。

6、給定一個有向圖的鄰接表如下圖，則該圖有__個強(qiáng)連通分量。

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

環(huán)或一個結(jié)點。

7、對于一個具有N個頂點的無向圖，要連通所有頂點至少需要多少條邊？

A.N?1

B.N

C.N+1

D.N/2

A

8、一個有N個頂點的強(qiáng)連通圖至少有多少條邊？

A.N?1

B.N

C.N+1

D.N(N?1)

B

9、對于有向圖，其鄰接矩陣表示比鄰接表表示更易于：

A.求一個頂點的入度

B.求一個頂點的出邊鄰接點

C.進(jìn)行圖的深度優(yōu)先遍歷

D.進(jìn)行圖的廣度優(yōu)先遍歷

A

鄰接矩陣用空間換取時間，對于查詢度會比鄰接表更快，因為鄰接表查入度時候需要遍歷所有節(jié)點。

10、在用鄰接表表示有N個結(jié)點E條邊的圖時，深度優(yōu)先遍歷算法的時間復(fù)雜度為：

A.O(N)

B.O(N+E)

C.O(N^2)

D.O(N^2×E)

B

利用鄰接矩陣存儲的圖的遍歷的時間復(fù)雜度為O(n^2)。

利用鄰接表存儲的圖的遍歷的時間復(fù)雜度為O(n+e)。

n為結(jié)點數(shù)，e為邊數(shù)。

11、給定一有向圖的鄰接表如下。從頂點V1出發(fā)按深度優(yōu)先搜索法進(jìn)行遍歷，則得到的一種頂點序列為：

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

深度優(yōu)先搜索法

1 3 4 5 2

12、已知一個圖的鄰接矩陣如下，則從頂點V1出發(fā)按深度優(yōu)先搜索法進(jìn)行遍歷，可能得到的一種頂點序列為：

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

深度優(yōu)先搜索法

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、如果從無向圖的任一頂點出發(fā)進(jìn)行一次深度優(yōu)先搜索可訪問所有頂點，則該圖一定是：

A.連通圖

B.完全圖

C.有回路的圖

D.一棵樹

A

14、給定一有向圖的鄰接表如下。從頂點V1出發(fā)按廣度優(yōu)先搜索法進(jìn)行遍歷，則得到的一種頂點序列為：

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

廣度優(yōu)先搜索法

1 3 2 4 5

15、已知一個圖的鄰接矩陣如下，則從頂點V1出發(fā)按廣度優(yōu)先搜索法進(jìn)行遍歷，可能得到的一種頂點序列為：

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

廣度優(yōu)先搜索法

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、圖的廣度優(yōu)先遍歷類似于二叉樹的：

A.先序遍歷

B.中序遍歷

C.后序遍歷

D.層次遍歷

D

17、我們用一個有向圖來表示航空公司所有航班的航線。下列哪種算法最適合解決找給定兩城市間最經(jīng)濟(jì)的飛行路線問題？

A.Dijkstra算法

B.Kruskal算法

C.深度優(yōu)先搜索

D.拓?fù)渑判蛩惴?/p>

A

兩城市間最經(jīng)濟(jì)的飛行路線問題→最短路徑問題→Dijkstra算法

18、數(shù)據(jù)結(jié)構(gòu)中Dijkstra算法用來解決哪個問題？

A.關(guān)鍵路徑

B.最短路徑

C.拓?fù)渑判?/p>

D.字符串匹配

B

最短路徑問題。

19、使用迪杰斯特拉（Dijkstra）算法求下圖中從頂點1到其他各頂點的最短路徑，依次得到的各最短路徑的目標(biāo)頂點是：

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、任何一個帶權(quán)無向連通圖的最小生成樹——

A.是唯一的

B.是不唯一的

C.有可能不唯一

D.有可能不存在

B

最小生成樹不唯一。

21、給定有權(quán)無向圖的鄰接矩陣如下，其最小生成樹的總權(quán)重是：

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、對下圖進(jìn)行拓?fù)渑判颍梢缘玫讲煌耐負(fù)湫蛄械膫€數(shù)是：

A.4

B.3

C.2

D.1

B

拓?fù)渑判虻牟襟E：

①在有向圖中選一個沒有前驅(qū)的頂點且輸出之

②從圖中刪除該頂點和所有以它為尾的弧

a e b c d

a b c e d

a b e c d

23、使用迪杰斯特拉（Dijkstra）算法求下圖中從頂點1到其他各頂點的最短路徑，依次得到的各最短路徑的目標(biāo)頂點是：

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、下列關(guān)于無向連通圖特征的敘述中，正確的是：

1. 所有頂點的度之和為偶數(shù)

2. 邊數(shù)大于頂點個數(shù)減1

3. 至少有一個頂點的度為1

A.只有1

B.只有2

C.1和2

D.1和3

A

有n個頂點的連通圖最多有n(n-1)/2 條邊（完全圖），最少有n-1條邊（單鏈表）。

2.邊數(shù)等于頂點個數(shù)*2，只有兩個頂點的無向連通圖，邊數(shù)等于頂點個數(shù)減1

3.三角形形狀的無向連通圖（完全圖），三個頂點的度都為2

25、給出如下圖所示的具有 7 個結(jié)點的網(wǎng) G，采用Prim算法，從4號結(jié)點開始，給出該網(wǎng)的最小生成樹。下列哪個選項給出了正確的樹結(jié)點收集順序？

A.4501362

B.4526301

C.4561023

D.4563201

D

從4號結(jié)點開始

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）按列優(yōu)先存入C語言的一維數(shù)組 N 中，元素 m7,2在 N在中的下標(biāo)是：

A.15

B.16

C.22

D.23

C

在第1+2+3+4+5+6+2=23個存儲單元

下標(biāo)為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、修改遞歸方式實現(xiàn)的圖的深度優(yōu)先搜索（DFS）算法，將輸出（訪問）頂點信息的語句移動到退出遞歸前（即執(zhí)行輸出語句后立即退出遞歸）。采用修改后的算法遍歷有向無環(huán)圖 G，若輸出結(jié)果中包含 G 中的全部頂點，則輸出的頂點序列是 G 的：

A.拓?fù)溆行蛐蛄?/p>

B.逆拓?fù)溆行蛐蛄?/p>

C.廣度優(yōu)先搜索序列

D.深度優(yōu)先搜索序列

B

倒序輸出拓?fù)湫蛄?，即輸出逆拓?fù)湫蛄小?/span>

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算法：依次選權(quán)值最小的邊加入最小生成樹（加入邊后不能形成環(huán)），直至所有結(jié)點都加入最小生成樹。

29、給定如下有向圖，該圖的拓?fù)溆行蛐蛄械膫€數(shù)是：

A.1

B.2

C.3

D.4

A

A B C D E F

30、使用 Dijkstra 算法求下圖中從頂點 1 到其余各頂點的最短路徑，將當(dāng)前找到的從頂點 1 到頂點 2、3、4、5 的最短路徑長度保存在數(shù)組 dist 中，求出第二條最短路徑后，dist 中的內(nèi)容更新為：

A.26、3、14、6

B.25、3、14、6

C.21、3、14、6

D.15、3、14、6

C

第一次求能直接到達(dá)各頂點的邊的權(quán)值，后續(xù)依次增加邊數(shù)求權(quán)值。

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

有向完全圖

在有向圖中有以下幾點結(jié)論：

1.所有頂點的度數(shù)之和等于邊數(shù)的二倍。

2.所有頂點的入度之和等于出度之和。

3.n個頂點的有向完全圖有n(n-1)條邊。

4.n個頂點的強(qiáng)連通圖至少有n條邊。

32、圖的遍歷(廣度優(yōu)先)

對下圖進(jìn)行廣度優(yōu)先遍歷，得到的序列不可能為 ▁▁▁▁▁ 。

A.BCFADE

B.DCEFBA

C.AFEBCD

D.CDFBAE

A

A→D:∞

33、拓?fù)渑判?/p>

▁▁▁▁▁ 是下面 AOV 網(wǎng)的一個拓?fù)湫蛄小?/p>

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.當(dāng) ∣V∣>∣E∣ 時，G 一定是連通的

B.當(dāng) ∣V∣<∣E∣ 時，G 一定是連通的

C.當(dāng) ∣V∣=∣E∣?1 時，G 一定是不連通的

D.當(dāng)∣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、假設(shè)我們掌握了從各種不同案件中推導(dǎo)出的疑犯關(guān)系，即“A 與 B 屬于同一團(tuán)伙”的信息若干條，要求列出規(guī)模最大的那個團(tuán)伙的所有成員。以下哪種算法最合適解決這個問題？

A.并查集

B.深度優(yōu)先搜素

C.多源最短路算法

D.最小生成樹算法

B

”A 與 B 屬于同一團(tuán)伙”的信息若干條，

列出規(guī)模最大的那個團(tuán)伙的所有成員，

即求拓?fù)湫蛄小?/span>

可以使用深度優(yōu)先搜索對有向無環(huán)圖進(jìn)行拓?fù)渑判颉?/span>

36、假設(shè)我們掌握了從各種不同案件中推導(dǎo)出的疑犯關(guān)系，即“A 與 B 屬于同一團(tuán)伙”的信息若干條，要求判斷是否所有嫌犯都屬于同一個團(tuán)伙。以下哪種算法不能解決這個問題？

A.并查集

B.廣度優(yōu)先搜索

C.最小生成樹算法

D.拓?fù)渑判蛩惴?/p>

D

”A 與 B 屬于同一團(tuán)伙”的信息若干條，

判斷是否所有嫌犯都屬于同一個團(tuán)伙，

即判斷一個圖是否連通。

可以使用DFS（廣度優(yōu)先搜索）、BFS（深度優(yōu)先搜索）（求最小生成樹算法使用深度優(yōu)先搜索）和并查集。文章來源地址http://www.zghlxwxcb.cn/news/detail-758739.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法--圖（概念+練習(xí)題+解析）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！