Adjacency matrix undirected graph (I) - basic concepts and C language

This chapter introduces the adjacency matrix undirected graph . stay " The theoretical basis of graph " The theory of graph has been introduced in , The concept of graph is not repeated here . As usual , This article will first give C The realization of language ; We will give you the following C++ and Java Implementation of version . The language of implementation is different , But the principle is the same , Choose one of them to learn . If there are mistakes or deficiencies in the article , Please point out ！

Catalog
1.  Introduction of adjacency matrix undirected graph
2.  Adjacency matrix undirected graph code description
3.  Adjacency matrix undirected graph complete source code

Reprint please indicate the source ： If the sky doesn't die - Blog Garden

More ： Data structure and algorithm series Catalog

Introduction of adjacency matrix undirected graph

Adjacency matrix undirected graph refers to the undirected graph represented by adjacency matrix .

 

The picture above G1 Contains "A,B,C,D,E,F,G" common 7 vertices , And it includes "(A,C),(A,D),(A,F),(B,C),(C,D),(E,G),(F,G)" common 7 side . Because this is an undirected graph , So side (A,C) He Bian (C,A) It's the same side ; Here are the side times , It is listed in alphabetical order .

The matrix on the right of the above figure is G1 Diagram of adjacency matrix in memory .A[i][j]=1 It means the first one i Vertices and the j Vertices are adjacency points ,A[i][j]=0 They are not adjacency points ; and A[i][j] It means No i Xing di j The value of the column ; for example ,A[1,2]=1, It means the first one 1 vertices ( Vertex B) And the 2 vertices (C) It's the adjacency point .

Adjacency matrix undirected graph code description

1. The basic definition

//  Adjacency matrix 
typedef struct _graph
{
    char vexs[MAX];       //  Vertex set 
    int vexnum;           //  Number of vertices 
    int edgnum;           //  Number of edges 
    int matrix[MAX][MAX]; //  Adjacency matrix 
}Graph, *PGraph;

Graph Is the structure corresponding to the adjacency matrix .
vexs Lets you save vertices ,vexnum It's the top point ,edgnum It's the number of sides ;matrix Is a two-dimensional array used to store matrix information . for example ,matrix[i][j]=1, said " The vertices i( namely vexs[i])" and " The vertices j( namely vexs[j])" It's the adjacency point ;matrix[i][j]=0, They are not adjacency points .

2. Create a matrix

Here are two ways to create a matrix . One is Using known data , Another rule The user needs to input data manually .

2.1 Create diagrams ( Use the provided matrix )

/*
 *  Create diagrams ( Use the provided matrix )
 */
Graph* create_example_graph()
{
    char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
    char edges[][2] = {
        {'A', 'C'}, 
        {'A', 'D'}, 
        {'A', 'F'}, 
        {'B', 'C'}, 
        {'C', 'D'}, 
        {'E', 'G'}, 
        {'F', 'G'}}; 
    int vlen = LENGTH(vexs);
    int elen = LENGTH(edges);
    int i, p1, p2;
    Graph* pG;

    //  Input " Number of vertices " and " Number of edges "
    if ((pG=(Graph*)malloc(sizeof(Graph))) == NULL )
        return NULL;
    memset(pG, 0, sizeof(Graph));

    //  initialization " Number of vertices " and " Number of edges "
    pG->vexnum = vlen;
    pG->edgnum = elen;
    //  initialization " The vertices "
    for (i = 0; i < pG->vexnum; i++)
    {
        pG->vexs[i] = vexs[i];
    }

    //  initialization " edge "
    for (i = 0; i < pG->edgnum; i++)
    {
        //  Read the start and end vertices of the edge 
        p1 = get_position(*pG, edges[i][0]);
        p2 = get_position(*pG, edges[i][1]);

        pG->matrix[p1][p2] = 1;
        pG->matrix[p2][p1] = 1;
    }

    return pG;
}

Fold

createexamplegraph The function of yes is to create an undirected graph of adjacency matrix .

Be careful ： Undirected graph created by this method , It's the picture above G1.

2.2 Create diagrams ( Enter your own )

/*
 *  Create diagrams ( Use the provided matrix )
 */
Graph* create_example_graph()
{
    char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
    char edges[][2] = {
        {'A', 'C'}, 
        {'A', 'D'}, 
        {'A', 'F'}, 
        {'B', 'C'}, 
        {'C', 'D'}, 
        {'E', 'G'}, 
        {'F', 'G'}}; 
    int vlen = LENGTH(vexs);
    int elen = LENGTH(edges);
    int i, p1, p2;
    Graph* pG;

    //  Input " Number of vertices " and " Number of edges "
    if ((pG=(Graph*)malloc(sizeof(Graph))) == NULL )
        return NULL;
    memset(pG, 0, sizeof(Graph));

    //  initialization " Number of vertices " and " Number of edges "
    pG->vexnum = vlen;
    pG->edgnum = elen;
    //  initialization " The vertices "
    for (i = 0; i < pG->vexnum; i++)
    {
        pG->vexs[i] = vexs[i];
    }

    //  initialization " edge "
    for (i = 0; i < pG->edgnum; i++)
    {
        //  Read the start and end vertices of the edge 
        p1 = get_position(*pG, edges[i][0]);
        p2 = get_position(*pG, edges[i][1]);

        pG->matrix[p1][p2] = 1;
        pG->matrix[p2][p1] = 1;
    }

    return pG;
}

Fold

create_graph() Is to read the user's input , Convert the input data into the corresponding undirected graph .