数据结构—图的邻接矩阵存储

迷南。 2022-08-23 00:38 221阅读 0赞

/*
    邻接矩阵的基本操作。
    */
    #include <iostream>
    #include <malloc.h>
    #include <stdio.h>
    #define MAXV 50
    #define LIMITLESS 9999
    #define N 50
    using namespace std;
    typedef struct
    {
        int no;        //顶点编号
        char info[20];  //顶点其他信息
    } VertexType;
    
    typedef struct
    {
        int edges[MAXV][MAXV];    //邻接矩阵的边数组
        int n,e;                  //顶点数和边数
        VertexType vexs[MAXV];    //存放顶点信息
    }MGraph;
    
    //建立一个图的邻接矩阵存储
    void CreateMGraph(MGraph *G)
    {
        /*建立有向图G的邻接矩阵存储*/
        int i,j,k,w;
        cout<<"请输入顶点数和边数(输入格式为:顶点数 边数):";
        cin>>G->n>>G->e;     /*输入顶点数和边数*/
        cout<<"请输入顶点信息(输入格式为:顶点号 顶点描述):"<<endl;
        for (i=0; i<G->n; i++)
            cin>>G->vexs[i].no>>G->vexs[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]=LIMITLESS;
            }
        cout<<"请输入每条边对应的两个顶点的序号及权值(输入格式为:i j w):"<<endl;
        for (k=0; k<G->e; k++)
        {
            cin>>i>>j>>w;            //输入e 条边，建立邻接矩阵
            G->edges[i][j]=w;       //若为无权图，直接G->edges[j][i]=1;，无需输入w
        }
    }
    
    //显示一个用邻接矩阵存储的图
    void DispMGraph(MGraph *G)
    {
        int i,j;
        cout<<"顶点数: "<<G->n<<"边数: "<<G->e<<endl;
        cout<<G->n<<"个顶点的信息:\n";
        for (i=0; i<G->n; i++) /*输出顶点信息*/
            printf("%5d %5d %s\n", i, G->vexs[i].no, G->vexs[i].info);
        cout<<"各顶点相连的情况:\n";
        cout<<"\t";
        for (j=0; j<G->n; j++)    //第一行
            cout<<"["<<j<<"]\t";
        cout<<endl;
        for (i=0; i<G->n; i++)    //除第一行之外的每行
        {
            cout<<"["<<i<<"]\t";
            for (j=0; j<G->n; j++)
            {
                if(G->edges[i][j]==LIMITLESS)
                    cout<<"∞\t";
                else
                    cout<<G->edges[i][j]<<"\t";
            }
            cout<<endl;
        }
    }
    
    int main()
    {
        MGraph *g;
        g = (MGraph *)malloc(sizeof(MGraph));
        CreateMGraph(g);
        DispMGraph(g);
        return 0;
    }

运行结果：

![Center][]

[Center]: /images/20220722/5fa445a8d00544afab0192581a01c5fe.png