[電腦基礎(chǔ)知識]數(shù)據(jù)結(jié)構(gòu)圖.ppt

1、第7章 圖,圖是一種非線性結(jié)構(gòu),結(jié)構(gòu)較復(fù)雜,數(shù)據(jù)元素之間的關(guān)系是任意的。它可應(yīng)用到電子線路分析、系統(tǒng)工程、人工智能等。 7.1 圖的定義和術(shù)語 圖的抽象數(shù)據(jù)類型:P156157 圖的定義 圖(Graph)圖G是由兩個(gè)集合V(G)和E(G)組成的,記為G=(V,E) 其中：V(G)是頂點(diǎn)的非空有限集 E(G)是邊的有限集合，邊是頂點(diǎn)的無序?qū)蛴行驅(qū)?零圖：只有頂點(diǎn)沒有邊，E（G）為空集 有向圖有向圖G是由兩個(gè)集合V(G)和E(G)組成的 其中：V(G)是頂點(diǎn)的非空有限集 E(G)是有向邊（也稱?。┑挠邢藜?，弧是頂點(diǎn)的有序?qū)Γ洖椋瑅,w是頂點(diǎn)，v為弧尾，w為弧頭 無向圖無向圖G是由兩個(gè)集合V(

2、G)和E(G)組成的 其中：V(G)是頂點(diǎn)的非空有限集 E(G)是邊的有限集合，邊是頂點(diǎn)的無序?qū)?，記為（v,w）或（w,v)，并且（v,w)=(w,v),圖G1中：V(G1)=1,2,3,4,5,6 E(G1)=, , , , , , ,圖G2中：V(G2)=1,2,3,4,5,6,7 E(G1)=(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7),圖的基本術(shù)語 完全圖：n個(gè)頂點(diǎn)的圖中，每個(gè)頂點(diǎn)與其它n-1個(gè)頂點(diǎn)都有邊 有向完全圖n個(gè)頂點(diǎn)的有向圖最大邊數(shù)是n(n-1) 無向完全圖n個(gè)頂點(diǎn)的無向圖最大邊數(shù)是n(n-1)/2 權(quán)與圖的邊或弧相關(guān)的數(shù)叫 網(wǎng)帶

3、權(quán)的圖叫 子圖如果圖G(V,E)和圖G(V,E),滿足： VV EE 則稱G為G的子圖 頂點(diǎn)的度 無向圖中，頂點(diǎn)的度為與每個(gè)頂點(diǎn)相連的邊數(shù) 有向圖中，頂點(diǎn)的度分成入度與出度 入度：以該頂點(diǎn)為頭的弧的數(shù)目 出度：以該頂點(diǎn)為尾的弧的數(shù)目 路徑路徑是頂點(diǎn)的序列V=Vi0,Vi1,Vin，滿足(Vij-1,Vij)E 或 E,(1jn),路徑長度沿路徑邊的數(shù)目或沿路徑各邊權(quán)值之和 回路第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑叫 簡單路徑序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑叫 簡單回路除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路叫 連通從頂點(diǎn)V到頂點(diǎn)W有一條路徑，則說V和W是連通的 連通圖圖中任意兩個(gè)頂點(diǎn)都

4、是連通的叫 連通分量非連通圖的每一個(gè)連通部分叫 (P159 圖7.3) 強(qiáng)連通圖有向圖中，如果對每一對Vi,VjV, ViVj,從Vi到Vj 和從Vj到 Vi都存在路徑，則稱G是 P159圖7.4中V2是自身對自身的強(qiáng)連通分量,路徑：1，2，3，5，6，3 路徑長度：5 簡單路徑：1，2，3，5 回路：1，2，3，5，6，3，1 簡單回路：3，5，6，3,路徑：1，2，5，7，6，5，2，3 路徑長度：7 簡單路徑：1，2，5，7，6 回路：1，2，5，7，6，5，2，1 簡單回路：1，2，3，1,連通圖,強(qiáng)連通圖,非連通圖 連通分量,有向樹:一個(gè)有向圖若只有一個(gè)頂點(diǎn)的入度為0, 其余頂點(diǎn)的入

