表示法
鄰接矩陣① 用鄰接矩陣表示頂點間的相鄰關係
② 用一個順序表來存儲頂點信息
圖的矩陣
設G=(V，E)是具有n個頂點的圖，則G的鄰接矩陣是具有如下性質的n階方陣：
鄰接矩陣【例】
下圖中無向圖G 5 和有向圖G 6 的鄰接矩陣分別為A l 和A 2 。
鄰接矩陣網路矩陣
若G是網路，則鄰接矩陣可定義為：
鄰接矩陣其中：
w ij 表示邊上的權值;
∞表示一個計算機允許的、大於所有邊上權值的數。
【例】下面帶權圖的兩種鄰接矩陣分別為A 3 和A 4 。
鄰接矩陣圖的鄰接矩陣存儲結構形式說明
#define MaxVertexNum l00 //最大頂點數，應由用戶定義
typedef char VertexType; //頂點類型應由用戶定義
typedef int EdgeType; //邊上的權值類型應由用戶定義
typedef struct{
VextexType vexs[MaxVertexNum] //頂點表
EdeType edges[MaxVertexNum][MaxVertexNum];//鄰接矩陣，可看作邊表
int n，e; //圖中當前的頂點數和邊數
}MGragh;
注意：
① 在簡單套用中，可直接用二維數組作為圖的鄰接矩陣(頂點表及頂點數等均可省略)。
② 當鄰接矩陣中的元素僅表示相應的邊是否存在時，EdgeTyPe可定義為值為0和1的枚舉類型。
③無向圖的鄰接矩陣是對稱矩陣，對規模特大的鄰接矩陣可壓縮存儲。
④鄰接矩陣表示法的空間複雜度S(n)=0(n 2 )。
⑤建立無向網路的算法。
void CreateMGraph(MGraph *G)
{//建立無向網的鄰接矩陣表示
int i，j，k，w;
scanf("%d%d"，&G->n，&G->e); //輸入頂點數和邊數
for(i = 0;i < n;i++) //讀入頂點信息，建立頂點表
{
G->vexs=getchar();
}
for(i = 0;i < G->n;i++)
{
for(j = 0;j n;j++)
{
G->edges[i][j] = 0; //鄰接矩陣初始化
}
}
for(k = 0;k < G->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
該算法的執行時間是0(n+n 2 +e)。由於e
根據圖的定義可知，圖的邏輯結構分為兩部分：V和E的集合。因此，用一個一維數組存放圖中所有頂點數據；用一個二維數組存放頂點間關係（邊或弧）的數據，稱這個二維數組為鄰接矩陣。鄰接矩陣又分為有向圖鄰接矩陣和無向圖鄰接矩陣。
Matlab表達N=4;//圖中的節點數目
dag=zeros(N,N);//鄰接矩陣初始化，值均為0
C=1;S=2;R=3;
W=4;//制定各節點編號
dag(C,[RS])=1;//有兩條有向邊：C->R,C->S
dag(R,W)=1;//有向邊：R->W
dag(S,W)=1;//有向邊：S->W
