圖形結(jié)構(gòu)是一種比樹形結(jié)構(gòu)更復(fù)雜的非線性結(jié)構(gòu)。樹形結(jié)構(gòu)中的結(jié)點(diǎn)之間具有明顯的層次關(guān)系，且每一層上的結(jié)點(diǎn)只能和上一層中的一個(gè)結(jié)點(diǎn)相關(guān)，但可能和下一層的多個(gè)結(jié)點(diǎn)相關(guān)。在圖形結(jié)構(gòu)中，任意兩個(gè)結(jié)點(diǎn)之間都可能相關(guān)，即結(jié)點(diǎn)與結(jié)點(diǎn)之間的鄰接關(guān)系可以是任意的。因此，圖形結(jié)構(gòu)可用來描述更加復(fù)雜的對(duì)象。
1 圖的基本概念和存儲(chǔ)結(jié)構(gòu)
1.1 圖的定義
圖（Graph）是由非空的頂點(diǎn)集合V與描述頂點(diǎn)之間關(guān)系——邊（或者?。┑募螮組成，其形式化定義為：
G=(V, E)
如果圖G中的每一條邊都是沒有方向的，則稱G為無向圖。無向圖中邊是圖中頂點(diǎn)的無序偶對(duì)。無序偶對(duì)通常用圓括號(hào)“( )”表示。例如，頂點(diǎn)偶對(duì)(vi,vj)表示頂點(diǎn)vi和頂點(diǎn)vj相連的邊，并且(vi,vj)與(vj,vi)表示同一條邊。
如果圖G中的每一條邊都是有方向的，則稱G為有向圖。有向圖中的邊是圖中頂點(diǎn)的有序偶對(duì)，有序偶對(duì)通常用尖括號(hào)“”表示。例如，頂點(diǎn)偶對(duì)表示從頂點(diǎn)vi指向頂點(diǎn)vj的一條有向邊；其中，頂點(diǎn)vi稱為有向邊的起點(diǎn)，頂點(diǎn)vj稱為有向邊的終點(diǎn)。有向邊也稱為?。粚?duì)弧來說，vi為弧的起點(diǎn)，稱為弧尾；vj為弧的終點(diǎn)，稱為弧頭。
圖是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，表現(xiàn)在不僅各頂點(diǎn)的度可以不同，而且頂點(diǎn)之間的邏輯關(guān)系也錯(cuò)綜復(fù)雜。從圖的定義可知：一個(gè)圖的信息包括兩個(gè)部分：圖中頂點(diǎn)的信息以及描述頂點(diǎn)之間的關(guān)系——邊或弧的信息。因此無論采取什么方法來建立圖的存儲(chǔ)結(jié)構(gòu)，都要完整、準(zhǔn)確地反映這兩部分的信息。為適于用C語言描述，從本節(jié)起頂點(diǎn)序號(hào)由0開始，即圖的頂點(diǎn)集的一般形式為：V={v0,v1,…,vn-1}。
下面介紹幾種常用的圖的存儲(chǔ)結(jié)構(gòu)。
1.2 鄰接矩陣
所謂鄰接矩陣存儲(chǔ)結(jié)構(gòu)，就是用一維數(shù)組存儲(chǔ)圖中頂點(diǎn)的信息，并用矩陣來表示圖中各頂點(diǎn)之間的鄰接關(guān)系。假定圖G=(V, E)有n個(gè)頂點(diǎn)，即V={v0,v1,…,vn-1}，則表示G中各頂點(diǎn)相鄰關(guān)系需用一個(gè)n×n的矩陣，且矩陣元素為：

A[i][j]=

若G是帶權(quán)圖（網(wǎng)），則鄰接矩陣可定義為：

A[i][j]=

其中，wij表示(vi,vj)或上的權(quán)值；∞則為計(jì)算機(jī)上所允許的大于所有邊上權(quán)值的數(shù)值。無向圖的鄰接矩陣表示如圖7-6所示。


圖7-6 無向圖及鄰接矩陣表示
有向圖的鄰接矩陣表示如圖7-7所示。