5、度都為1,則該圖稱為一棵有向樹. 生成森林:由若干棵有向樹組成,含圖中全部頂點(diǎn),這些頂點(diǎn)構(gòu)成若干棵互不相交的有向樹的弧. P160圖7.6,7.2 圖的存儲(chǔ)結(jié)構(gòu) 多重鏈表(P160),數(shù)組表示法表示頂點(diǎn)間相聯(lián)關(guān)系的鄰接矩陣 定義：設(shè)G=(V,E)是有n1個(gè)頂點(diǎn)的圖，G的鄰接矩陣A是具有以下性質(zhì)的n階方陣,特點(diǎn)： 無向圖的鄰接矩陣對稱，可壓縮存儲(chǔ)；有n個(gè)頂點(diǎn)的無向圖需存儲(chǔ)空間為n(n+1)/2 有向圖鄰接矩陣不一定對稱；有n個(gè)頂點(diǎn)的有向圖需存儲(chǔ)空間為n 無向圖中頂點(diǎn)Vi的度TD(Vi)是鄰接矩陣A中第i行(或第i列)元素之和 有向圖中， 頂點(diǎn)Vi的出度OD(vi)是A中第i行元素之和 頂點(diǎn)Vi的

6、入度ID(vi)是A中第i列元素之和 網(wǎng)絡(luò)的鄰接矩陣可定義為：,P162圖7.9是有向網(wǎng)的鄰接矩陣,關(guān)聯(lián)矩陣表示頂點(diǎn)與邊的關(guān)聯(lián)關(guān)系的矩陣 定義：設(shè)G=(V,E)是有n1個(gè)頂點(diǎn)，e0條邊的圖，G的關(guān)聯(lián)矩陣A是具有以下性質(zhì)的ne階矩陣,特點(diǎn) 關(guān)聯(lián)矩陣每列只有兩個(gè)非零元素，是稀疏矩陣；n越大，零元素比率越大 無向圖中頂點(diǎn)Vi的度TD(Vi)是關(guān)聯(lián)矩陣A中第i行元素之和 有向圖中， 頂點(diǎn)Vi的出度是A中第i行中“1”的個(gè)數(shù) 頂點(diǎn)Vi的入度是A中第i行中“-1”的個(gè)數(shù),鄰接表 實(shí)現(xiàn)：為圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，第i個(gè)單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)Vi的邊 有向圖中指以Vi為尾的弧,即頂點(diǎn)vi的出度,特點(diǎn)

7、 無向圖中頂點(diǎn)Vi的度為第i個(gè)單鏈表中的結(jié)點(diǎn)數(shù) 有向圖中 頂點(diǎn)Vi的出度為第i個(gè)單鏈表中的結(jié)點(diǎn)個(gè)數(shù) 頂點(diǎn)Vi的入度為整個(gè)單鏈表中鄰接點(diǎn)域值是i的結(jié)點(diǎn)個(gè)數(shù) 逆鄰接表：有向圖中對每個(gè)結(jié)點(diǎn)建立以Vi為頭的弧的單鏈表 逆鄰接表:,有向圖的十字鏈表表示法,藍(lán)色鄰接表 ，綠色第2個(gè)域值相同的結(jié)點(diǎn)鏈,無向圖的鄰接多重表表示法,7.3 圖的遍歷(P167) 深度優(yōu)先遍歷(DFS) 方法：從圖的某一頂點(diǎn)V0出發(fā)，訪問此頂點(diǎn)；然后依次從V0的未被訪問的鄰接點(diǎn)出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和V0相通的頂點(diǎn)都被訪問到；若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未被訪問的頂點(diǎn)作起點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都

8、被訪問為止,深度遍歷：V1 V2 V4 V8 V5 V3 V6 V7,深度遍歷：V1 V2 V4 V8 V5 V6 V3 V7 或 V1 V2 V4 V8 V6 V3 V7 V5 或,深度遍歷：V1 V2 V4 V8 V5 V6 V3 V7,深度遍歷：V1 V2 V4 V8 V3 V6 V7 V5,深度優(yōu)先遍歷算法 遞歸算法,Ch7_1.c,深度遍歷：V1,V3 ,V7 ,V6 ,V2 ,V5 ,V8 ,V4,深度遍歷：V1,V3 ,V7 ,V6 ,V2 ,V4 ,V8 ,V5,廣度優(yōu)先遍歷(BFS) 方法：從圖的某一頂點(diǎn)V0出發(fā)，訪問此頂點(diǎn)后，依次訪問V0的各個(gè)未曾訪問過的鄰接點(diǎn)；然后分別從

