圖的鄰接矩陣算法

• 無向圖的鄰接矩陣是關于左上右下對角線對稱的，有向圖不一定對稱
• 先得了解矩陣描述的圖，或者明白圖的矩陣描述概念。

圖的鄰接矩陣存儲結構

#define
typedef struct{
  char vexs[MAX]; //頂點表
  int arc[MAX][MAX];//鄰接矩陣，也就是邊的關系表
  int numVertexes,numEdges;//圖中的定點數和邊數 
}MGaph;      

根據鄰接矩陣的定義，可得到建立圖的鄰接矩陣算法。

• 算法描述：首先得到圖的頂點數和邊數、然後按照頂點的數量後再将頂點的名稱逐一放入字元存儲數組當中、再把關系矩陣全部初始化置零、知道邊數，利用一個循環把每兩條邊的關系描述出來。

/*建立無向圖鄰接矩陣*/
void GreatMGaph(MGaph *G){
  int i,j,k;
  char ch1,ch2;
  printf("請輸入頂點數和邊數：");
  scanf("%d%d",&G->numEdges,&G->numVertexes);
  getchar();
  printf("頂點邊數輸入成功！\n");
  
  /*輸入頂點資訊（名稱）*/
  for(i=0;i<G->numEdges;i++){
    printf("請輸入第%d個頂點name：",i+1);
    scanf("%c",&(G->vexs[i]));
    getchar();
  } 
  /*建立頂點之間的聯系*/
  //置零
  for(i=0;i<G->numEdges;i++){
    for(j=0;j<G->numEdges;j++){
      G->arc[i][j] = 0;
    }
  }
  //輸入關系
  for(k=0;k<G->numVertexes;k++){
    printf("建立第%d條邊：",k+1);
    scanf("%c,%c",&ch1,&ch2);
    getchar(); 
    for(i=0;i<G->numEdges;i++){
      for(j=0;j<G->numEdges;j++){
        if(ch1 == G->vexs[i] && ch2 == G->vexs[j]){
          G->arc[i][j] = 1;//可以在此處修改為帶權的圖 
          G->arc[j][i] = 1;//無向圖對稱，該語句作用 
        }
      }
    }
  } 
}      

最後還得輸出這個鄰接矩陣

void DisPlay(MGaph *G){
  int i,j;
  for(i=0;i<G->numEdges;i++){
    for(j=0;j<G->numEdges;j++){
      printf("%d ",G->arc[i][j]);
    }
    printf("\n");
  }
  
}      

int main() {
  MGaph G;//圖G 
  GreatMGaph(&G);
  DisPlay(&G);
  return 0;
}