C++邻接矩阵

想让APP和微信一样，可以流畅运行小程序？ | 体验即送大疆、华为、樱桃键盘！>>>

无向图和有向图在邻接矩阵中的表示方法： 

无向图和有向图大同小异，在这里只以无向图为例，代码部分通过简单调整即可对应编译有向图

邻接矩阵数据类型定义

#define MaxVertices 100                 //定义最大容量typedef struct{                         //包含权的邻接矩阵的的定义    int Vertices[MaxVertices];          //顶点信息的数组    int Edge[MaxVertices][MaxVertices]; //边信息的数组    int n,e;                            //总顶点数，边数}AMGraph;

以如关系图为例

根据上图，我们可以写出对应的邻接矩阵：

通过这个图可以看出，无向图对角线划分出来的两部分是互相对称的，由此即可通过创建无向图的邻接矩阵：

void CreateUDN(AMGraph &G)              //图的生成函数{    int i,j,n1,e1,vi,vj,w;    printf("请输入邻接矩阵的顶点数和边数:\n");    scanf("%d %d",&G.n,&G.e);               //输入总顶点数，总边数    n1 = G.n;    e1 = G.e;    printf("请输入每个顶点的信息:\n");            for(i=0; i<n1; i++)                     //将顶点存入数组中    {        scanf("%d",&G.vexs[i]);             //依次输入点的信息    }    for(i=0; i<n1; i++)                     //图的初始化    {        for(j=0; j<n1; j++)        {            if(i=j)            {                G.arcs[i][j] = 0;           //顶点到自身的路径为0            }            else            {                G.arcs[i][j] = MaxWeight;   //除顶点到自身外，其余均设为极大值            }        }    }    printf("\n");    //输入顶点从0开始//    for(i=0; i<e1; i++)//    {//        printf("请输入边的信息:\n");//        scanf("%d %d %d",&vi,&vj,&w);//        G.arcs[vi][vj] = w;             //因为无向图是对称的，a[i][j] = a[j][i]//        G.arcs[vj][vi] = w;//    }    //输入顶点从1开始    for(i=0; i<e1; i++)    {        printf("请输入边的信息:\n");        scanf("%d %d %d",&vi,&vj,&w);        G.arcs[vi-1][vj-1] = w;  // ①          //因为无向图是对称的，a[i][j] = a[j][i]        G.arcs[vj-1][vi-1] = w;  // ②        //无向图具有对称性的规律，通过①②实现        //有向图不具备此性质，所以只需要①    }}

创建完无向图对应的邻接矩阵，我们需要对输出的格式进行一下控制，使其尽量按照普通手写的方式输出

void PrintfGraph(AMGraph G)         //输出邻接矩阵的信息{    int i,j;    printf("输出顶点的信息为:\n");    for(i=0; i<G.n; i++)    {        printf("%d\t",G.vexs[i]);    }    printf("\n邻接矩阵为:\n");    for(i=0; i<G.n; i++)    {        printf("\t%d",G.vexs[i]);    }    for(i=0; i<G.n; i++)    {        printf("\n%d\t",G.vexs[i]);        for(j=0; j<G.n; j++)        {            if(G.arcs[i][j] == MaxWeight)   //两点之间无连接时权值为默认的32767，但输出时为了方便输出 "∞"            {                printf("%s\t","∞");            }            else                printf("%d\t",G.arcs[i][j]);        }    }}

完整程序如下：