9、這些鄰接點(diǎn)出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到；若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未被訪問的頂點(diǎn)作起點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問為止,廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8,廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8,廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8,廣度遍歷：V1 V2 V3 V4 V6 V7 V8 V5 （V5逆向最后訪問）,廣度優(yōu)先遍歷算法,Ch7_2.c,鄰接表：,7.4 圖的連通性問題 生成樹 定義：所有頂點(diǎn)均由邊連接在一起，但不存在回路的圖叫 深度優(yōu)先生成樹與廣度優(yōu)先生成樹

10、生成森林：非連通圖每個(gè)連通分量的生成樹組成的非連通圖的 說明 一個(gè)圖可以有許多棵不同的生成樹 所有生成樹具有以下共同特點(diǎn)： 生成樹的頂點(diǎn)個(gè)數(shù)與圖的頂點(diǎn)個(gè)數(shù)相同 生成樹是圖的極小連通子圖 一個(gè)有n個(gè)頂點(diǎn)的連通圖的生成樹有n-1條邊 生成樹中任意兩個(gè)頂點(diǎn)間的路徑是唯一的 在生成樹中再加一條邊必然形成回路 含n個(gè)頂點(diǎn)n-1條邊的圖不一定是生成樹,無向圖的連通分量和生成樹 連通圖的生成樹 非連通圖的生成森林,深度遍歷：V1 V2 V4 V8 V5 V3 V6 V7,廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8,(無向圖)連通圖的生成樹:,最小生成樹 問題提出,要在n個(gè)城市間建立通信聯(lián)絡(luò)網(wǎng)，

11、 頂點(diǎn)表示城市 權(quán)城市間建立通信線路所需花費(fèi)代價(jià) 希望找到一棵生成樹，它的每條邊上的權(quán)值之和（即建立 該通信網(wǎng)所需花費(fèi)的總代價(jià)）最小最小代價(jià)生成樹,問題分析,n個(gè)城市間，最多可設(shè)置n(n-1)/2條線路 n個(gè)城市間建立通信網(wǎng)，只需n-1條線路 問題轉(zhuǎn)化為：如何在可能的線路中選擇n-1條，能把 所有城市（頂點(diǎn)）均連起來，且總耗費(fèi) （各邊權(quán)值之和）最小,構(gòu)造最小生成樹方法 方法一：普里姆(Prim)算法 算法思想：設(shè)N=(V,E)是連通網(wǎng)，TE是N上最小生成樹中邊的集合 初始令U=u0,(u0V), TE= 在所有uU,vV-U的邊(u,v)E中，找一條代價(jià)最小的邊(u0,v0) 將(u0,v0)

12、并入集合TE，同時(shí)v0并入U(xiǎn) 重復(fù)上述操作直至U=V為止，則T=(V,TE)為N的最小生成樹 算法實(shí)現(xiàn)：圖用鄰接矩陣表示 算法描述 算法評價(jià)：T(n)=O(n),1,3到2和5中,到2最短,1,1,-2,1,-4,1,-1,1,-5,1,-3,以頂點(diǎn)6為起始點(diǎn),方法二：克魯斯卡爾(Kruskal)算法 算法思想：設(shè)連通網(wǎng)N=(V,E)，令最小生成樹 初始狀態(tài)為只有n個(gè)頂點(diǎn)而無邊的非連通圖T=(V,)，每個(gè)頂點(diǎn)自成一個(gè)連通分量 在E中選取代價(jià)最小的邊，若該邊依附的頂點(diǎn)落在T中不同的連通分量上，則將此邊加入到T中；否則，舍去此邊，選取下一條代價(jià)最小的邊 依此類推，直至T中所有頂點(diǎn)都在同一連通分量上

