武漢理工大學(xué)信息工程學(xué)院數(shù)據(jù)結(jié)構(gòu)課件ch071圖1圖的定義和存儲

第7章圖數(shù)據(jù)結(jié)構(gòu)講義-圖的定義和存儲信息工程學(xué)院魏洪濤Email:greattide@163.com第7章圖數(shù)據(jù)結(jié)構(gòu)講義-圖的定義和存儲信息工程學(xué)院1圖的定義：

圖G是由頂點集V和頂點間的關(guān)系集合E（邊的集合）組成的一種數(shù)據(jù)結(jié)構(gòu)，可以用二元組定義為：G=（V,E）。例如，對于圖7-1所示的無向圖G1和有向圖G2，它們的數(shù)據(jù)結(jié)構(gòu)可以描述為：G1=(V1,E1),其中V1={a,b,c,d},E1={(a,b),(a,c),(a,d),(b,d),(c,d)},而G2=(V2,E2)，其中V2={1,2,3},E2={<1,2>,<1,3>,<2,3>,<3,1>}。7.1圖的基本概念圖的定義：圖G是由頂點集V和頂點間的關(guān)系集合E（邊的集合）27.2圖的存貯結(jié)構(gòu)圖無法以數(shù)據(jù)元素在存儲區(qū)中的物理位置來表示元素之間關(guān)系，即圖沒有順序映象的存儲結(jié)構(gòu)。用多重鏈表表示圖，即以一個數(shù)據(jù)域和多個指針域組成的結(jié)點表示圖中一個頂點，其中數(shù)據(jù)域存儲該頂點的信息，指針域存儲指向其鄰接點的指針。常用的有鄰接矩陣、鄰接表和十字鏈表等。不管哪一種方式，它除了要存儲圖中各個頂點本身的信息外，同時還要存儲頂點與頂點之間的所有關(guān)系（邊的信息）。7.2圖的存貯結(jié)構(gòu)圖無法以數(shù)據(jù)元素在存儲區(qū)中的物理位置來3多重鏈表例G12413例15324G2V1V2^^V4^V3^^V1V2V4^V5^V3多重鏈表例G12413例15324G2V1V2^41．圖的鄰接矩陣表示在鄰接矩陣表示中，除了存放頂點本身信息外，還用一個矩陣表示各個頂點之間的關(guān)系。若（i,j）∈E(G)或〈i,j〉∈E(G),則矩陣中第i行第j列元素值為1，否則為0。圖的鄰接矩陣定義為：1若（i,j）∈E(G)或〈i,j〉∈E(G)A[i][j]=0其它情形7.2.1鄰接矩陣1．圖的鄰接矩陣表示在鄰接矩陣表示中，除了存放頂點本身信息5例如,對圖7-8所示的無向圖和有向圖的鄰接矩陣。例如,對圖7-8所示的無向圖和有向圖的鄰接矩陣。62．從無向圖的鄰接矩陣可以得出如下結(jié)論

（1）矩陣是對稱的，可壓縮存儲（上（下）三角）;（2）第i行或第i列中1的個數(shù)為頂點i的度;（3）矩陣中1的個數(shù)的一半為圖中邊的數(shù)目;（4）很容易判斷頂點i和頂點j之間是否有邊相連(看矩陣中i行j列值是否為1)。3．從有向圖的鄰接矩陣可以得出如下結(jié)論（1）矩陣不一定是對稱的;（2）第i行中1的個數(shù)為頂點i的出度;（3）第i列中1的個數(shù)為頂點i的入度;（4）矩陣中1的個數(shù)為圖中弧的數(shù)目;（5）很容易判斷頂點i和頂點j是否有弧相連.2．從無向圖的鄰接矩陣可以得出如下結(jié)論（1）矩陣是對稱的74．網(wǎng)的鄰接矩陣表示類似地可以定義網(wǎng)的鄰接矩陣為：wij若（i,j）∈E(G)或〈i,j〉∈E(G)A[i][j]=∞其它情形網(wǎng)及網(wǎng)的鄰接矩陣見下圖。4．網(wǎng)的鄰接矩陣表示類似地可以定義網(wǎng)的鄰接矩陣為：8鄰接矩陣法優(yōu)點：容易實現(xiàn)圖的操作，如：求某頂點的度、判斷頂點之間是否有邊（?。?、找頂點的鄰接點等等。鄰接矩陣法缺點：n個頂點需要n*n個單元存儲邊(弧);空間效率為O(n2)。對稀疏圖而言尤其浪費空間。鄰接矩陣法優(yōu)點：91．圖的鄰接表表示圖的鄰接表存儲方法是一種順序分配與鏈?zhǔn)椒峙湎嘟Y(jié)合的存儲方法，它包括兩部分：一部分是單鏈表，用來存放邊的信息；另一部分是數(shù)組，主要用來存放頂點本身的數(shù)據(jù)信息。adjvexweightnext邊結(jié)點頂點結(jié)點7.2.2鄰接表1．圖的鄰接表表示圖的鄰接表存儲方法是一種順序分配與鏈?zhǔn)椒?0左圖所示的無向圖G3和有向圖G4的鄰接表見右圖所示:左圖所示的無向圖G3和有向圖G4的鄰接表見右圖所示:112．從無向圖的鄰接表可以得到如下結(jié)論

