數(shù)據(jù)結(jié)構(gòu) 第7 章 圖的定義和術(shù)語(yǔ)

《數(shù)據(jù)結(jié)構(gòu) 第7 章 圖的定義和術(shù)語(yǔ)》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、7.1圖的定義和術(shù)語(yǔ)定義：圖(Graph)是一種復(fù)雜的非線(xiàn)性數(shù)據(jù)結(jié)構(gòu)，由頂點(diǎn)集合及頂點(diǎn)間的關(guān)系（也稱(chēng)弧或邊）集合組成。可以表示為：G＝(V,{VR})其中V是頂點(diǎn)的有窮非空集合；VR是頂點(diǎn)之間關(guān)系的有窮集合，也叫做弧或邊集合?；∈琼旤c(diǎn)的有序?qū)Γ吺琼旤c(diǎn)的無(wú)序?qū)?。生成?shù)：所有頂點(diǎn)均由邊連接在一起，但不存在回路的圖。一個(gè)圖可以有許多棵不同的生成樹(shù)。注所有生成樹(shù)具有以下共同特點(diǎn)：生成樹(shù)的頂點(diǎn)個(gè)數(shù)與圖的頂點(diǎn)個(gè)數(shù)相同；生成樹(shù)是圖的極小連通子圖；一個(gè)有n個(gè)頂點(diǎn)的連通圖的生成樹(shù)有n-1條邊；生成樹(shù)中任意兩個(gè)頂點(diǎn)間的路徑是唯一的；在生成樹(shù)中再加一條邊必然形成回路。含n

2、個(gè)頂點(diǎn)n-1條邊的圖不一定是生成樹(shù)。7.2圖的存儲(chǔ)結(jié)構(gòu)7.2.1數(shù)組表示法（鄰接矩陣表示法）特點(diǎn)：無(wú)向圖的鄰接矩陣對(duì)稱(chēng)，可壓縮存儲(chǔ)；有n個(gè)頂點(diǎn)的無(wú)向圖需存儲(chǔ)空間為n(n-1)/2。有向圖鄰接矩陣不一定對(duì)稱(chēng)；有n個(gè)頂點(diǎn)的有向圖需存儲(chǔ)空間為n2，空間復(fù)雜度為O(n2)，用于稀疏圖時(shí)空間浪費(fèi)嚴(yán)重。無(wú)向圖中頂點(diǎn)vi的度TD(vi)是鄰接矩陣中第i行1的個(gè)數(shù)。有向圖中頂點(diǎn)vi的出度是鄰接矩陣中第i行1的個(gè)數(shù)。頂點(diǎn)vi的入度是鄰接矩陣中第i列1的個(gè)數(shù)。7.2.2鄰接表（類(lèi)似于樹(shù)的孩子鏈表表示法）v2v1v3v4v5G2v1v3v4v2v5012343^142^04

3、3^12^02^1特點(diǎn)：若無(wú)向圖中有n個(gè)頂點(diǎn)、e條邊，則其鄰接表需n個(gè)頭結(jié)點(diǎn)和2e個(gè)表結(jié)點(diǎn)。適宜存儲(chǔ)稀疏圖。無(wú)向圖中頂點(diǎn)vi的度為第i個(gè)單鏈表中的結(jié)點(diǎn)數(shù)。v2v1v3v4G101232^13^^0v1v3v4v2^0123^30^^2v1v3v4v2^0鄰接表逆鄰接表頂點(diǎn)vi的出度為第i個(gè)單鏈表中的結(jié)點(diǎn)個(gè)數(shù)。特點(diǎn)：頂點(diǎn)vi的入度為整個(gè)單鏈表中鄰接點(diǎn)域值是i-1的結(jié)點(diǎn)個(gè)數(shù)。找出度易，找入度難。找入度易，找出度難。頂點(diǎn)vi的入度為第i個(gè)單鏈表中的結(jié)點(diǎn)個(gè)數(shù)。頂點(diǎn)vi的出度為整個(gè)單鏈表中鄰接點(diǎn)域值是i-1的結(jié)點(diǎn)個(gè)數(shù)?；〗Y(jié)點(diǎn)abcd01237.2.3十字鏈表01