13、為止,（0）用頂點(diǎn)數(shù)組和邊數(shù)組存放頂點(diǎn)和邊信息 （1）初始時(shí)，令每個(gè)頂點(diǎn)的jihe互不相同；每個(gè)邊的flag為0 （2）選出權(quán)值最小且flag為0的邊 （3）若該邊依附的兩個(gè)頂點(diǎn)的jihe 值不同，即非連通，則令 該邊的flag=1, 選中該邊；再令該邊依附的兩頂點(diǎn)的jihe 以及兩集合中所有頂點(diǎn)的jihe 相同 若該邊依附的兩個(gè)頂點(diǎn)的jihe 值相同，即連通，則令該 邊的flag=2, 即舍去該邊 （4）重復(fù)上述步驟，直到選出n-1條邊為止,頂點(diǎn)結(jié)點(diǎn)： typedef struct int data; /頂點(diǎn)信息 int jihe; VEX;,邊結(jié)點(diǎn)： typedef struct int

14、vexh, vext; /邊依附的兩頂點(diǎn) int weight; /邊的權(quán)值 int flag; /標(biāo)志域 EDGE;,算法實(shí)現(xiàn)：,Ch6_30.c,算法描述：,1,1,1,1,1,4,2,1,1,1,2,2,2,2,2,7.5有向無環(huán)圖及其應(yīng)用,一個(gè)無環(huán)的有向圖稱做有向無環(huán)圖（directed acycline praph）。簡稱DAG圖 有向無環(huán)圖應(yīng)用：描述公共子式表達(dá)式；工程；系統(tǒng)的有效工具。 關(guān)于工程：計(jì)劃、施工過程、生產(chǎn)流程、程序流程等都可看成一個(gè)工程。 活動(dòng)(子工程)；一個(gè)大的工程常常被劃分成許多較小的子工程，這些子工程稱為活動(dòng)，這些活動(dòng)完成時(shí)，整個(gè)工程也就完成了。 主要的兩個(gè)方面

15、: 工程的可行性; 估算整個(gè)工程完成所必須的最短時(shí)間(拓?fù)渑判颉⑶箨P(guān)鍵路徑),有向樹、DAG圖和有向圖示意,P179利用有向無環(huán)圖表達(dá)含公共子式的表達(dá)式 利用有向無環(huán)圖，可將相同子式共享，以減少信息的重復(fù)表達(dá)。 無向圖中，若DFS過程中遇到回邊，則必定存在環(huán)。 有向圖中，DFS的回邊可能是指向DFS生成森林的另一棵生成樹上頂點(diǎn)的弧。 有向圖中，DFS中v到u路徑，但又出現(xiàn)u到v的回邊，則必定存在包含v和u的環(huán)。,7.5.1 拓?fù)渑判?問題提出：學(xué)生選修課程問題 頂點(diǎn)表示課程 有向弧表示先決條件，若課程i是課程j的先決條件，則圖中有弧 學(xué)生應(yīng)按怎樣的順序?qū)W習(xí)這些課程，才能無矛盾、順利地完成學(xué)業(yè)拓

16、撲排序 定義 AOV網(wǎng)用頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)間優(yōu)先關(guān)系的有向圖稱為頂點(diǎn)表示活動(dòng)的網(wǎng)(Activity On Vertex network)，簡稱AOV網(wǎng) 若是圖中有向邊，則vi是vj的直接前驅(qū)；vj是vi的直接后繼,并且具有傳遞性。 AOV網(wǎng)中不允許有回路，這意味著某項(xiàng)活動(dòng)以自己為先決條件（此工程是無法完成的）,7.5.1 拓?fù)渑判?拓?fù)渑判?(數(shù)學(xué)中) 由某個(gè)集合上的一個(gè)偏序得到該集合上的一個(gè)全序,這個(gè)操作過程叫拓?fù)渑判颉?偏序:直觀地說指集合中僅有部分成員之間可比較。 全序:指集合中全體成員之間均可比較。 表示偏序和全序的有向圖P180圖7.25,拓?fù)渑判虬袮OV網(wǎng)絡(luò)中各頂點(diǎn)按照它們

