欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

图的邻接矩阵存储

程序员文章站 2022-05-21 08:49:15
...
图的邻接矩阵

图的基本存储方法有两种:邻接矩阵和邻接表
这里简单对邻接矩阵做一个描述(带权有向图)

首先要定义一个图和顶点的结构体
typedef struct//定义顶点的结构体
{
   int no; //顶点的编号
   char info[20]; //顶点的一些信息,看应用而定
}Acme;
typedef struct  //图的定义
{
   int edges[Max][Max];  //定义一个矩阵
   int n,e;//边长数和顶点数
   Acme acme[Max];//存放顶点信息
}Graph;

建立一个图的邻接矩阵
void CreateGraph(Graph *G)
{
    int i,j,k,m;
   printf("请输入顶点数和边数:\n");
   scanf("%d %d",&G->n,&G->e);
   printf("请输入顶点的编号及信息:\n");
   for(i=0;i<G->n;i++)
   {
       scanf("%d %s",&G->acme[i].no,&G->acme[i].info);
   }
   for(i=0;i<G->n;i++)
   {
       for(j=0;j<G->n;j++)
       {
           if(i==j)
            G->edges[i][j]=0;
           else
               G->edges[i][j]=LIMIT;
       }
   }
   printf("请输入每条边的顶点及其权值\n");
   for(k=0;k<G->e;k++)
   {
       scanf("%d %d %d",&i,&j,&m);
       G->edges[i][j]=m;//若为无权图G->edges[i][j]=1;
   }
}
输出邻接矩阵
void PrintGraph(Graph *G)
{
    int i,j;
    printf("输出顶点数及边数:\n");
    printf("%d %d",G->n,G->e);
    printf("输出各顶点信息:\n");
    for(i=0;i<G->n;i++)
    {
        printf("%d %s\n",G->acme[i].no,G->acme[i].info);
    }
    printf("输出邻接矩阵\n");
    printf("\t");
    for(j=0;j<G->n;j++)
        printf("[%d]\t",j);
    printf("\n");
    for(i=0;i<G->n;i++)
    {
        printf("[%d]\t",i);
        for(j=0;j<G->n;j++)
        {
            if(G->edges[i][j]==LIMIT)
                 printf("∞\t");
            else
                 printf("%d\t",G->edges[i][j]);
        }
        printf("\n");
    }
}
main函数
int main()
{
    Graph *h;
    h=(Graph*)malloc(sizeof(Graph));
    CreateGraph(h);
    PrintGraph(h);
   return 0;
}