數(shù)據(jù)結構（Python Java）（微課版） 課件 6.1 圖的概念

數(shù)據(jù)結構與算法設計圖的相關術語圖的存儲結構6.1圖的概念圖(Graph)G=(V，E)V是非空有限集合，其元素稱為頂點E是邊的集合,頂點偶對稱為邊圖的相關術語有向圖G1(b)無向圖G2有向圖G1=(V1，E1)V1={v1，v2，v3，v4}E1={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}弧有序的頂點偶對：<x，y>

有向圖G1XY弧尾弧頭無向圖G2=(V2，E2)V2={v1，v2，v3，v4，v5}E2={(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)}邊無序的頂點偶對(x，y)(b)無向圖G2完全圖(completedgraph)無向圖，邊的取值范圍是0到n(n-1)/2有n(n-1)/2條邊的無向圖有向圖，邊的取值范圍是0到n(n-1)有n(n-1)條弧的有向圖鄰接點(adjacent)無向圖G=(V，E)，若邊(v，v’)∈E頂點v和v’互為鄰接點，即v和v’相鄰接邊(v,v’)與頂點v,v’相關聯(lián)有向圖G=(V,E)，如果邊<v,v’>∈E頂點v鄰接到v’,或v’鄰接于v弧<v,v’>與頂點v,v’相關聯(lián)無向圖度與頂點v相關聯(lián)的邊數(shù)有向圖入度出度頂點v的度為：TD(v)=ID(v)+OD(v)有n個頂點，e條邊或弧的圖，滿足關系:子圖

假設有兩個圖G=(V，E)G'=(V'，E')如果V'包含于V，E'包含于E，則稱G'是G的子圖(b)G2的子圖(a)G1的子圖G1(b)

G2路徑在無向圖中,若存在一個頂點序列 vi,vp1,vp2,…,vpm，vj使得(vi,vp1)、(vp1,vp2),...,(vpm,vj)∈E則稱頂點vi到vj存在一條路徑如果G是有向圖，則路徑也是有向的頂點序列應滿足<vi,vp1>,<vp1,vp2>,...,<vpm,vj>∈E路徑的長度路徑上的邊的或弧的數(shù)目簡單路徑頂點不重復出現(xiàn)的路徑稱為簡單路徑回路第一個頂點和最后一個頂點相同的路徑稱為回路或環(huán)簡單回路除了第一頂點和最后一個頂點之外，其余頂點不重復出現(xiàn)的回路權(weight)在圖的每條邊上加上一個數(shù)字作權網(wǎng)(network)帶權的圖稱為網(wǎng)鄰接矩陣鄰接矩陣是表示頂點間相鄰關系的矩陣若G是一個具有n頂點的圖則G的鄰接矩陣是如下定義的n×n矩陣：圖的存儲結構無向圖的鄰接矩陣對稱，可壓縮存儲有n個頂點的無向圖需存儲空間為n(n+1)/2有向圖的鄰接矩陣不一定對稱有n個頂點的有向圖需存儲空間為n2無向圖中頂點Vi的度TD(Vi)是鄰接矩陣A中第i行元素之和有向圖中頂點Vi的出度是A中第i行元素之和頂點Vi的入度是A中第i列元素之和鄰接矩陣的特點網(wǎng)的鄰接矩陣定義：網(wǎng)的鄰接矩陣頂點表頂點表的每個結點中指針域指向邊表的第一個結點數(shù)據(jù)域存儲頂點的名稱或其它信息頂點表的每個結點，相當于邊表頭結點邊表把同一個頂點發(fā)出的邊鏈接在同一個鏈表中，鏈表的每一個結點代表一條邊邊表結點中保存著與某頂點相關聯(lián)的另一頂點，和指向下一個表結點的指針圖的鄰接表表示法鄰接表邊表結點vexdatafirstarcadjvexnext頂點表結點圖的鄰接表表示法圖的鄰接表表示法有向圖的鄰接表鄰接表V1V2V4V5V3V7V6V8在弧結點中有四個域：尾域(tailvex)和頭域(headvex)分別指示弧尾和弧頭這兩個頂點在圖中的編號。鏈域(hlink)：指向弧頭相同的下一條弧。鏈域(tlink)：指向指向弧尾相同的下一條弧。十字鏈表tailvexheadvexhlinktlink弧頭相同的弧在同一鏈表上，弧尾相同的弧也是在同一鏈表上。它們的頭結點即為頂點結點，它由三個域組成data域存儲和頂點相關的信息firstin域和firstout域分別指向以該頂點為弧頭或弧尾的第一個弧結點。十字鏈表datafirstinfirstout十字鏈表tailvexheadvexhlinktlinkdatafirstinfirstout用一維數(shù)組存儲圖中所有的邊每個元素用于存儲一條邊的起點、終點和權(對于無向圖，可選定邊的任一端點為起點或終點)各