圖的存儲結(jié)構(gòu)鄰接矩陣

數(shù)據(jù)結(jié)構(gòu)和算法讓編程改變世界Changetheworldbyprogram圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)相比較線性表與樹來說就復(fù)雜很多。我們回顧下，對于線性表來說，是一對一的關(guān)系，所以用數(shù)組或者鏈表均可簡單存放。樹結(jié)構(gòu)是一對多的關(guān)系，所以我們要將數(shù)組和鏈表的特性結(jié)合在一起才能更好的存放。那么我們的圖，是多對多的情況，另外圖上的任何一個頂點都可以被看作是第一個頂點，任一頂點的鄰接點之間也不存在次序關(guān)系。我們仔細觀察以下幾張圖，然后深刻領(lǐng)悟一下：圖的存儲結(jié)構(gòu)ABCDFGEHABCDFGEHABCDFGEHABCDFGEH鄰接矩陣（無向圖）考慮到圖是由頂點和邊或弧兩部分組成，合在一起比較困難，那就很自然地考慮到分為兩個結(jié)構(gòu)來分別存儲。頂點因為不區(qū)分大小、主次，所以用一個一維數(shù)組來存儲是狠不錯的選擇。而邊或弧由于是頂點與頂點之間的關(guān)系，一維數(shù)組肯定就搞不定了，那我們不妨考慮用一個二維數(shù)組來存儲。于是我們的鄰接矩陣方案就誕生了！鄰接矩陣（無向圖）圖的鄰接矩陣(AdjacencyMatrix)存儲方式是用兩個數(shù)組來表示圖。一個一維數(shù)組存儲圖中頂點信息，一個二維數(shù)組(稱為鄰接矩陣)存儲圖中的邊或弧的信息。V0V1V2V3頂點數(shù)組：V0V1V2V3V0V1V2V3V00111V11010V21101V31010鄰接矩陣（無向圖）我們可以設(shè)置兩個數(shù)組，頂點數(shù)組為vertex[4]={V0,V1,V2,V3}，邊數(shù)組arc[4][4]為對稱矩陣(0表示不存在頂點間的邊，1表示頂點間存在邊)。對稱矩陣：所謂對稱矩陣就是n階矩陣的元滿足a[i][j]=a[j][i](0<=i,j<=n)。即從矩陣的左上角到右下角的主對角線為軸，右上角的元與左下角相對應(yīng)的元全都是相等的。鄰接矩陣（有向圖）無向圖的邊構(gòu)成了一個對稱矩陣，貌似浪費了一半的空間，那如果是有向圖來存放，會不會把資源都利用得很好呢？V0V1V2V3頂點數(shù)組：V0V1V2V3V0V1V2V3V00001V11010V21100V30000鄰接矩陣（有向圖）可見頂點數(shù)組vertex[4]={V0,V1,V2,V3}，弧數(shù)組arc[4][4]也是一個矩陣，但因為是有向圖，所以這個矩陣并不對稱，例如由V1到V0有弧，得到arc[1][0]=1，而V0到V1沒有弧，因此arc[0][1]=0。另外有向圖是有講究的，要考慮入度和出度，頂點V1的入度為1，正好是第V1列的各數(shù)之和，頂點V1的出度為2，正好是第V1行的各數(shù)之和。鄰接矩陣（網(wǎng)）在圖的術(shù)語中，我們提到了網(wǎng)這個概念，事實上也就是每條邊上帶有權(quán)的圖就叫網(wǎng)。這里“∞”表示一個計算機允許的、大于所有邊上權(quán)值的值。V0V1V2V3頂點數(shù)組：V0V1V2V3