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

1、有向圖及無向圖的比較研究知識結(jié)構(gòu) 圖的定義 無向圖與有向圖 無向圖與有向圖異同點圖圖（圖（GraphGraph）是一種較線性表和樹更為復雜的非線性結(jié)構(gòu)。是對結(jié)點的前趨和后繼個數(shù)不加限制的數(shù)據(jù)結(jié)構(gòu)，用來描述元素之間描述元素之間“多對多”的關(guān)系。的關(guān)系。一一 圖的定義圖的定義 圖圖G G由兩個集合構(gòu)成，記作由兩個集合構(gòu)成，記作G=(V,E) G=(V,E) 其中其中V V是頂點的非空有限集是頂點的非空有限集合，合，E E是邊的有限集合，其中邊是頂點的無序?qū)蛴行驅(qū)?。是邊的有限集合，其中邊是頂點的無序?qū)蛴行驅(qū)?。G1=(V1,E1)G1=(V1,E1)V1=vV1=v0 0 ,v ,v1 1

2、,v,v2 2,v,v3 3,v,v4 4 E1=(vE1=(v0 0,v,v1 1),(v),(v0 0,v,v3 3),(v),(v1 1,v,v2 2),(v),(v1 1,v,v4 4),(v),(v2 2,v,v3 3)(v)(v2 2,v,v4 4)無序?qū)o序?qū)?v(vi i,v,vj j) )：用連接頂點用連接頂點v vi i、v vj j的線段的線段表示，稱為表示，稱為無向邊無向邊； V0V0 V4V4 V3V3 V1V1 V2V2例例G1 G1 圖示圖示G2 G2 圖示圖示有序?qū)τ行驅(qū) ：用以為用以為v vi i起點、以起點、以v vj j為終點為終點的有向線段表示，稱為的

3、有向線段表示，稱為有向有向邊或??；邊或弧； V0V0 V1V1 V2V2 V3V3G2=G2=V2=vV2=v0 0 v v1 1,v,v2 2,v,v3 3 E2=vE2= , v, , , , 有向圖和無向圖有向圖和無向圖在圖中，若用箭頭標明了邊是有方向性的，則稱這樣在圖中，若用箭頭標明了邊是有方向性的，則稱這樣的圖為有向圖，否則稱為無向圖。的圖為有向圖，否則稱為無向圖。在無向圖中，一條邊（在無向圖中，一條邊（x,y）與（）與（y,x）表示的結(jié)果相）表示的結(jié)果相同，用圓括號表示，在有向圖中，一條邊同，用圓括號表示，在有向圖中，一條邊與與表示的結(jié)果不相同，故用尖括號表示。表示的結(jié)果不相同，故

4、用尖括號表示。表表示從頂點示從頂點x發(fā)向頂點發(fā)向頂點y的邊，的邊，x為始點，為始點，y為終點。為終點。 V0V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3有向圖：有向圖：無向圖：無向圖：完全圖完全圖:圖圖G G中的每條邊都是有方向的；中的每條邊都是有方向的；圖圖G G中的每條邊都是無方向的；中的每條邊都是無方向的；圖圖G G任意兩個頂點都有一條邊相連任意兩個頂點都有一條邊相連接；接；若若 n 個頂點的無向圖有個頂點的無向圖有 n(n-1)/2 條邊條邊, 稱為稱為無向完全圖無向完全圖若若 n 個頂點的有向圖有個頂點的有向圖有n(n-1) 條邊條邊, 稱為稱

5、為有有向完全圖向完全圖圖的應用舉例：圖的應用舉例：例例1 1 交通圖（公路、鐵路）交通圖（公路、鐵路） 頂點：地點頂點：地點 邊：連接地點的公路邊：連接地點的公路 交通圖中的有單行道雙行道，分別用有向邊、無向交通圖中的有單行道雙行道，分別用有向邊、無向邊表示；邊表示；例例2 2 電路圖電路圖 頂點：元件頂點：元件 邊：連接元件之間的線路邊：連接元件之間的線路例例3 3 通訊線路圖通訊線路圖 頂點：地點頂點：地點 邊：地點間的連線邊：地點間的連線例例4 4 各種流程圖各種流程圖 如產(chǎn)品的生產(chǎn)流程圖如產(chǎn)品的生產(chǎn)流程圖 頂點：工序頂點：工序 邊：各道工序之間的順序關(guān)系邊：各道工序之間的順序關(guān)系 V0

