有向圖及無向圖的比較研究.ppt

《有向圖及無向圖的比較研究.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、有向圖及無向圖的比較研究知識(shí)結(jié)構(gòu)圖的定義無向圖與有向圖無向圖與有向圖異同點(diǎn)圖圖（Graph）是一種較線性表和樹更為復(fù)雜的非線性結(jié)構(gòu)。是對(duì)結(jié)點(diǎn)的前趨和后繼個(gè)數(shù)不加限制的數(shù)據(jù)結(jié)構(gòu)，用來描述元素之間“多對(duì)多”的關(guān)系。一圖的定義圖G由兩個(gè)集合構(gòu)成，記作G=(V,E)其中V是頂點(diǎn)的非空有限集合，E是邊的有限集合，其中邊是頂點(diǎn)的無序?qū)蛴行驅(qū)稀1=(V1,E1)V1={v0,v1,v2,v3,v4}E1={(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3)(v2,v4)}無序?qū)?vi,vj)：用連接頂點(diǎn)vi、vj的線段表示，稱為無向邊；

2、V0V4V3V1V2例G1圖示G2圖示有序?qū)?vi,vj>：用以為vi起點(diǎn)、以vj為終點(diǎn)的有向線段表示，稱為有向邊或?。籚0V1V2V3G2=V2={v0v1,v2,v3}E2={,,,}有向圖和無向圖在圖中，若用箭頭標(biāo)明了邊是有方向性的，則稱這樣的圖為有向圖，否則稱為無向圖。在無向圖中，一條邊（x,y）與（y,x）表示的結(jié)果相同，用圓括號(hào)表示，在有向圖中，一條邊與表示的結(jié)果不相同，故用尖括號(hào)表示。表示從頂點(diǎn)x發(fā)向頂點(diǎn)y的邊，x為始點(diǎn)，y為終點(diǎn)。V0V4V3V

3、1V2V0V1V2V3有向圖：無向圖：完全圖:圖G中的每條邊都是有方向的；圖G中的每條邊都是無方向的；圖G任意兩個(gè)頂點(diǎn)都有一條邊相連接；若n個(gè)頂點(diǎn)的無向圖有n(n-1)/2條邊,稱為無向完全圖若n個(gè)頂點(diǎn)的有向圖有n(n-1)條邊,稱為有向完全圖圖的應(yīng)用舉例：例1交通圖（公路、鐵路）頂點(diǎn)：地點(diǎn)邊：連接地點(diǎn)的公路交通圖中的有單行道雙行道，分別用有向邊、無向邊表示；例2電路圖頂點(diǎn)：元件邊：連接元件之間的線路例3通訊線路圖頂點(diǎn)：地點(diǎn)邊：地點(diǎn)間的連線例4各種流程圖如產(chǎn)品的生產(chǎn)流程圖頂點(diǎn)：工序邊：各道工序之間的順序關(guān)系V0V4V3V1V2V0V1V2V3異同點(diǎn)證明：若是

4、完全有向圖，則n個(gè)頂點(diǎn)中的每個(gè)頂點(diǎn)都有一條弧指向其它n-1個(gè)頂點(diǎn),因此總邊數(shù)=n(n-1)證明：從①可以直接推論出無向完全圖的邊數(shù)——因?yàn)闊o方向，兩弧合并為一邊，所以邊數(shù)減半，總邊數(shù)為n(n-1)/2。②完全無向圖有n(n-1)/2條邊。①完全有向圖有n(n-1)條邊。12341234圖的鄰接表表示圖的鄰接表存儲(chǔ)方法是一種順序分配與鏈?zhǔn)椒峙湎嘟Y(jié)合的存儲(chǔ)方法，它包括兩部分：邊表和頂點(diǎn)表。邊表是單鏈表，用來存放邊的信息；頂點(diǎn)表是數(shù)組，主要用來存放頂點(diǎn)本身的數(shù)據(jù)信息和該頂點(diǎn)鄰接點(diǎn)的位置。adjvexweightnext邊結(jié)點(diǎn)頂點(diǎn)結(jié)點(diǎn)1無向圖的鄰接表頂點(diǎn)：通常按編號(hào)

5、順序?qū)㈨旤c(diǎn)數(shù)據(jù)存儲(chǔ)在一維數(shù)組中；關(guān)聯(lián)同一頂點(diǎn)的邊：用線性鏈表存儲(chǔ)該結(jié)點(diǎn)表示邊（ViVj）,其中的1是Vj在一維數(shù)組中的位置例V0V4V3V1V2201234m-1V0V1V2V3V413422110034下標(biāo)編號(hào)link2有向圖的鄰接表和逆鄰接表1）有向圖的鄰接表頂點(diǎn)：用一維數(shù)組存儲(chǔ)（按編號(hào)順序）以同一頂點(diǎn)為起點(diǎn)的?。河镁€性鏈表存儲(chǔ)類似于無向圖的鄰接表，所不同的是：以同一頂點(diǎn)為起點(diǎn)的弧：用線性鏈表存儲(chǔ)下標(biāo)編號(hào)linkV0V1V2V312300123m-1例V0V1V2V32）有向圖的逆鄰接表頂點(diǎn)：用一維數(shù)組存儲(chǔ)（按編號(hào)順序）以同一頂點(diǎn)為終點(diǎn)的?。河镁€性鏈表存

6、儲(chǔ)V0V1V2V30123m-10023類似于有向圖的鄰接表，所不同的是：以同一頂點(diǎn)為終點(diǎn)?。河镁€性鏈表存儲(chǔ)例V0V1V2V32．從無向圖的鄰接表可以得到如下結(jié)論1）在G鄰接表中，同一條邊對(duì)應(yīng)兩個(gè)結(jié)點(diǎn)，所有鏈表中結(jié)點(diǎn)數(shù)目的一半為圖中邊數(shù)；2）頂點(diǎn)v的度：等于v對(duì)應(yīng)線性鏈表的長度；3）判定兩頂點(diǎn)v，u是否鄰接：要看v對(duì)應(yīng)線性鏈表中有無對(duì)應(yīng)的結(jié)點(diǎn)4）在G中增減邊：要在兩個(gè)單鏈表插入、刪除結(jié)點(diǎn)；5）設(shè)存儲(chǔ)頂點(diǎn)的一維數(shù)組大小為m(m?圖的頂點(diǎn)數(shù)n),圖的邊數(shù)為e，G占用存儲(chǔ)空間為：m+2*e。G占用存儲(chǔ)空間與G的頂點(diǎn)數(shù)、邊數(shù)均有關(guān)；3．從有向圖的鄰接表可以得到如下結(jié)

7、論（1）第i個(gè)鏈表中結(jié)點(diǎn)數(shù)目為頂點(diǎn)i的出度；（2）所有鏈表中結(jié)點(diǎn)數(shù)目為圖中弧數(shù)；（3）占用的存儲(chǔ)單元數(shù)目為n+e。從有向圖的鄰接表可知，不能求出頂點(diǎn)的入度。為此，我們必須另外建立有向圖的逆鄰接表，以便求出每一個(gè)頂點(diǎn)的入度。適用于邊稀疏的圖鄰接矩陣：A.Edge=（v1v2v3v4v5）v1v2v3v4v50101010101010111010101110分析1：無向圖的鄰接矩陣是對(duì)稱的；分析2：頂點(diǎn)Vi的度＝第i行(列)中1的個(gè)數(shù)；特別：完全圖的鄰接矩陣中，對(duì)角元素為0，其余全1。頂點(diǎn)表：無向圖的鄰接矩陣如何表示？v1v2v3v5v4v4A000000000

8、00000000000000000101010101