（1）第i個鏈表中結(jié)點數(shù)目為頂點i的度；（2）所有鏈表中結(jié)點數(shù)目的一半為圖中邊數(shù)；（3）占用的存儲單元數(shù)目為n+2e。3．從有向圖的鄰接表可以得到如下結(jié)論（1）第i個鏈表中結(jié)點數(shù)目為頂點i的出度；（2）所有鏈表中結(jié)點數(shù)目為圖中弧數(shù)；（3）占用的存儲單元數(shù)目為n+e。從有向圖的鄰接表可知，不能求出頂點的入度。為此，我們必須另外建立有向圖的逆鄰接表，以便求出每一個頂點的入度。2．從無向圖的鄰接表可以得到如下結(jié)論（1）第i個鏈表12例：已知某網(wǎng)的鄰接（出邊）表，請畫出該網(wǎng)絡(luò)。8064125當(dāng)鄰接表的存儲結(jié)構(gòu)形成后，圖便唯一確定！例：已知某網(wǎng)的鄰接（出邊）表，請畫出該網(wǎng)絡(luò)。8064125當(dāng)13如果是無向圖，只要搜索任意一個結(jié)點的邊表。有向圖要搜索兩個結(jié)點的邊表。鄰接表的優(yōu)點：空間效率高；容易尋找頂點的鄰接點；鄰接表的缺點：判斷兩頂點間是否有邊或弧，需搜索兩結(jié)點對應(yīng)的單鏈表，沒有鄰接矩陣方便。如果是無向圖，只要搜索任意一個結(jié)點的邊表。有向圖要搜索兩個結(jié)144．圖的鄰接表數(shù)據(jù)類型描述圖的鄰接表數(shù)據(jù)類型描述如下：#defineMAXN50/*MAXN表示圖中最大頂點數(shù)*/typedefstructe_node//定義邊結(jié)點的結(jié)構(gòu){intadjvex;intweight;//邊的信息structe_node*next;}E_NODE;//指向鄰接點的指針typedefstructv_node//定義鄰接表的表頭類型{intvertex;//頂點信息

E_NODE*link;//指向“邊表”的指針}V_NODE;V_NODEhead[MAXN];4．圖的鄰接表數(shù)據(jù)類型描述圖的鄰接表數(shù)據(jù)類型描述如下：15討論：鄰接表與鄰接矩陣有什么異同之處？1.聯(lián)系：鄰接表中每個鏈表對應(yīng)于鄰接矩陣中的一行，鏈表中結(jié)點個數(shù)等于一行中非零元素的個數(shù)。2.區(qū)別：①對于任一確定的無向圖，鄰接矩陣是唯一的（行列號與頂點編號一致），但鄰接表不唯一（鏈接次序與頂點編號無關(guān)）。②鄰接矩陣的空間復(fù)雜度為O(n2),而鄰接表的空間復(fù)雜度為O(n+e)。3.