6、V0 V4V4 V3V3 V1V1 V2V2 V0V0 V1V1 V2V2 V3V3異同點證明：證明：若是完全有向圖，則若是完全有向圖，則n個頂點中個頂點中的每個頂點都有一條弧指向其它的每個頂點都有一條弧指向其它n-1個個頂點頂點, 因此總邊數(shù)因此總邊數(shù)=n(n-1)證明：證明：從可以直接推論出無向完全圖的從可以直接推論出無向完全圖的邊數(shù)邊數(shù)因為無方向，兩弧合并為一邊，因為無方向，兩弧合并為一邊，所以邊數(shù)減半，總邊數(shù)為所以邊數(shù)減半，總邊數(shù)為n(n-1)/2。12341234 圖的鄰接表表示圖的鄰接表表示 圖的鄰接表存儲方法是一種順序分配與鏈式分配相結(jié)合圖的鄰接表存儲方法是一種順序分配與鏈式分配

7、相結(jié)合的存儲方法，它包括兩部分的存儲方法，它包括兩部分：邊表和頂點表。：邊表和頂點表。邊表是單鏈表，用來存放邊的信息；邊表是單鏈表，用來存放邊的信息；頂點表是數(shù)組，主要用來存放頂點本身的數(shù)據(jù)信息和頂點表是數(shù)組，主要用來存放頂點本身的數(shù)據(jù)信息和該頂點鄰接點的位置。該頂點鄰接點的位置。 vertex link next adjvex weight next 邊結(jié)點邊結(jié)點頂點結(jié)點頂點結(jié)點1 1 無向圖的鄰接表無向圖的鄰接表頂點：通常按編號順序?qū)㈨旤c數(shù)據(jù)存頂點：通常按編號順序?qū)㈨旤c數(shù)據(jù)存儲在一維數(shù)組中；儲在一維數(shù)組中；關(guān)聯(lián)同一頂點的邊：用線性鏈表存儲關(guān)聯(lián)同一頂點的邊：用線性鏈表存儲該結(jié)點表示邊該結(jié)點表

8、示邊（Vi VjVi Vj）, ,其中的其中的1 1是是VjVj在一維數(shù)組中的位置在一維數(shù)組中的位置例例 V0V0 V4V4 V3V3 V1V1 V2V22 2 0 0 1 1 2 2 3 3 4 4m-1m-1V0V0V1V1V2V2V3V3V4V41 13 34 42 22 21 11 10 00 03 34 4下標下標 編號編號 linklink2 2 有向圖的鄰接表和逆鄰接表有向圖的鄰接表和逆鄰接表1 1）有向圖的鄰接表）有向圖的鄰接表頂點：用一維數(shù)組存儲（按編號順序）頂點：用一維數(shù)組存儲（按編號順序）以同一頂點為起點的弧：用線性鏈表存儲以同一頂點為起點的?。河镁€性鏈表存儲類似于無向圖

9、的鄰接表，類似于無向圖的鄰接表，所不同的是：所不同的是：以同一頂點為起點的弧：以同一頂點為起點的弧：用線性鏈表存儲用線性鏈表存儲下標下標 編號編號 link link V0V0V1V1V2V2V3V31 12 23 30 0 0 1 2 3m-1例例 V0V0 V1V1 V2V2 V3V32 2）有向圖的逆鄰接表）有向圖的逆鄰接表頂點：用一維數(shù)組存儲（按編號順序）頂點：用一維數(shù)組存儲（按編號順序）以同一頂點為終點的?。河镁€性鏈表存儲以同一頂點為終點的?。河镁€性鏈表存儲V0V0V1V1V2V2V3V3 0 1 2 3m-10 00 02 23 3 類似于有向圖的鄰接表，類似于有向圖的鄰接表，所不

