# C + + adjacency matrix

2020-11-08 23:48:06  The representation of undirected graph and digraph in adjacency matrix ： Undirected graphs and digraphs are similar , Just take undirected graphs as an example , The code part can be compiled by simple adjustment

``#define MaxVertices 100                 // Define maximum capacity ``typedef struct{                         // The definition of adjacency matrix with weight ``    int Vertices[MaxVertices];          // An array of vertex information ``    int Edge[MaxVertices][MaxVertices]; // An array of edge information ``    int n,e;                            // Total vertices , Number of edges ``}AMGraph;``

Take the diagram as an example According to the picture above , We can write the corresponding adjacency matrix ： You can see from this picture that , The diagonals of an undirected graph are divided into two parts Symmetrical to each other Of , By creating adjacency matrix of undirected graph ：

``void CreateUDN(AMGraph &G)              // The generating function of graphs ``{``    int i,j,n1,e1,vi,vj,w;``    printf(" Please enter the number of vertices and edges of the adjacency matrix :\n");``    scanf("%d %d",&G.n,&G.e);               // Enter the total number of vertex points , The total number of edges ``    n1 = G.n;``    e1 = G.e;``    printf(" Please enter the information for each vertex :\n");        ``    for(i=0; i<n1; i++)                     // Put the vertices in the array ``    {``        scanf("%d",&G.vexs[i]);             // Input the information of the points in turn ``    }``    for(i=0; i<n1; i++)                     // Initialization of graphs ``    {``        for(j=0; j<n1; j++)``        {``            if(i=j)``            {``                G.arcs[i][j] = 0;           // The path from the vertex to itself is 0``            }``            else``            {``                G.arcs[i][j] = MaxWeight;   // Except for the vertex to itself , The rest are set to the maximum ``            }``        }``    }``    printf("\n");``    // Input vertex from 0 Start ``//    for(i=0; i<e1; i++)``//    {``//        printf(" Please enter the side information :\n");``//        scanf("%d %d %d",&vi,&vj,&w);``//        G.arcs[vi][vj] = w;             // Because undirected graphs are symmetric ,a[i][j] = a[j][i]``//        G.arcs[vj][vi] = w;``//    }``    // Input vertex from 1 Start ``    for(i=0; i<e1; i++)``    {``        printf(" Please enter the side information :\n");``        scanf("%d %d %d",&vi,&vj,&w);``        G.arcs[vi-1][vj-1] = w;  // ①          // Because undirected graphs are symmetric ,a[i][j] = a[j][i]``        G.arcs[vj-1][vi-1] = w;  // ②``        // An undirected graph has the law of symmetry , adopt ①② Realization ``        // Digraphs do not have this property , So you just need to ①``    }``}``

The adjacency matrix corresponding to the undirected graph is created , We need to control the format of the output , Make it output as much as possible in the normal handwriting way

``void PrintfGraph(AMGraph G)         // Output the information of adjacency matrix ``{``    int i,j;``    printf(" The output vertex information is :\n");``    for(i=0; i<G.n; i++)``    {``        printf("%d\t",G.vexs[i]);``    }``    printf("\n The adjacency matrix is :\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)   // When there is no connection between two points, the weight value is the default 32767, But for the convenience of output  "∞"``            {``                printf("%s\t","∞");``            }``            else``                printf("%d\t",G.arcs[i][j]);``        }``    }``}``

The complete procedure is as follows ：

``#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)              // The generating function of graphs ``{``    int i,j,n1,e1,vi,vj,w;``    printf(" Please enter the number of vertices and edges of the adjacency matrix :\n");``    scanf("%d %d",&G.n,&G.e);               // Enter the total number of vertex points , The total number of edges ``    n1 = G.n;``    e1 = G.e;``    printf(" Please enter the information for each vertex :\n");``    for(i=0; i<n1; i++)                     // Put the vertices in the array ``    {``        scanf("%d",&G.vexs[i]);             // Input the information of the points in turn ``    }``    for(i=0; i<n1; i++)                     // Initialization of graphs ``    {``        for(j=0; j<n1; j++)``        {``            if(i=j)``            {``                G.arcs[i][j] = 0;           // The path from the vertex to itself is 0``            }``            else``            {``                G.arcs[i][j] = MaxWeight;   // Except for the vertex to itself , The rest are set to the maximum ``            }``        }``    }``    printf("\n");``    // Input vertex from 0 Start ``//    for(i=0; i<e1; i++)``//    {``//        printf(" Please enter the side information :\n");``//        scanf("%d %d %d",&vi,&vj,&w);``//        G.arcs[vi][vj] = w;             // Because undirected graphs are symmetric ,a[i][j] = a[j][i]``//        G.arcs[vj][vi] = w;``//    }``    // Input vertex from 1 Start ``    for(i=0; i<e1; i++)``    {``        printf(" Please enter the side information :\n");``        scanf("%d %d %d",&vi,&vj,&w);``        G.arcs[vi-1][vj-1] = w;  // ①          // Because undirected graphs are symmetric ,a[i][j] = a[j][i]``        G.arcs[vj-1][vi-1] = w;  // ②``        // An undirected graph has the law of symmetry , adopt ①② Realization ``        // Digraphs do not have this property , So you just need to ①``    }``}``void PrintfGraph(AMGraph G)         // Output the information of adjacency matrix ``{``    int i,j;``    printf(" The output vertex information is :\n");``    for(i=0; i<G.n; i++)``    {``        printf("%d\t",G.vexs[i]);``    }``    printf("\n The adjacency matrix is :\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)   // When there is no connection between two points, the weight value is the default 32767, But for the convenience of output  "∞"``            {``                printf("%s\t","∞");``            }``            else``                printf("%d\t",G.arcs[i][j]);``        }``    }``}``int main()``{``    AMGraph G;``    CreateUDN(G);``    PrintfGraph(G);``}``

The operation results are as follows ：  ``#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(" Please enter the total number of vertices and the number of sides :\n");``    scanf("%d %d",&G.n,&G.e);``    n = G.n;    e = G.e;``    printf(" Please enter the information for each vertex :\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;           // The path from the vertex to itself is 0``            }``            else``            {``                G.arcs[i][j] = MaxWeight;   // Except for the vertex to itself , The rest are set to the maximum ``            }``        }``    }``    printf("\n");``    // Input vertex from 0 Start ``    for(i=0;i<e;i++)``    {``        printf(" Please enter the side information :\n");``        scanf("%d %d %d",&vi,&vj,&w);``        G.arcs[vi][vj] = w;``    }``//      // Input vertex from 1 Start ``//    for(i=0;i<e;i++)``//    {``//        printf(" Please enter the side information :\n");``//        scanf("%d %d %d",&vi,&vj,&w);``//        G.arcs[vi-1][vj-1] = w;``//    }``}``void PrintfGraph(AMGraph G)         // Output the information of adjacency matrix ``{``    int i,j;``    printf(" The output vertex information is :\n");``    for(i=0; i<G.n; i++)``    {``        printf("%d\t",G.vexs[i]);``    }``    printf("\n The adjacency matrix is :\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)   // When there is no connection between two points, the weight value is the default 32767, But for the convenience of output  "∞"``            {``                printf("%s\t","∞");``            }``            else``                printf("%d\t",G.arcs[i][j]);``        }``    }``}``int main()``{``    AMGraph G;``    CreateGraph(G);``    PrintfGraph(G);``}``

Running results ： 