用途：鄰接矩陣多用于稠密圖的存儲（e接近n(n-1)/2)；而鄰接表多用于稀疏圖的存儲（e<<n2)討論：鄰接表與鄰接矩陣有什么異同之處？1.聯(lián)系：鄰接表中每16有向圖的十字鏈表表示法弧結(jié)點：typedefstructarcnode{inttailvex,headvex;//弧尾、弧頭在表頭數(shù)組中位置structarcnode*hlink；//指向弧頭相同的下一條弧structarcnode*tlink;//指向弧尾相同的下一條弧}AD;tailvexheadvexhlinktlink頂點結(jié)點：typedefstructdnode{intdata;//存與頂點有關(guān)信息structarcnode*firstin；//指向以該頂點為弧頭的第一個弧結(jié)點structarcnode*firstout;//指向以該頂點為弧尾的第一個弧結(jié)點}DD;DDg[M];//g[0]不用datafirstinfirstout有向圖的十字鏈表表示法弧結(jié)點：tailvexheadv17例bdacabcd123413123431434241^^^^^^^^例bdacabcd1234118無向圖的鄰接多重表表示法頂點結(jié)點：typedefstructdnode{intdata;//存與頂點有關(guān)的信息structnode*firstedge;//指向第一條依附于該頂點的邊}DD;DDga[M];//ga[0]不用datafirstedge邊結(jié)點：typedefstructnode{intmark;//標(biāo)志域intivex,jvex;//該邊依附的兩個頂點在表頭數(shù)組中位置structnode*ilink,*jlink;//分別指向依附于ivex和jvex的下一條邊}JD;markivexilinkjvexjlink無向圖的鄰接多重表表示法頂點結(jié)點：datafirste19例aecbd1234acdb5e121434323552^^^^^例aecbd1234acdb5e120作業(yè)已知如圖所示的有向圖，請給出該圖的:（1） 每個頂點的入/出度；（2） 鄰接矩陣；（3） 鄰接表；（4） 逆鄰接表；（5） 十字鏈表.作業(yè)已知如圖所示的有向圖，請給出該圖的:21第7章圖數(shù)據(jù)結(jié)構(gòu)講義-圖的定義和存儲信息工程學(xué)院魏洪濤Email:greattide@163.com第7章圖數(shù)據(jù)結(jié)構(gòu)講義-圖的定義和存儲信息工程學(xué)院22圖的定義：

圖G是由頂點集V和頂點間的關(guān)系集合E（邊的集合）組成的一種數(shù)據(jù)結(jié)構(gòu)，可以用二元組定義為：G=（V,E）。例如，對于圖7-1所示的無向圖G1和有向圖G2，它們的數(shù)據(jù)結(jié)構(gòu)可以描述為：G1=(V1,E1),其中V1={a,b,c,d},E1={(a,b),(a,c),(a,d),(b,d),(c,d)},而G2=(V2,E2)，其中V2={1,2,3},E2={<1,2>,<1,3>,<2,3>,<3,1>}。7.1圖的基本概念圖的定義：圖G是由頂點集V和頂點間的關(guān)系集合E（邊的集合）237.2圖的存貯結(jié)構(gòu)圖無法以數(shù)據(jù)元素在存儲區(qū)中的物理位置來表示元素之間關(guān)系，即圖沒有順序映象的存儲結(jié)構(gòu)。用多重鏈表表示圖，即以一個數(shù)據(jù)域和多個指針域組成的結(jié)點表示圖中一個頂點，其中數(shù)據(jù)域存儲該頂點的信息，指針域存儲指向其鄰接點的指針。常用的有鄰接矩陣、鄰接表和十字鏈表等。不管哪一種方式，它除了要存儲圖中各個頂點本身的信息外，同時還要存儲頂點與頂點之間的所有關(guān)系（邊的信息）。7.2圖的存貯結(jié)構(gòu)圖無法以數(shù)據(jù)元素在存儲區(qū)中的物理位置來24多重鏈表例G12413例15324G2V1V2^^V4^V3^^V1V2V4^V5^V3多重鏈表例G12413例15324G2V1V2^251．圖的鄰接矩陣表示在鄰接矩陣表示中，除了存放頂點本身信息外，還用一個矩陣表示各個頂點之間的關(guān)系。若（i,j）∈E(G)或〈i,j〉∈E(G),則矩陣中第i行第j列元素值為1，否則為0。圖的鄰接矩陣定義為：1若（i,j）∈E(G)或〈i,j〉∈E(G)A[i][j]=0其它情形7.2.1鄰接矩陣1．圖的鄰接矩陣表示在鄰接矩陣表示中，除了存放頂點本身信息26例如,對圖7-8所示的無向圖和有向圖的鄰接矩陣。例如,對圖7-8所示的無向圖和有向圖的鄰接矩陣。272．從無向圖的鄰接矩陣可以得出如下結(jié)論

（1）矩陣是對稱的，可壓縮存儲（上（下）三角）;（2）第i行或第i列中1的個數(shù)為頂點i的度;（3）矩陣中1的個數(shù)的一半為圖中邊的數(shù)目;（4）很容易判斷頂點i和頂點j之間是否有邊相連(看矩陣中i行j列值是否為1)。3．從有向圖的鄰接矩陣可以得出如下結(jié)論（1）矩陣不一定是對稱的;（2）第i行中1的個數(shù)為頂點i的出度;（3）第i列中1的個數(shù)為頂點i的入度;（4）矩陣中1的個數(shù)為圖中弧的數(shù)目;（5）很容易判斷頂點i和頂點j是否有弧相連.2．從無向圖的鄰接矩陣可以得出如下結(jié)論（1）矩陣是對稱的284．網(wǎng)的鄰接矩陣表示類似地可以定義網(wǎng)的鄰接矩陣為：wij若（i,j）∈E(G)或〈i,j〉∈E(G)A[i][j]=∞其它情形網(wǎng)及網(wǎng)的鄰接矩陣見下圖。4．網(wǎng)的鄰接矩陣表示類似地可以定義網(wǎng)的鄰接矩陣為：29鄰接矩陣法優(yōu)點：容易實現(xiàn)圖的操作，如：求某頂點的度、判斷頂點之間是否有邊（弧）、找頂點的鄰接點等等。鄰接矩陣法缺點：n個頂點需要n*n個單元存儲邊(弧);空間效率為O(n2)。對稀疏圖而言尤其浪費空間。鄰接矩陣法優(yōu)點：301．圖的鄰接表表示圖的鄰接表存儲方法是一種順序分配與鏈?zhǔn)椒峙湎嘟Y(jié)合的存儲方法，它包括兩部分：一部分是單鏈表，用來存放邊的信息；另一部分是數(shù)組，主要用來存放頂點本身的數(shù)據(jù)信息。adjvexweightnext邊結(jié)點頂點結(jié)點7.2.2鄰接表1．圖的鄰接表表示圖的鄰接表存儲方法是一種順序分配與鏈?zhǔn)椒?1左圖所示的無向圖G3和有向圖G4的鄰接表見右圖所示:左圖所示的無向圖G3和有向圖G4的鄰接表見右圖所示:322．從無向圖的鄰接表可以得到如下結(jié)論