17、相互之間的優(yōu)先關(guān)系排列成一個(gè)有序序列的過程叫 檢測AOV網(wǎng)中是否存在環(huán)（回路）方法（拓?fù)渑判颍簩τ邢驁D構(gòu)造其頂點(diǎn)的拓?fù)溆行蛐蛄?，若網(wǎng)中所有頂點(diǎn)都在它的拓?fù)溆行蛐蛄兄?，則該AOV網(wǎng)必定不存在環(huán) 拓?fù)渑判虻姆椒?在有向圖中選一個(gè)沒有前驅(qū)的頂點(diǎn)且輸出之 從圖中刪除該頂點(diǎn)和所有以它為尾的弧 重復(fù)上述兩步，直至全部頂點(diǎn)均已輸出；或者當(dāng)圖中不存在無前驅(qū)的頂點(diǎn)為止,拓?fù)湫蛄校篊1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8 或 ：C9-C10-C11-C6-C1-C12-C4-C2-C3-C5-C7-C8,一個(gè)AOV網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏?算法實(shí)現(xiàn)（棧） 以鄰接表作存儲(chǔ)結(jié)構(gòu) 把

18、鄰接表中所有入度為0的頂點(diǎn)進(jìn)棧 棧非空時(shí)，輸出棧頂元素Vj并退棧；在鄰接表中查找Vj的直接后繼Vk，把Vk的入度減1；若Vk的入度為0則進(jìn)棧 重復(fù)上述操作直至?？諡橹?。若?？諘r(shí)輸出的頂點(diǎn)個(gè)數(shù)不是n，則有向圖有環(huán)；否則，拓?fù)渑判蛲戤?鄰接表結(jié)點(diǎn)： typedef struct node int vex; /頂點(diǎn)域 struct node *next; /鏈域 JD;,表頭結(jié)點(diǎn)： typedef struct tnode int in; /入度域 struct node *link; /鏈域 TD; TD gM; /g0不用,算法描述,Ch7_40.c,1,6,輸出序列：6,輸出序列：6,輸出序列

19、：6,輸出序列：6,輸出序列：6,輸出序列：6,輸出序列：6 1,輸出序列：6 1,輸出序列：6 1,4,輸出序列：6 1,4,輸出序列：6 1,4,輸出序列：6 1,4,3,輸出序列：6 1,4,3,輸出序列：6 1,4,3,輸出序列：6 1,4,3,輸出序列：6 1,4,3,輸出序列：6 1 3,4,3,輸出序列：6 1 3,4,輸出序列：6 1 3,4,輸出序列：6 1 3,4,輸出序列：6 1 3,4,2,輸出序列：6 1 3,4,2,輸出序列：6 1 3,4,2,輸出序列：6 1 3 2,4,2,輸出序列：6 1 3 2,4,輸出序列：6 1 3 2 4,4,輸出序列：6 1 3 2

20、 4,輸出序列：6 1 3 2 4,5,輸出序列：6 1 3 2 4,5,輸出序列：6 1 3 2 4 5,5,輸出序列：6 1 3 2 4 5,算法分析,建鄰接表：T(n)=O(e) 搜索入度為0的頂點(diǎn)的時(shí)間：T(n)=O(n) 拓?fù)渑判颍篢(n)=O(n+e),Ch7_4.c,7.5.2 關(guān)鍵路徑 問題提出,把工程計(jì)劃表示為有向圖，用頂點(diǎn)表示事件，弧表示活動(dòng)； 每個(gè)事件表示在它之前的活動(dòng)已完成，在它之后的活動(dòng)可以開始,例 設(shè)一個(gè)工程有11項(xiàng)活動(dòng)，9個(gè)事件 事件 V1表示整個(gè)工程開始 事件V9表示整個(gè)工程結(jié)束 問題：（1）完成整項(xiàng)工程至少需要多少時(shí)間？ （2）哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵？,

