# 20162317 2017-2018-1 《程式設計與資料結構》第10周學習總結

20162317 2017-2018-1 《程式設計與資料結構》第10周學習總結 十九章 圖

教材學習内容總結

1. 圖的概念和特點
2. 圖的組成
3. 圖的類型
4. 拓撲序的定義
5. 圖的算法
6. 鄰接表（正鄰接表、逆鄰接表、帶權鄰接表）
7. 鄰接矩陣

教材學習中的問題和解決過程

• 問題1：我看到書上有這麼一句話：“生成樹的一個令人感興趣的應用是找到帶權圖的最小生成樹。最小生成樹是其所含邊的權值之和小于等于圖的任意其他生成樹的邊的權值之和的生成樹”，但并未能看懂其中的意思
• 問題1解決方案：在上網查閱資料和例子之後，我明白了最小生成樹是這個意思，一個圖可以有多種生成樹，同時要明白一個概念，每棵生成樹的權值之和一定小于原圖的權值之和。樹有多樣性，權值和也就多樣性，在這其中會存在一個權值之和最小的生成樹，這棵生成樹就是最小生成樹。
• 問題2：我在有關圖的PPT中看到有圖的構造和儲存方法之一——鄰接多重表設計，但不能了解它的運作流程。
• 問題2解決方案：XXXXXX
• 問題3：圖的例子中的結點序列和結果不知道如何得到的。
• 問題3解決方案：XXXXXX
• 問題4：我在PPT圖中看到一個叫作AOE網的圖，它其中有一個概念——關鍵路徑：圖中最長的路徑。但例如在這張圖中：

最長路徑不隻一條，但它們的權值又不相同，試問哪條才是關鍵路徑呢？

• 問題5的解決方案：上網查找參考資料——AOE網。結合資料與個人分析

代碼托管

上周考試錯題總結

• 錯題1及原因，了解情況
• 錯題2及原因，了解情況
• ...

其他

• 隻有頂點沒有邊也是圖，是圖的一種特殊情況。
• 網：邊（或弧）上帶權的圖
• 特殊的子圖：

下面的圖可以看成是一個整體，那麼該整體是上面圖的子圖；若将下面的圖分成兩部分來看，每一小部分也是上面圖的子圖。

• 稀疏圖和稠密圖：有很少條邊或弧（如e<nlogn，n是圖的頂點數，e是弧數）的圖稱為稀疏圖，反之成為稠密圖。

• 有向圖的頂點排序：

根據圖，我們可以列出這樣一個表：

頂點	引用
A	無
B	A,C
C
D
E	C,B,D

進而我們可以得到這麼一個情況：

進而這幾個頂點的順序為：A、C、B、D、E。同時，這一種将無序的頂點通過關系将其有序排列的做法叫做拓撲排序

拓撲排序的定義就是：由某個集合上的一個偏序（集合中僅有集合中僅有部分成員之間可比較）得到該集合上的一個全序（集合中全體成員之間均可比較

），這個操作稱之為拓撲排序。

解析：圖上的表就是一個偏序，通過表得到的頂點線性排列圖表示的就是全序

唯一性：當圖中的所有頂點指之間具有全序關系，那麼拓撲排序的結果唯一；同時，所有頂點之間不具備全序關系，拓撲排序也就不唯一。

拓撲排序的特點：

1. 圖中所有的有向邊均是從左指向右的
2. 若圖中存在有向環，則不可能使頂點滿足拓撲次序。

1. 一個DAG(無回路有向圖)的拓撲序列通常表示某種方案切實可行。

AOV網權重值後的表達方式：

例：

該圖的拓撲排序是：

表示方式：

裡面暗的點隻是表示階段，不是學科。

表示方式的圖叫做AOE網，即帶權有向圖。圖中最長的路徑叫做關鍵路徑。AOE圖隻有一個源點，隻有一個彙點。

AOE網中的頂點和邊是有含義和屬性的：

• 頂點表示事件（能被觸發，兩特征屬性：最早發生時間Ve(j);最晚發生時間Vl(j)）
• 邊表示活動（能被開始，兩特征屬性：最早開始時間e(i)；最晚開始時間l(i)），權表示活動持續時間

.

• Ve(j):是指從源點到彙點的最大路徑長度。

計算方法：

（1）從前到後取值取較大值，最終獲得路徑長度的權值之和最大

（2）源點的值預設為0

用上方的AOE網圖：

	V1	V2	V3	V4	V5	V6
Ve(j)	32	96	142	74	194

計算順序：

“------------------------------------------------------------------>”

• Vl(j)

（1）從後到前取值取較小值,獲得路徑最長，最後權值最小的路徑。

（2）彙點就是Ve(j)

用上方的AOE網圖

“<-------------------------------------------------------------------”

• e(i):若活動ai由弧<vk,vj>表示，則活動ai的最早開始時間應該等于事件vk的最早發生時間。因而，有：e[i]=ve[k]

	c1	c2	c3	c4	c5	c6
e(i)

• l(i):若活動ai由弧<vk,vj>表示,有l[i] = vj - ai

用上方的AOE網圖:

	66		98

計算關鍵路徑的方法：

隻需求出上面的四個特征屬性，然後取e(i)=l(i)的邊即為關鍵路徑上的邊。

由上面兩個表格可知，e(i) = l(i)的有C6、C4、C5

是以最長路徑是：

V1--C6-->V3--C4-->V4--C5-->V6

• 關鍵路徑的特點是：

1. 關鍵路徑上所有活動的持續時間總和就是項目的工期。
2. 關鍵路徑上的任何一個活動都是關鍵活動，其中任何一個活動的延遲都會導緻整個項目完工時間的延遲。
3. 若縮短關鍵路徑的總耗時，會縮短項目工期
4. 可以存在多條關鍵路徑

學習進度條

代碼行數（新增/累積）	部落格量（新增/累積）	學習時間（新增/累積）	重要成長
目标	5000行	15篇	400小時
第一周	200/200	2/2	20/20
第二周	20/220	1/3	20/40
第三周	645/865	1/4	14/54
第五周	654/1519	1/5	18/72
第六周	436/1955	1/6	16/88
第七周	839/2794	2/8	20/108
第八周	2143/4937	2/10	25/133
第九周	1368/6305	2/12	18/151
第十周	2452/8757	1/13	16/167

• 計劃學習時間:20小時
• 實際學習時間:16小時