4、2002^30^31^32^23^^bdactailvexheadvexhlinktlinkdatafirstinfirstout頂點(diǎn)結(jié)點(diǎn)^^指向依附于ivex的下一條邊7.2.3鄰接多重表（無(wú)向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)）鄰接表優(yōu)點(diǎn)：容易求得頂點(diǎn)和邊的信息。缺點(diǎn)：某些操作不方便（如：刪除一條邊需找表示此邊的兩個(gè)結(jié)點(diǎn)）。鄰接多重表：每條邊用一個(gè)結(jié)點(diǎn)表示。其結(jié)點(diǎn)結(jié)構(gòu)如下：指向依附于jvex的下一條邊markivexilinkjvexjlinkinfo邊結(jié)點(diǎn)datafirstedge頂點(diǎn)結(jié)點(diǎn)存與頂點(diǎn)有關(guān)的信息指向第一條依附于該頂點(diǎn)的邊標(biāo)志域標(biāo)記此邊是否被搜索過(guò)

5、該邊依附的兩個(gè)頂點(diǎn)在表頭數(shù)組中位置0301234v2v1v3v4v5G2v1v2v3v4v50123212441^^^^^markivexilinkjvexjlinkinfo邊結(jié)點(diǎn)datafirstedge頂點(diǎn)結(jié)點(diǎn)7.2.3鄰接多重表（無(wú)向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)）7.3圖的遍歷深度優(yōu)先遍歷（Depth_FirstSearch——DFS）廣度優(yōu)先遍歷（Breadth_FristSearch——BFS）7.4.3最小生成樹(shù)構(gòu)造最小生成樹(shù)方法：方法一：普里姆(Prim)算法。方法二：克魯斯卡爾(Kruskal)算法。最小生成樹(shù)可能不惟一V1V6V5V4V3V

6、26513566425拓?fù)渑判虻姆椒ǎ涸谟邢驁D中選一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)且輸出之。從圖中刪除該頂點(diǎn)和所有以它為尾的弧。重復(fù)上述兩步，直至全部頂點(diǎn)均已輸出；或者當(dāng)圖中不存在無(wú)前驅(qū)的頂點(diǎn)為止一個(gè)AOV網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏?.5.2關(guān)鍵路徑把工程計(jì)劃表示為有向圖，用頂點(diǎn)表示事件，弧表示活動(dòng)，弧的權(quán)表示活動(dòng)持續(xù)時(shí)間。每個(gè)事件表示在它之前的活動(dòng)已經(jīng)完成，在它之后的活動(dòng)可以開(kāi)始。稱(chēng)這種有向圖為邊表示活動(dòng)的網(wǎng)絡(luò)，簡(jiǎn)稱(chēng)為AOE（ActivityOnEdge）網(wǎng)。對(duì)于AOE網(wǎng)，我們關(guān)心兩個(gè)問(wèn)題：(1)完成整項(xiàng)工程至少需要多少時(shí)間？(2)哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵？求關(guān)鍵

7、路徑步驟：求ve(i)、vl(j)求e(i)、l(i)計(jì)算l(i)-e(i)7.6最短路徑7.6.1單源點(diǎn)最短路徑（從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑）迪杰斯特拉（Dijkstra）算法：按路徑長(zhǎng)度遞增次序產(chǎn)生各頂點(diǎn)的最短路徑。7.6.2每一對(duì)頂點(diǎn)之間的最短路徑方法一：每次以一個(gè)頂點(diǎn)為源點(diǎn)，重復(fù)執(zhí)行Dijkstra算法n次。方法二：弗洛伊德(Floyd)算法算法思想：逐個(gè)頂點(diǎn)試探，從vi到vj的所有可能存在的路徑中，選出一條長(zhǎng)度最短的路徑。