鄰接矩陣

無向圖和有向圖在鄰接矩陣中的表示方法：

無向圖和有向圖大同小異，在這里只以無向圖為例，代碼部分通過簡單調整即可對應編譯有向圖

鄰接矩陣數據類型定義

#define MaxVertices 100 //定義最大容量 typedef struct{ //包含權的鄰接矩陣的的定義int Vertices[MaxVertices]; //頂點信息的數組int Edge[MaxVertices][MaxVertices]; //邊信息的數組int numV; //頂點數int numE; //邊數 }AdjMatrix;

以如關系圖為例

根據上圖，我們可以寫出對應的鄰接矩陣：

通過這個圖可以看出，無向圖對角線劃分出來的兩部分是互相對稱的，由此即可通過創建無向圖的鄰接矩陣：

void CreateGraph(AdjMatrix *G) //圖的生成函數 { int n,e,vi,vj,w,i,j;printf("請輸入圖的頂點數和邊數（以空格分隔）：");scanf("%d%d",&n,&e);G->numV=n;G->numE=e;for(i=0;i<n;i++) //圖的初始化for(j=0;j<n;j++){ if(i==j)G->Edge[i][j]=0;else G->Edge[i][j]=32767;}for(i=0;i<G->numV;i++) //將頂點存入數組中{ printf("請輸入第%d個頂點的信息:",i+1);scanf("%d",&G->Vertices[i]);}printf("\n");for(i=0;i<G->numE;i++){ printf("請輸入邊的信息i,j,w(以空格分隔):");scanf("%d%d%d",&vi,&vj,&w); //若為不帶權值的圖，則w輸入1//若為帶權值的圖，則w輸入對應權值G->Edge[vi-1][vj-1]=w;//①G->Edge[vj-1][vi-1]=w;//②//無向圖具有對稱性的規律，通過①②實現//有向圖不具備此性質，所以只需要①} }

創建完無向圖對應的鄰接矩陣，我們需要對輸出的格式進行一下控制，使其盡量按照普通手寫的方式輸出

void DispGraph(AdjMatrix G) //輸出鄰接矩陣的信息 { int i,j;printf("\n輸出頂點的信息（整型）:\n");for(i=0;i<G.numV;i++)printf("%8d",G.Vertices[i]);printf("\n輸出鄰接矩陣:\n");printf("\t");for(i=0;i<G.numV;i++)printf("%8d",G.Vertices[i]);for(i=0;i<G.numV;i++){ printf("\n%8d",i+1);for(j=0;j<G.numV;j++){ if(G.Edge[i][j]==32767) //兩點之間無連接時權值為默認的32767，但輸出時為了方便輸出 "∞"printf("%8s", "∞");elseprintf("%8d",G.Edge[i][j]);}printf("\n"); } }

完整程序如下：

#include<stdio.h> #include<stdlib.h> #define MaxVertices 100 //假設包含100個頂點 #define MaxWeight 32767 //不鄰接時為32767，但輸出時用 "∞" typedef struct{ //包含權的鄰接矩陣的的定義int Vertices[MaxVertices]; //頂點信息的數組int Edge[MaxVertices][MaxVertices]; //邊的權信息的數組int numV; //當前的頂點數int numE; //當前的邊數 }AdjMatrix;void CreateGraph(AdjMatrix *G) //圖的生成函數 { int n,e,vi,vj,w,i,j;printf("請輸入圖的頂點數和邊數（以空格分隔）：");scanf("%d%d",&n,&e);G->numV=n;G->numE=e;for(i=0;i<n;i++) //圖的初始化for(j=0;j<n;j++){ if(i==j)G->Edge[i][j]=0;else G->Edge[i][j]=32767;}for(i=0;i<G->numV;i++) //將頂點存入數組中{ printf("請輸入第%d個頂點的信息(整型):",i+1);scanf("%d",&G->Vertices[i]);}printf("\n");for(i=0;i<G->numE;i++){ printf("請輸入邊的信息i,j,w(以空格分隔):");scanf("%d%d%d",&vi,&vj,&w); //若為不帶權值的圖，則w輸入1//若為帶權值的圖，則w輸入對應權值G->Edge[vi-1][vj-1]=w;//①G->Edge[vj-1][vi-1]=w;//②//無向圖具有對稱性的規律，通過①②實現//有向圖不具備此性質，所以只需要①} } void DispGraph(AdjMatrix G) //輸出鄰接矩陣的信息 { int i,j;printf("\n輸出頂點的信息（整型）:\n");for(i=0;i<G.numV;i++)printf("%8d",G.Vertices[i]);printf("\n輸出鄰接矩陣:\n");printf("\t");for(i=0;i<G.numV;i++)printf("%8d",G.Vertices[i]);for(i=0;i<G.numV;i++){ printf("\n%8d",i+1);for(j=0;j<G.numV;j++){ if(G.Edge[i][j]==32767) //兩點之間無連接時權值為默認的32767，在無向圖中一般用"0"表示，在有向圖中一般用"∞",這里為了方便統一輸出 "∞"printf("%8s", "∞");elseprintf("%8d",G.Edge[i][j]);}printf("\n"); } } int main() { AdjMatrix G;CreateGraph(&G);DispGraph(G); }

運行結果如下：

總結

以上是生活随笔為你收集整理的图的邻接矩阵（C语言）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。