如何利用鄰接矩陣構建網路

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

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

圖的鄰接矩陣表示法

圖的鄰接矩陣表示法

在圖的鄰接矩陣表示法中

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

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

圖的鄰接矩陣(Adacency Matrix)

設G=(V E)是具有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 n e; //圖中當前的頂點數和邊數

}MGragh;

注意

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

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

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

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

建立無向網路的演算法

void CreateMGraph(MGraph *G)

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

int i j k w;

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

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

G >vexs[i]=getchar();

for(i= ;i n;i++)

for(j= ;j n;j++)

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

for(k= ;k e;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 <n )。.lishixin