图的邻接矩阵存储

待我称王封你为后i 2022-02-09 09:45 220阅读 0赞

###### 图的邻接矩阵 ######

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

###### 首先要定义一个图和顶点的结构体 ######

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