《圖的定義和術(shù)語(yǔ)》PPT課件

《《圖的定義和術(shù)語(yǔ)》PPT課件》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第6章圖6.1圖的定義和術(shù)語(yǔ)6.2圖的存儲(chǔ)結(jié)構(gòu)6.3圖的遍歷6.4最小生成樹(shù)6.5最短路徑6.6拓?fù)渑判?.7典型題例6.8實(shí)訓(xùn)例題6.1圖的定義和術(shù)語(yǔ)6．1．1圖的定義圖(Graph)——圖G是由兩個(gè)集合V(G)和E(G)組成的,記為G=(V,E)其中：V(G)是頂點(diǎn)的非空窮集合有窮集合E(G)是用頂點(diǎn)對(duì)表示的邊（Edge）的有窮集合，可以為空。無(wú)向圖——若圖G中表示邊的頂點(diǎn)對(duì)是無(wú)序的（稱(chēng)無(wú)向邊），則稱(chēng)圖G為無(wú)向圖。通常用(vi，vj)表示頂點(diǎn)vi和vj間的無(wú)向邊。有向圖——若圖G中表示邊的頂

2、點(diǎn)對(duì)是有序的（稱(chēng)有向邊），則稱(chēng)圖G為有向圖。通常用表示從頂點(diǎn)vi到頂點(diǎn)vj的有向邊，有向邊也稱(chēng)為弧，頂點(diǎn)vi稱(chēng)為弧尾（或初始點(diǎn)），頂點(diǎn)vj稱(chēng)為弧頭（或終端點(diǎn)），用由弧尾指向弧頭的箭頭形象地表示弧。例如圖6.1所示，G1是無(wú)向圖，其中，V={v0，v1，v2，v3，v4}，E={(v0，v1)，(v0，v3)，(v0，v4)，(v1，v4)，(v1，v2)，(v2，v4)，(v3，v4)}；G2是有向圖，其中，V={v0，v1，v2，v3}，E={，

3、，v2>，，}。(a)圖G1(b)圖G2圖6.1圖的示例v4v3v0v3v0v1v2v1v26.1.2圖的基本術(shù)語(yǔ)鄰接點(diǎn)——在無(wú)向圖G＝(V，E)中，若邊(vi，vj)∈E，則稱(chēng)頂點(diǎn)vi和vj互為鄰接點(diǎn)（Adjacent），或vi和vj相鄰接，并稱(chēng)邊(vi，vj)與頂點(diǎn)vi和vj相關(guān)聯(lián)，或者說(shuō)邊(vi，vj)依附于頂點(diǎn)vi，vj。在有向圖G＝（V，E）中，若弧E，則稱(chēng)頂點(diǎn)vi鄰接到頂點(diǎn)vj，頂點(diǎn)vj鄰接自頂點(diǎn)vi，并稱(chēng)弧和頂點(diǎn)vi，vj相關(guān)

4、聯(lián)。頂點(diǎn)的度、入度和出度——頂點(diǎn)vi的度（Degree）是圖中與vi相關(guān)聯(lián)的邊的數(shù)目，記為T(mén)D(vi)。對(duì)于有向圖，頂點(diǎn)vi的度等于該頂點(diǎn)的入度和出度之和，即TD（vi）＝ID（vi）＋OD（vi）。其中，頂點(diǎn)vi的入度（InDegree）ID（vi），是以vi為弧頭的弧的數(shù)目；頂點(diǎn)vi的出度（OutDegree）OD（vi）是以vi為弧尾的弧的數(shù)目。完全圖、稠密圖、稀疏圖——若無(wú)向圖中有n(n–1)條邊，即圖中每對(duì)頂點(diǎn)之間都有一條邊，則稱(chēng)該無(wú)向圖為無(wú)向完全圖。若有向圖中有n(n–1)條弧，即圖

5、中每對(duì)頂點(diǎn)之間都有方向相反的兩條弧，則稱(chēng)該有向圖為有向完全圖。有很少條邊或?。╡

6、是有向的，且〈vij–1，vij〉∈E，１≤j≤m。路徑上邊或弧的數(shù)目稱(chēng)為路徑長(zhǎng)度。如果路徑的起點(diǎn)和終點(diǎn)相同（即v＝v‘），則稱(chēng)此路徑為回路或環(huán)（Cycle）。序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑稱(chēng)為簡(jiǎn)單路徑。除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)之外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路，稱(chēng)為簡(jiǎn)單回路或簡(jiǎn)單環(huán)。(a)圖6.1中G1的子圖v0v4v0v1v2v4v3v0v1v0v1v0v3v0v1v2(b)圖6.1中G2的子圖圖6.3子圖示例連通圖、連通分量：在無(wú)向圖G中，若從頂點(diǎn)vi到頂點(diǎn)vj(i≠j)有路徑相通，則稱(chēng)vi和

7、vj是連通的。如果圖中任意兩個(gè)頂點(diǎn)vi和vj(i≠j)都是連通的，則稱(chēng)該圖是連通圖（ConnectedGraph）。無(wú)向圖中極大連通子圖稱(chēng)為連通分量（ConnectedComponent）。強(qiáng)連通圖、強(qiáng)連通分量：在有向圖中，若任意兩個(gè)頂點(diǎn)vi和vj都連通，即從vi到vj和從vj到vi都有路徑相通，則稱(chēng)該有向圖為強(qiáng)連通圖，例如圖6.2中G4就是強(qiáng)連通圖。有向圖中的極大強(qiáng)連通子圖稱(chēng)為該有向圖的強(qiáng)連通分量。v5圖6.4無(wú)向圖及其連通分量v4v3v0v1v2(a)無(wú)向圖G5v7v6(b)G5的三個(gè)連通分

8、量v4v3v0v1v2v5v7v6v3v0v1v2圖6.5有向圖G2的兩個(gè)強(qiáng)連通分量(a)(b)權(quán)、網(wǎng)：圖的每條邊或弧上常常附上一個(gè)具有一定意義的數(shù)值，這種與邊或弧相關(guān)的數(shù)值稱(chēng)為該邊（弧）的權(quán)（Weight）。邊或弧上帶權(quán)的連通圖稱(chēng)為網(wǎng)（Network）。如圖6.6所示。10706030205090圖6.6網(wǎng)G6示例v1v4v0v2v36．2圖的存儲(chǔ)結(jié)構(gòu)6．2．1鄰接矩陣1．鄰接矩陣這種存儲(chǔ)結(jié)構(gòu)采用兩個(gè)數(shù)組來(lái)表示圖：一個(gè)是一維數(shù)組，存儲(chǔ)圖中的所有頂點(diǎn)的信息；另一個(gè)是二維數(shù)組即鄰接矩陣，存儲(chǔ)頂點(diǎn)之