#include <stdio.h>#include <stdlib.h>#define MaxVertices 100#define MaxWeight 32767typedef int VerType;typedef int ArcType;typedef struct{    VerType vexs[MaxVertices];    ArcType arcs[MaxVertices][MaxVertices];    int n,e;} AMGraph;void CreateUDN(AMGraph &G)              //图的生成函数{    int i,j,n1,e1,vi,vj,w;    printf("请输入邻接矩阵的顶点数和边数:\n");    scanf("%d %d",&G.n,&G.e);               //输入总顶点数，总边数    n1 = G.n;    e1 = G.e;    printf("请输入每个顶点的信息:\n");    for(i=0; i<n1; i++)                     //将顶点存入数组中    {        scanf("%d",&G.vexs[i]);             //依次输入点的信息    }    for(i=0; i<n1; i++)                     //图的初始化    {        for(j=0; j<n1; j++)        {            if(i=j)            {                G.arcs[i][j] = 0;           //顶点到自身的路径为0            }            else            {                G.arcs[i][j] = MaxWeight;   //除顶点到自身外，其余均设为极大值            }        }    }    printf("\n");    //输入顶点从0开始//    for(i=0; i<e1; i++)//    {//        printf("请输入边的信息:\n");//        scanf("%d %d %d",&vi,&vj,&w);//        G.arcs[vi][vj] = w;             //因为无向图是对称的，a[i][j] = a[j][i]//        G.arcs[vj][vi] = w;//    }    //输入顶点从1开始    for(i=0; i<e1; i++)    {        printf("请输入边的信息:\n");        scanf("%d %d %d",&vi,&vj,&w);        G.arcs[vi-1][vj-1] = w;  // ①          //因为无向图是对称的，a[i][j] = a[j][i]        G.arcs[vj-1][vi-1] = w;  // ②        //无向图具有对称性的规律，通过①②实现        //有向图不具备此性质，所以只需要①    }}void PrintfGraph(AMGraph G)         //输出邻接矩阵的信息{    int i,j;    printf("输出顶点的信息为:\n");    for(i=0; i<G.n; i++)    {        printf("%d\t",G.vexs[i]);    }    printf("\n邻接矩阵为:\n");    for(i=0; i<G.n; i++)    {        printf("\t%d",G.vexs[i]);    }    for(i=0; i<G.n; i++)    {        printf("\n%d\t",G.vexs[i]);        for(j=0; j<G.n; j++)        {            if(G.arcs[i][j] == MaxWeight)   //两点之间无连接时权值为默认的32767，但输出时为了方便输出 "∞"            {                printf("%s\t","∞");            }            else                printf("%d\t",G.arcs[i][j]);        }    }}int main(){    AMGraph G;    CreateUDN(G);    PrintfGraph(G);}

运行结果如下：

有向图的邻接矩阵：

#include <stdio.h>#include <stdlib.h>#define MaxVertices 100#define MaxWeight 32767typedef struct{    int vexs[MaxVertices];    int arcs[MaxVertices][MaxVertices];    int n,e;}AMGraph;void CreateGraph(AMGraph &G){    int n,e,i,j,vi,vj,w;    printf("请输入总顶点数和边数:\n");    scanf("%d %d",&G.n,&G.e);    n = G.n;    e = G.e;    printf("请输入每个顶点的信息:\n");    for(i=0;i<n;i++)    {        scanf("%d",&G.vexs[i]);    }    for(i=0;i<n;i++)    {        for(j=0;j<n;j++)        {             if(i==j)            {                G.arcs[i][j] = 0;           //顶点到自身的路径为0            }            else            {                G.arcs[i][j] = MaxWeight;   //除顶点到自身外，其余均设为极大值            }        }    }    printf("\n");    //输入顶点从0开始    for(i=0;i<e;i++)    {        printf("请输入边的信息:\n");        scanf("%d %d %d",&vi,&vj,&w);        G.arcs[vi][vj] = w;    }//      //输入顶点从1开始//    for(i=0;i<e;i++)//    {//        printf("请输入边的信息:\n");//        scanf("%d %d %d",&vi,&vj,&w);//        G.arcs[vi-1][vj-1] = w;//    }}void PrintfGraph(AMGraph G)         //输出邻接矩阵的信息{    int i,j;    printf("输出顶点的信息为:\n");    for(i=0; i<G.n; i++)    {        printf("%d\t",G.vexs[i]);    }    printf("\n邻接矩阵为:\n");    for(i=0; i<G.n; i++)    {        printf("\t%d",G.vexs[i]);    }    for(i=0; i<G.n; i++)    {        printf("\n%d\t",G.vexs[i]);        for(j=0; j<G.n; j++)        {            if(G.arcs[i][j] == MaxWeight)   //两点之间无连接时权值为默认的32767，但输出时为了方便输出 "∞"            {                printf("%s\t","∞");            }            else                printf("%d\t",G.arcs[i][j]);        }    }}int main(){    AMGraph G;    CreateGraph(G);    PrintfGraph(G);}

运行结果：

本文分享自微信公众号 - WHICH工作室（which_cn）。
如有侵权，请联系 [email protected] 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。