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

A[i][j]=

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

A[i][j]=

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


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