（1）第i個鏈表中結(jié)點數(shù)目為頂點i的度；（2）所有鏈表中結(jié)點數(shù)目的一半為圖中邊數(shù)；（3）占用的存儲單元數(shù)目為n+2e。3．從有向圖的鄰接表可以得到如下結(jié)論（1）第i個鏈表中結(jié)點數(shù)目為頂點i的出度；（2）所有鏈表中結(jié)點數(shù)目為圖中弧數(shù)；（3）占用的存儲單元數(shù)目為n+e。從有向圖的鄰接表可知，不能求出頂點的入度。為此，我們必須另外建立有向圖的逆鄰接表，以便求出每一個頂點的入度。2．從無向圖的鄰接表可以得到如下結(jié)論（1）第i個鏈表33例：已知某網(wǎng)的鄰接（出邊）表，請畫出該網(wǎng)絡(luò)。8064125當(dāng)鄰接表的存儲結(jié)構(gòu)形成后，圖便唯一確定！例：已知某網(wǎng)的鄰接（出邊）表，請畫出該網(wǎng)絡(luò)。8064125當(dāng)34如果是無向圖，只要搜索任意一個結(jié)點的邊表。有向圖要搜索兩個結(jié)點的邊表。鄰接表的優(yōu)點：空間效率高；容易尋找頂點的鄰接點；鄰接表的缺點：判斷兩頂點間是否有邊或弧，需搜索兩結(jié)點對應(yīng)的單鏈表，沒有鄰接矩陣方便。如果是無向圖，只要搜索任意一個結(jié)點的邊表。有向圖要搜索兩個結(jié)354．圖的鄰接表數(shù)據(jù)類型描述圖的鄰接表數(shù)據(jù)類型描述如下：#defineMAXN50/*MAXN表示圖中最大頂點數(shù)*/typedefstructe_node//定義邊結(jié)點的結(jié)構(gòu){intadjvex;intweight;//邊的信息structe_node*next;}E_NODE;//指向鄰接點的指針typedefstructv_node//定義鄰接表的表頭類型{intvertex;//頂點信息

E_NODE*link;//指向“邊表”的指針}V_NODE;V_NODEhead[MAXN];4．圖的鄰接表數(shù)據(jù)類型描述圖的鄰接表數(shù)據(jù)類型描述如下：36討論：鄰接表與鄰接矩陣有什么異同之處？1.聯(lián)系：鄰接表中每個鏈表對應(yīng)于鄰接矩陣中的一行，鏈表中結(jié)點個數(shù)等于一行中非零元素的個數(shù)。2.區(qū)別：①對于任一確定的無向圖，鄰接矩陣是唯一的（行列號與頂點編號一致），但鄰接表不唯一（鏈接次序與頂點編號無關(guān)）。②鄰接矩陣的空間復(fù)雜度為O(n2),而鄰接表的空間復(fù)雜度為O(n+e)。3.

用途：鄰接矩陣多用于稠密圖的存儲（e接近n(n-1)/2)；而鄰接表多用于稀疏圖的存儲（e<<n2)討論：鄰接表與鄰接矩陣有什么異同之處？1.聯(lián)系：鄰接表中每37有向圖的十字鏈表表示法弧結(jié)點：typedefstructarcnode{inttailvex,headvex;//弧尾、弧頭在表頭數(shù)組中位置structarcnode*hlink；//指向弧頭相同的下一條弧structarcnode*tlink;//指向弧尾相同的下一條弧}AD;tailvexheadvexhlinktlink頂點結(jié)點：typedefstructdnode{intdata;//存與頂點有關(guān)信息structarcnode*firstin；//指向以該頂點為弧頭的第一個弧結(jié)點structarcnode*firstout;//指向以該頂點為弧尾的第一個弧結(jié)點}DD;DDg[M];//g[0]不用datafirstin