數據結構與算法(吳躍)ch4-1)

1、4.1 圖圖引子引子右圖為一個新興小鎮(zhèn)右圖為一個新興小鎮(zhèn).其中其中3個紅色小塊為社區(qū)房屋個紅色小塊為社區(qū)房屋, 1個個白色小塊為商店白色小塊為商店. 現在要鋪現在要鋪設天然氣管道設天然氣管道, 造價和天然造價和天然氣管長度成正比氣管長度成正比. 如何鋪設如何鋪設管道使得所有房屋和商店都管道使得所有房屋和商店都通氣且造價最低通氣且造價最低? 4.1 圖圖引子引子問題1: 造價和管線長度成正比,如何表示管線長度?4.1 圖圖引子引子問題2: 如何以最少連線連通所有房屋和商店?問題3: 如何連通所有房屋和商店且造價最低?4.1 圖圖引子引子問題4: 如何用計算機技術解決現實中大量社區(qū)的最優(yōu)化管道鋪設

2、問題?4.1 圖圖引子引子思路現實問題圖形化: 社區(qū)(房屋,商店)為點, 連通的點之間用線表示,點之間距離(管線長度)用權值表示,得到一個有權圖計算機存儲圖形數據: 存儲點,線,權值最優(yōu)管線問題分析: 求連通圖的最小權值和解決算法思路: ? 4.1 圖圖引子引子深入思考:有哪些解決方案? 哪個方案更優(yōu)? 如何分析算法優(yōu)劣?這種解決方案還可以解決哪種類型的實際問題?4.1 圖的定義和術語v圖(Graph)圖G是由兩個集合V(G)和E(G)組成的,記為G=(V,E)其中：V(G)是頂點的非空有限集 E(G)是邊的有限集合，邊是頂點的無序對或有序對v有向圖有向圖G是由兩個集合V(G)和E(G)組成的

3、 其中：V(G)是頂點的非空有限集 E(G)是有向邊（也稱?。┑挠邢藜希∈琼旤c的有序對，記為，v,w是頂點，v為弧尾，w為弧頭v無向圖無向圖G是由兩個集合V(G)和E(G)組成的 其中：V(G)是頂點的非空有限集 E(G)是邊的有限集合，邊是頂點的無序對，記為（v,w）或（w,v)，并且（v,w)=(w,v)例245136G1圖G1中：V(G1)=1,2,3,4,5,6 E(G1)=, , , , , , 例157324G26圖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)v有向完全圖

4、n個頂點的有向圖最大邊數是n(n-1)v無向完全圖n個頂點的無向圖最大邊數是n(n-1)/2v權與圖的邊或弧相關的數叫v網帶權的圖叫v子圖如果圖G(V,E)和圖G(V,E),滿足：lVVlEE 則稱G為G的子圖v鄰接點對于無向圖G(V,E),如果邊(v,v) E,則稱v和v互為鄰接點。即：v和v相鄰接。v依附邊(v,v) 依附于頂點v和v。v相關聯邊(v,v) 和頂點v和v相關聯。v頂點的度l無向圖中，頂點的度為與每個頂點相連的邊數l有向圖中，頂點的度分成入度與出度u入度：以該頂點為頭的弧的數目u出度：以該頂點為尾的弧的數目v如果頂點vi的度記為TD(vi)，則有n個頂點，e條邊或弧的圖，滿足