10、同的是：所不同的是：以同一頂點為終點弧：以同一頂點為終點?。河镁€性鏈表存儲用線性鏈表存儲例例 V0V0 V1V1 V2V2 V3V32 從無向圖的鄰接表可以得到如下結(jié)論從無向圖的鄰接表可以得到如下結(jié)論 1 1）在）在G G鄰接表中，同一條邊對應兩個結(jié)點，鄰接表中，同一條邊對應兩個結(jié)點，所有鏈表中結(jié)所有鏈表中結(jié)點數(shù)目的一半為圖中邊數(shù)；點數(shù)目的一半為圖中邊數(shù)； 2）頂點）頂點v的度：等于的度：等于v對應線性鏈表的長度；對應線性鏈表的長度； 3）判定兩頂點）判定兩頂點v v ，u u是否鄰接：要看是否鄰接：要看v v對應線性鏈表中有對應線性鏈表中有無對應的結(jié)點無對應的結(jié)點 4 4）在）在G G中增減

11、邊：要在兩個單鏈表插入、刪除結(jié)點；中增減邊：要在兩個單鏈表插入、刪除結(jié)點； 5 5）設存儲頂點的一維數(shù)組大小為）設存儲頂點的一維數(shù)組大小為m(mm(m 圖的頂點數(shù)圖的頂點數(shù)n), n), 圖圖的邊數(shù)為的邊數(shù)為e e，G G占用存儲空間為：占用存儲空間為：m+2m+2* *e e。G G占用存儲空間與占用存儲空間與 G G 的頂點數(shù)、邊數(shù)均有關(guān)；的頂點數(shù)、邊數(shù)均有關(guān)；3 從有向圖的鄰接表可以得到如下結(jié)論從有向圖的鄰接表可以得到如下結(jié)論（1）第）第i 個鏈表中結(jié)點數(shù)目為頂點個鏈表中結(jié)點數(shù)目為頂點i的出度；的出度；（2）所有鏈表中結(jié)點數(shù)目為圖中弧數(shù)；）所有鏈表中結(jié)點數(shù)目為圖中弧數(shù)；（3）占用的存儲單

12、元數(shù)目為）占用的存儲單元數(shù)目為n+e 。從有向圖的鄰接表可知，不能求出頂點的入度。為此，從有向圖的鄰接表可知，不能求出頂點的入度。為此，我們必須另外建立有向圖的逆鄰接表，以便求出每一我們必須另外建立有向圖的逆鄰接表，以便求出每一個頂點的入度。個頂點的入度。適用于邊稀疏的圖適用于邊稀疏的圖鄰接矩陣：鄰接矩陣：A.Edge =（ v1 v2 v3 v4 v5 ）v1v2v3v4v50 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 0頂點表：頂點表：無向圖的鄰接矩陣如何表示？無向圖的鄰接矩陣如何表示？v1v2v3v5v4v40 0 0 0 00 0 0 0 00

13、 0 0 0 00 0 0 0 00 0 0 0 00 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 0有向圖的鄰接矩陣如何表示？有向圖的鄰接矩陣如何表示？有向圖的鄰接矩陣有向圖的鄰接矩陣可能是不對稱可能是不對稱的。的。頂點頂點v vi i的的出度出度= =第第i i行元素之和行元素之和， OD(v vi i )= A.Edge i j 頂點頂點v vi i的的入度入度= =第第i i列元素之和列元素之和。 ID(v vi i )= A.Edge j i 頂點的頂點的度度= =第第i i行元素之和行元素之和+ +第第i i列元素之和列元素之和, , 即：即：TD( v vi i ) = OD( vi ) + ID( vi )v1v2v3v4鄰接矩陣：鄰接矩陣：A.Edge =( v1 v2 v3 v4 )v1v2v3v40 0 0 00 0 0 0 0 0