21、定義 AOE網(wǎng)(Activity On Edge)也叫邊表示活動(dòng)的網(wǎng)。AOE網(wǎng)是一個(gè)帶權(quán)的有向無環(huán)圖，其中頂點(diǎn)表示事件，弧表示活動(dòng)，權(quán)表示活動(dòng)持續(xù)時(shí)間 路徑長度路徑上各活動(dòng)持續(xù)時(shí)間之和 關(guān)鍵路徑路徑長度最長的路徑叫 Ve(j)表示事件Vj的最早發(fā)生時(shí)間 Vl(j)表示事件Vj的最遲發(fā)生時(shí)間 e(i)表示活動(dòng)ai的最早開始時(shí)間 l(i)表示活動(dòng)ai的最遲開始時(shí)間 l(i)-e(i)表示完成活動(dòng)ai的時(shí)間余量 關(guān)鍵活動(dòng)關(guān)鍵路徑上的活動(dòng)叫，即l(i)=e(i)的活動(dòng),問題分析 如何找e(i)=l(i)的關(guān)鍵活動(dòng)？,設(shè)活動(dòng)ai用弧表示，其持續(xù)時(shí)間記為：dut() 則有：（1）e(i)=Ve(j) （2

22、）l(i)=Vl(k)-dut(),如何求Ve(j)和Vl(j)？,(1)從Ve(1)=0開始向前遞推,(2)從Vl(n)=Ve(n)開始向后遞推,求關(guān)鍵路徑步驟 求Ve(i) 求Vl(j) 求e(i) 求l(i) 計(jì)算l(i)-e(i),V1 V2 V3 V4 V5 V6 V7 V8 V9,0 6 4 5 7 7 16 14 18,0 6 6 8 7 10 16 14 18,a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11, ,=(a1+a4)- (a2+a5),=18-(a6+a9+a11),算法實(shí)現(xiàn) 以鄰接表作存儲(chǔ)結(jié)構(gòu) 從源點(diǎn)V1出發(fā)，令Ve1=0,按拓?fù)湫蛄星蟾黜旤c(diǎn)

23、的Vei 從匯點(diǎn)Vn出發(fā)，令Vln=Ven,按逆拓?fù)湫蛄星笃溆喔黜旤c(diǎn)的Vli 根據(jù)各頂點(diǎn)的Ve和Vl值，計(jì)算每條弧的ei和li,找出ei=li的關(guān)鍵活動(dòng),鄰接表結(jié)點(diǎn)： typedef struct node int vex; /頂點(diǎn)域 int length; struct node *next; /鏈域 JD;,表頭結(jié)點(diǎn)： typedef struct tnode int vexdata; int in; /入度域 struct node *link; /鏈域 TD; TD gM; /g0不用,算法描述 輸入頂點(diǎn)和弧信息，建立其鄰接表 計(jì)算每個(gè)頂點(diǎn)的入度 對其進(jìn)行拓?fù)渑判?排序過程中求頂點(diǎn)的V

24、ei 將得到的拓?fù)湫蛄羞M(jìn)棧 按逆拓?fù)湫蛄星箜旤c(diǎn)的Vli 計(jì)算每條弧的ei和li,找出ei=li的關(guān)鍵活動(dòng),7.6 最短路徑 問題提出,用帶權(quán)的有向圖表示一個(gè)交通運(yùn)輸網(wǎng)，圖中： 頂點(diǎn)表示城市 邊表示城市間的交通聯(lián)系 權(quán)表示此線路的長度或沿此線路運(yùn)輸所花的時(shí)間或費(fèi)用等 問題：從某頂點(diǎn)出發(fā)，沿圖的邊到達(dá)另一頂點(diǎn)所經(jīng)過的路徑中， 各邊上權(quán)值之和最小的一條路徑最短路徑,求從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑,13,8,13,19,21,20,迪杰斯特拉(Dijkstra)算法思想,按路徑長度遞增次序產(chǎn)生最短路徑算法： 把V分成兩組： （1）S：已求出最短路徑的頂點(diǎn)的集合 （2）V-S=T：尚未確定最短路徑的頂點(diǎn)集合 將T中頂點(diǎn)按最短路徑遞增的次序加入到S中， 保證：（1）從源點(diǎn)V0到S中各頂點(diǎn)的最短路徑長度都不大于 從V0到T中任何頂點(diǎn)的最短路徑長度 （2）每個(gè)頂點(diǎn)對應(yīng)一個(gè)距離值 S中頂點(diǎn)：從V0到此頂點(diǎn)的最短路徑長度 T中頂點(diǎn)：從V0到此頂點(diǎn)的只包括S中頂點(diǎn)作中間 頂點(diǎn)的最短路徑長度