圖 - 圖的存儲結構 - 鄰接矩陣表示法

　　圖的存儲表示方法很多這裡介紹兩種最常用的方法至於具體選擇哪一種表示法主要取決於具體的應用和欲施加的操作

　　為了適合用C語言描述以下假定頂點序號從開始即圖G的頂點集的一般形式是V(G)={v v i …V n }

　　圖的鄰接矩陣表示法

　　圖的鄰接矩陣表示法

　　在圖的鄰接矩陣表示法中

　　① 用鄰接矩陣表示頂點間的相鄰關系

　　② 用一個順序表來存儲頂點信息

　　圖的鄰接矩陣(Adacency Matrix)

　　設G=(VE)是具有n個頂點的圖則G的鄰接矩陣是具有如下性質的n階方陣

　　【例】下圖中無向圖G 和有向圖G 的鄰接矩陣分別為A l 和A

　　網絡的鄰接矩陣

　　若G是網絡則鄰接矩陣可定義為

　　其中

　　w ij 表示邊上的權值;

　　∞表示一個計算機允許的大於所有邊上權值的數

　　【例】下面帶權圖的兩種鄰接矩陣分別為A 和A

　　圖的鄰接矩陣存儲結構形式說明

　　#define MaxVertexNum l //最大頂點數應由用戶定義

　　typedef char VertexType; //頂點類型應由用戶定義

　　typedef int EdgeType; //邊上的權值類型應由用戶定義

　　typedef struct{

　　VextexType vexs[MaxVertexNum] //頂點表

　　EdeType edges[MaxVertexNum][MaxVertexNum];

　　//鄰接矩陣可看作邊表

　　int ne; //圖中當前的頂點數和邊數

　　}MGragh;

　　注意

　　① 在簡單應用中可直接用二維數組作為圖的鄰接矩陣(頂點表及頂點數等均可省略)

　　② 當鄰接矩陣中的元素僅表示相應的邊是否存在時EdgeTyPe可定義為值為和的枚舉類型

　　③ 無向圖的鄰接矩陣是對稱矩陣對規模特大的鄰接矩陣可壓縮存儲

　　④ 鄰接矩陣表示法的空間復雜度S(n)=(n )

　　建立無向網絡的算法

　　void CreateMGraph(MGraph *G)

　　{//建立無向網的鄰接矩陣表示

　　int ijkw;

　　scanf(%d%d&G>n&G>e); //輸入頂點數和邊數

　　for(i=;in;i++) //讀人頂點信息建立頂點表

　　G>vexs[i]=getchar();

　　for(i=;in;i++)

　　for(j=;jn;j++)

　　G>edges[i][j]=; //鄰接矩陣初始化

　　for(k=;ke;k++){//讀入e條邊建立鄰接矩陣

　　scanf(%d%d%d&i&j&w);//輸入邊(v i v j )上的權w

　　G>edges[i][j]=w;

　　G>edges[j][i]=w;

　　}

　　}//CreateMGraph

　　該算法的執行時間是(n+n +e)由於e