C语言数据结构——图的邻接矩阵

谁借莪１个温暖的怀抱￠ 2021-11-29 14:36 379阅读 0赞

**转载地址：[https://blog.csdn.net/qq\_39630587/article/details/77374857][https_blog.csdn.net_qq_39630587_article_details_77374857]**

![邻接矩阵概念][SouthEast]  
**无向图和有向图在邻接矩阵中的表示方法：**  
![有向图和无向图的表示方法][SouthEast 1]

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

**邻接矩阵数据类型定义**

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

**以如关系图为例**  
![邻接矩阵关系图][SouthEast 2]  
**根据上图，我们可以写出对应的邻接矩阵：**  
![邻接矩阵手写][SouthEast 3]  
通过这个图可以看出，无向图对角线划分出来的两部分是**互相对称**的，由此即可通过创建无向图的邻接矩阵：

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 32767
    typedef 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);
    }

**运行结果如下：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70][]

**有向图的邻接矩阵：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70 1][]

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

**全部代码：**

#include <stdio.h>
    #include <stdlib.h>
    #define MaxVertices 100
    #define MaxWeight 32767
    typedef 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);
    }

**运行结果：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70 2][]

[https_blog.csdn.net_qq_39630587_article_details_77374857]: https://blog.csdn.net/qq_39630587/article/details/77374857
[SouthEast]: /images/20211129/ad172735213e4790b30213e0146a318e.png
[SouthEast 1]: /images/20211129/89fe1e19c99e40ab903fefeaae788ff1.png
[SouthEast 2]: /images/20211129/078550ea7b8343398db0f51b951a1337.png
[SouthEast 3]: /images/20211129/2fb313b64f5f4b6d95417dc07742c09d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70]: /images/20211129/4f04f57f58af42bf87696fcd50c9e32c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70 1]: /images/20211129/99da96a19a0c4939aac8cf326de70369.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDgxOTI0_size_16_color_FFFFFF_t_70 2]: /images/20211129/6a6010b8add54f8b8c681760a18a1858.png