C + + adjacency matrix

Want to make APP Same thing as WeChat , Can run small programs smoothly ？ | Experience will send you to Xinjiang 、 Huawei 、 Cherry keyboard ！>>>

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

Adjacency matrix data type definition

#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 32767typedef 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 ：

Adjacency matrix of digraph ：

#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(" 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 ：

This article is from WeChat official account. - WHICH Studio （which_cn）.
If there is any infringement , Please contact the [email protected] Delete .
Participation of this paper “OSC Source creation plan ”, You are welcome to join us , share .