图的邻接矩阵算法

• 无向图的邻接矩阵是关于左上右下对角线对称的，有向图不一定对称
• 先得理解矩阵描述的图，或者明白图的矩阵描述概念。

图的邻接矩阵存储结构

#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;
}