引言
浠水網(wǎng)站制作公司哪家好，找
創(chuàng)新互聯(lián)建站！從網(wǎng)頁設(shè)計、網(wǎng)站建設(shè)、微信開發(fā)、APP開發(fā)、
響應(yīng)式網(wǎng)站設(shè)計等網(wǎng)站項目制作，到程序開發(fā)，運營維護。
創(chuàng)新互聯(lián)建站從2013年開始到現(xiàn)在10年的時間，我們擁有了豐富的建站經(jīng)驗和運維經(jīng)驗，來保證我們的工作的順利進行。專注于網(wǎng)站建設(shè)就選
創(chuàng)新互聯(lián)建站。
- 文章大綱：本文由知識點思維導圖，注意事項與易錯點，題型總結(jié)，方法心得四部分組成。
- 思維導圖中，標紅的是重點內(nèi)容，標黃的是次重點。
- 碼字不易，如果這篇文章對您有幫助的話，希望您能點贊、收藏、加關(guān)注！您的鼓勵就是我前進的動力！
知識點思維導圖
（點此查看原圖）
補充：
- 鄰接表
1）優(yōu)點：空間效率高，容易尋找頂點的鄰接點；
2）缺點：判斷兩頂點間是否有邊或弧，需搜索兩結(jié)點對應(yīng)的單鏈表，沒有鄰接矩陣方便。
3）鄰接矩陣的空間復雜度為O(n2)，而鄰接表的空間復雜度O(n+e)。
4）鄰接矩陣多用于稠密圖的存儲，鄰接表多用于稀疏圖的存儲。 - 圖的遍歷
1）為避免訪問多次，常設(shè)置一個訪問數(shù)組，訪問前的元素標志為0，訪問后設(shè)置為1。
2）深度優(yōu)先搜索是一種遞歸的過程。
3）深度和廣度優(yōu)先遍歷得到的序列不唯一。
4）若圖是連通的或強連通的，則從圖中某一個頂點出發(fā)可以訪問到圖中所有頂點，否則只能訪問到一部分頂點，再從未被訪問的頂點中選一個頂點出發(fā)訪問未被訪問的頂點。
5）廣度優(yōu)先生成樹高度 ≤ 深度優(yōu)先生成樹高度
注意事項與易錯點
- 用Prim算法構(gòu)建最小生成樹時，注意每一輪選邊時，要將已選頂點一起作為一組，找出這一組中，到剩余結(jié)點中權(quán)最小的邊，而不是只看新加入結(jié)點的最小邊。
題型總結(jié)
一、求關(guān)鍵路徑
- 五個描述量：
1）ve( vj ) 表示事件（即圖中的頂點） vj 的最早發(fā)生時間。計算方法：從
v
e
(
1
)
=
0
ve(1)=0
ve(1)=0 開始向前遞推，
v
e
(
j
)
=
M
a
x
[
v
e
(
i
)
+
W
i
,
j
]
ve(j)=Max[ve(i)+W_{i,j}]
ve(j)=Max[ve(i)+Wi,j?]
即事件的最早發(fā)生時間，等于該事件的前一個事件的最早發(fā)生時間加上兩個事件之間的弧上的權(quán)值，該事件的前一個事件若有多個，則取結(jié)果大的。
2）vl( vj ) 表示事件 vj 的最晚發(fā)生時間。計算方法：從
v
l
(
n
?
1
)
=
v
e
(
n
?
1
)
vl(n-1)=ve(n-1)
vl(n?1)=ve(n?1) 開始向后遞推，
v
l
[
i
]
=
M
i
n
[
v
l
[
j
]
?
W
i
,
j
]
vl[i]=Min[vl[j]-W_{i,j}]
vl[i]=Min[vl[j]?Wi,j?]
即事件的最晚發(fā)生時間，等于該事件的后一個事件的最晚發(fā)生時間減去兩個事件之間的弧上的權(quán)值，該事件的后一個事件若有多個，則取結(jié)果最小的。
3）e( i ) 表示活動（即圖中的弧） ai 的最早開始時間。計算方法：
e
(
i
)
=
v
e
(
j
)
e(i) = ve(j)
e(i)=ve(j)
即活動的最早開始時間等于（弧尾）事件的最早開始時間。
4）l( i ) 表示活動 ai 的最晚開始時間。計算方法：
l
(
i
)
=
v
l
(
k
)
?
W
i
,
j
l(i)=vl(k)-W_{i,j}
l(i)=vl(k)?Wi,j?
即活動的最晚開始時間等于（弧頭）事件的最晚發(fā)生時間減去活動所需時間（弧上的權(quán)值）。
5）時間余量：
l
(
i
)
?
e
(
i
)
l(i) - e(i)
l(i)?e(i)
- 求關(guān)鍵路徑的步驟：
1）列表求
v
e
(
i
)
ve(i)
ve(i)、
v
e
(
j
)
ve(j)
ve(j)（見下表）
2）列表求
e
(
i
)
e(i)
e(i)、
e
(
j
)
e(j)
e(j) 和
e
(
i
)
?
e
(
j
)
e(i) - e(j)
e(i)?e(j)（見下表）
3）表中所有
e
(
i
)
?
e
(
j
)
e(i) - e(j)
e(i)?e(j) 等于0的弧組成的路徑就是關(guān)鍵路徑。
| 頂點 |
v
(
e
)
v(e)
v(e) |
v
(
l
)
v(l)
v(l) |
|---|
|
V
1
V1
V1 | | |
|
V
2
V2
V2 | | |
| …… | | |
|
V
n
Vn
Vn | | |
| 活動 |
e
(
i
)
e(i)
e(i) |
l
(
i
)
l(i)
l(i) |
e
(
i
)
?
l
(
i
)
e(i)-l(i)
e(i)?l(i) |
|---|
|
a
1
a1
a1 | | | |
|
a
2
a2
a2 | | | |
| …… | | | |
|
a
n
an
an | | | |
（詳解見青島大學-王卓老師數(shù)據(jù)結(jié)構(gòu)與算法-關(guān)鍵路徑）
二、Dijkstra算法（求單源最短路徑）
- 步驟：
1）初始化：先找出從源點到各個終點的直達路徑
(
v
0
,
v
k
)
(v_0,v_k)
(v0?,vk?)，即通過一條弧到達的路徑。
2）選擇：從這些路徑中找出一條長度最短的路徑
(
v
0
,
u
)
(v_0,u)
(v0?,u)。
3）更新：然后對其余各條路徑進行適當調(diào)整，若圖中存在弧
(
u
,
v
k
)
(u,v_k)
(u,vk?)，且
(
v
0
,
u
)
+
(
u
,
v
k
)
<
(
v
0
,
v
k
)
(v_0,u)+(u,v_k)<(v_0,v_k)
(v0?,u)+(u,vk?)<(v0?,vk?)，則以路徑
(
v
0
,
u
,
v
k
)
(v_0,u,v_k)
(v0?,u,vk?) 代替
(
v
0
,
v
k
)
(v_0,v_k)
(v0?,vk?)，在調(diào)整后的各條路徑中，再找長度最短的路徑，以此類推。 - 注意：
1）把V集合分為 S 和 T 兩組，其中S是已求出最短路徑的頂點集合；T是尚未確定最短路徑的頂點集合（即T=V - S）。
2）將T中頂點按照最短路徑遞增的次序加入到S中。 - 例題：求下圖的最短路徑：
解析：
1）初始化：從
v
0
v_0
v0?能直達
v
1
v_1
v1?、
v
2
v_2
v2?、
v
4
v_4
v4?和
v
6
v_6
v6?，故在下表中第一列對應(yīng)格填入距離和路徑，無法直達的填∞。
2）選擇：其中路徑長度最小的是
<
v
0
,
v
2
>
（為8）故寫在
v
j
v_j
vj?處。
3）更新：在S集合加入頂點
v
2
v_2
v2?后，后面就不用在考慮
v
2
v_2
v2?了（
v
0
v_0
v0?到
v
2
v_2
v2?的最短路徑已經(jīng)確定了），故在表格中將后續(xù)的
v
2
v_2
v2?劃掉。再看加入
v
2
v_2
v2?后，可直達的路徑有沒有變得更短，有則更新，沒有保持不變，數(shù)據(jù)填入第二列中，其中
v
0
v_0
v0?到
v
1
v_1
v1?的路徑最短，故將其填入第二列的
v
j
v_j
vj?中。
4）以此類推，填好該表格，表格的最后一行和最后一列所表示的路徑即為從
v
0
v_0
v0?到各頂點的最短路徑。
（詳解見青島大學-王卓老師數(shù)據(jù)結(jié)構(gòu)與算法-Dijkstra算法）
三、Floyd算法（求所有頂點間的最短路徑）
- 算法思想：逐個頂點試探，從
v
i
v_i
vi?到
v
j
v_j
vj?的所有可能存在的路徑中選出一條長度最短的路徑。
- 解題步驟：
1）初始時設(shè)置一個n階方陣，令其對角線元素為0，若存在弧
<
V
i
,
V
j
>
，則對應(yīng)元素為權(quán)值；否則為∞。
2）逐步試著在原直接路徑中增加中間頂點，若加入中間點后路徑變短，則修改之；否則，維持原值。
3）所有頂點試探完畢，算法結(jié)束。 - 補充：
1）也可以用 Dijkstra算法 來計算所有頂點間的最短路徑，但較為復雜。
2）該算法的時間復雜度和 Dijkstra算法 的時間復雜度均為
O
(
n
3
)
O(n^3)
O(n3)，但該方法較為簡單。
（詳解見青島大學-王卓老師數(shù)據(jù)結(jié)構(gòu)與算法-Floyd算法）
方法心得
NULL
參考資料：
［1］ 程杰. 大話數(shù)據(jù)結(jié)構(gòu). 北京：清華大學出版社, 2020.
［2］嚴蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu) (C語言版). 北京：清華大學出版社, 1997.
［3］青島大學-王卓老師數(shù)據(jù)結(jié)構(gòu)與算法課：關(guān)鍵路徑、Dijkstra算法、Floyd算法。
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧
文章名稱：第八章圖-創(chuàng)新互聯(lián)
URL標題：
http://weahome.cn/article/dechpd.html
重慶分公司
重慶分公司