5、：v路徑路徑是頂點的序列V=Vi0,Vi1,Vin，滿足(Vij-1,Vij)E 或 E,(1jn)niivTD1)(21ev路徑長度沿路徑邊的數目或沿路徑各邊權值之和v回路/環(huán)第一個頂點和最后一個頂點相同的路徑叫v簡單路徑序列中頂點不重復出現的路徑叫v簡單回路/簡單環(huán)除了第一個頂點和最后一個頂點外，其余頂點不重復出現的回路叫v連通在無向圖中，從頂點V到頂點W有一條路徑，則說V和W是連通的v連通圖圖中任意兩個頂點都是連通的叫v連通分量非連通圖的每一個連通部分叫v強連通圖有向圖中，如果對每一對（Vi,Vj）V, ViVj,從Vi到Vj 和從Vj到 Vi都存在路徑，則稱G是v強連通分量有向圖中的極

6、大強連通子圖叫v生成樹一個連通圖的生成樹是一個極小連通子圖，它含有圖中的全部頂點，但只有足以構成一棵樹的n-1條邊例213213有向完全圖無向完全圖356例245136圖與子圖例245136G1頂點2入度：1 出度：3頂點4入度：1 出度：0例157324G26頂點5的度：3頂點2的度：4例157324G26例245136G1路徑：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連通圖例2451

7、36強連通圖356例非連通圖例2451364.2 圖的存儲結構多重鏈表例G12413例15324G2V1V2 V4 V3 V1 V2 V4 V5 V3鄰接矩陣表示頂點間相聯關系的矩陣v定義：設G=(V,E)是有n1個頂點的圖，G的鄰接矩陣A是具有以下性質的n階方陣，其它0E(G)v,v或)v,(v若1,jijijiA例G12413例15324G200110001011101010101010100001100000000110v特點：l無向圖的鄰接矩陣對稱，可壓縮存儲；有n個頂點的無向圖需存儲空間為n(n+1)/2l有向圖鄰接矩陣不一定對稱；有n個頂點的有向圖需存儲空間為nl無向圖中頂點Vi的

8、度TD(Vi)是鄰接矩陣A中第i行元素之和l有向圖中，u頂點Vi的出度是A中第i行元素之和u頂點Vi的入度是A中第i列元素之和l網絡的鄰接矩陣可定義為：ijij,(v ,v )v ,vE(G) , ijA i j若或，其它5735487214263816例1452375318642關聯矩陣表示頂點與邊的關聯關系的矩陣v定義：設G=(V,E)是有n1個頂點，e0條邊的圖，G的關聯矩陣A是具有以下性質的ne階矩陣為頭邊相連，且頂點與邊不相連頂點與為尾邊相連，且頂點與有向圖：ijijiijijiA, 1, 0, 1,邊不相連頂點與，邊相連頂點與，無向圖：jijijiA01,1100011000011

9、0114321例G124131234例15324G2123456110000000110011100101001000011432156例BDAC123456ABCD432156101011110000011100000111v特點l關聯矩陣每列只有兩個非零元素，是稀疏矩陣；n越大，零元素比率越大l無向圖中頂點Vi的度TD(Vi)是關聯矩陣A中第i行元素之和l有向圖中，u頂點Vi的出度是A中第i行中“1”的個數u頂點Vi的入度是A中第i行中“-1”的個數鄰接表v實現：為圖中每個頂點建立一個單鏈表，第i個單鏈表中的結點表示依附于頂點Vi的邊（有向圖中指以Vi為尾的?。﹖ypedef struct

10、 node int adjvex; /鄰接點域，存放與Vi鄰接的點在表頭數組中的位置 struct node *next; /鏈域，指示下一條邊或弧JD;adjvex next表頭接點：typedef struct tnode int vexdata; /存放頂點信息 struct node *firstarc; /指示第一個鄰接點TD;TD gaM; /ga0不用vexdata firstarc例G1bdac例aecbdG21234acdbvexdata firstarc 3 2 4 1adjvex next1234acdbvexdata firstarc 4 2 1 2adjvex nex

11、t5e 4 3 5 1 5 3 2 3v特點l無向圖中頂點Vi的度為第i個單鏈表中的結點數l有向圖中u頂點Vi的出度為第i個單鏈表中的結點個數u頂點Vi的入度為整個單鏈表中鄰接點域值是i的結點個數l逆鄰接表：有向圖中對每個結點建立以Vi為頭的弧的單鏈表例G1bdac1234acdbvexdata firstarc 4 1 1 3adjvex next鄰接矩陣與鄰接表的對比 對于n個頂點、e條邊，鄰接矩陣需要nn矩陣（有向圖） 或n（n+1）/2(無向圖壓縮存儲)個存儲單元，鄰接表需要n個頭節(jié)點和2e個表節(jié)點（無向圖），有向圖需要n個頭節(jié)點和e個表節(jié)點。在邊稀疏情況下（en(n-1)/2），鄰接

12、表比鄰接矩陣節(jié)省存儲空間。要判定任意兩個頂點（vi和vj）之間是否有邊或弧相連，鄰接表需要搜索第i個或第j個鏈表，不如鄰接矩陣方便。有向圖的十字鏈表表示法弧結點：typedef struct arcnode int tailvex, headvex; /弧尾、弧頭在表頭數組中位置 struct arcnode *hlink；/指向弧頭相同的下一條弧 struct arcnode *tlink; /指向弧尾相同的下一條弧AD;tailvex headvex hlink tlink頂點結點：typedef struct dnode int data; /存與頂點有關信息 struct arcnode *firstin；/指向以該頂點為弧頭的第一個弧結點 struct arcnode *firstout; /指向以該頂點為弧尾的第一個弧結點DD;DD gM; /g0不用data firstin firstout例bdacab cd1234 1 3 1 2 3 4 3 1 4 3 4 2 4 1無向圖的鄰接多重表表示法頂點結點：typedef struct dnode int data; /存與頂點有關的信息 struct node *firstedge; /指向第一條依附于該頂點的邊DD;DD gaM; /ga0不用data