This is the 22nd day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

Preface:

We learn in front of the figure of some definitions and terminology, the data structure on the map have new insights and knowledge, let us understand the structure of knowledge, today we’ll learn figure storage structure, storage structure of figure is more, we mainly study adjacency matrix and adjacency list today, for the adjacency matrix is the use of the form of an array, we don’t call the sequential storage structure, called the adjacency matrix, Adjacency list and our cross chain have similarities and similarities, but the adjacency list of the linked list to a little more, good words do not say we began to learn!!

Once a day to prevent decadence

1. Adjacency matrix

Official term:

The Adjacency Matrix is a Matrix that represents the relationships between vertices. Let G=(V,E) be a graph where V={v1,v2... ,.vn} [1]. The adjacency matrix of G is a square matrix of order N with the following properties: ① For undirected graphs, the adjacency matrix must be symmetric, and the principal diagonal must be zero (only undirected simple graphs are discussed here), and the auxiliary diagonal must not be zero, not necessarily for directed graphs. ② In an undirected graph, the degree of any vertex I is the number of all non-zero elements in column I (or row I); in a directed graph, the degree of vertex I is the number of all non-zero elements in row I, and the degree of vertex I is the number of all non-zero elements in column I. ③ A total of N ^2 Spaces are needed to represent a graph by the adjacency matrix method. Since the adjacency matrix of an undirected graph must have a symmetric relationship, only the data of the upper triangle or the lower triangle need to be stored except that the diagonal is zero, so only N (n-1) /2 Spaces are needed.Copy the code

In human terms, adjacency matrix is similar to the triplet representation of a matrix, that is, a vertex is combined with a two-dimensional array. The first subscript of the two-dimensional array represents the beginning of an edge, and the second subscript represents the end of an edge. If there are edges, the value of this position is assigned to 1, and if there are no edges, the value is assigned to 0 as shown below:

1.1 Adjacency matrix type declaration of figure:

#include <stdio.h> #include <malloc.h> #define MAXVEX 100 #define INF 32767 VertexType[10]; Typedef struct vertex {int adjvex; VertexType data; // Vertex information} VType; // typedef struct graph {int n,e; //n is the number of vertices,e is the number of edges VType vexs[MAXVEX]; Int edges[MAXVEX][MAXVEX]; // set of edges} MatGraph; // Graph adjacency matrix typeCopy the code

1.2 Establish the algorithm of graph adjacency matrix

The adjacency matrix storage structure of graph G is established by array A of adjacency matrix, number of vertices N and number of edges E.

void CreateGraph(MatGraph &g,int A[][MAXVEX],int n,int e) { int i,j; g.n=n; g.e=e; for (i=0; i<n; i++) for (j=0; j<n; j++) g.edges[i][j]=A[i][j]; }Copy the code

1.3 Destruction graph algorithm

Here, the adjacency matrix is a sequential storage structure of the graph. Its memory space is automatically allocated by the system and released automatically when it is no longer needed. So the corresponding function does not contain any statements.

Void DestroyGraph(MatGraph g) void DestroyGraph(MatGraph g) void DestroyGraph(MatGraph g)Copy the code

1.4 Output graph operation algorithm

Output the adjacency matrix storage structure of Figure G to the screen

void DispGraph(MatGraph g) { int i,j; for (i=0; i<g.n; i++) { for (j=0; j<g.n; j++) if (g.edges[i][j]<INF) printf("%4d",g.edges[i][j]); The else printf (" % 4 s ", "up"); printf("\n"); }}Copy the code

1.5 Computing algorithm of vertex degree

For undirected graphs and directed graphs, vertex degree is different. According to the definition, the algorithm for finding the degree of vertex V in undirected graph G is as follows:

Int Degree1(MatGraph g,int v) {int I,d=0; if (v<0 || v>=g.n) return -1; For (I =0; i<g.n; i++) if (g.edges[v][i]>0 && g.edges[v][i]<INF) d++; // count the number of edges on line V that are neither 0 nor ∞. } int Degree2(MatGraph g,int v) {int I,d1=0,d2=0,d; if (v<0 || v>=g.n) return -1; For (I =0; i<g.n; I++) if (g.e dges [v] [I] > 0 && g.e dges [v] [I] < INF) d1 + +; // Count the number of edges on row V that are neither 0 nor ∞. i<g.n; I++) if (g.e dges [I] [v] > 0 && g.e dges [I] [v] < INF) d2 + +; // Count the number of edges in column V that are neither 0 nor ∞ d=d1+d2; return d; }Copy the code

1.6 Main functions and effect display

int main(int argc, char** argv) { MatGraph g; int n=5,e=7,i; Int A [MAXVEX] [MAXVEX] = {{0,1,2,6, INF}, {INF, 0, INF, 4, 5}, {INF, INF, 0, INF, 3}, {INF, INF, INF, 0, INF}, {INF, INF, INF, 7, 0}}; CreateGraph(g,A,n,e); // Set up the adjacency matrix printf(" memory structure of graph G :\n"); DispGraph(g); Printf (" Degree of all vertices in graph G :\n"); Printf (" vertex \t degree \n"); for (i=0; i<g.n; i++) printf(" %d\t%d\n",i,Degree2(g,i)); DestroyGraph(g); return 0; }Copy the code

2. The adjacency list

Adjacency list is a chain storage structure of graphs. In adjacency list, a singly linked list of leading nodes is established for each vertex in the graph, and all the adjacent points of the vertex are connected together. All the heads form an array, called an array of heads, and are represented by AdjList. The nodes in the i-th single linked list adjList [I] represent the edges attached to vertex I, that is, the subscripts of the elements in the array of heads are the same as the number of vertices.Copy the code

Each node of this array represents a head pointer that points to a single linked list. This single linked list holds the next vertex you want to point to (the head pointer) and the weights

2.1 The type declaration of the adjacency list storage structure of the figure is as follows:

#include <stdio.h> #include <malloc.h> #define MAXVEX 100 #define INF 32767 VertexType[10]; Typedef struct edgenode {int adjvex; // Int weight; Struct edgenode *nextarc; } ArcNode; Typedef struct vexnode {VertexType data; ArcNode *firstarc; } VHeadNode; Typedef struct {int n,e; //n is the actual number of vertices,e is the actual number of edges VHeadNode AdjList [MAXVEX]; // single link header array} AdjGraph; // The adjacency list type of the graphCopy the code

2.2 Adjacency List Creation

void CreateGraph(AdjGraph *&G,int A[][MAXVEX],int n,int e) { int i,j; ArcNode *p; G=(AdjGraph *)malloc(sizeof(AdjGraph)); G->n=n; G->e=e; for (i=0; i<G->n; G-> adjList [I]. Firstarc =NULL; for (i=0; i<G->n; For (j=G->n-1; j>=0; J -) if (A [I] [j] > 0 && A [I] [j] < INF) / / there is A side {p = (ArcNode *) malloc (sizeof (ArcNode)); P p->adjvex=j; p->weight=A[i][j]; p->nextarc=G->adjlist[i].firstarc; [I]. Firstarc =p; }}Copy the code

2.3 Graph destruction algorithm

The head and edge of the adjacency list are allocated using malloc, and free is used to free all allocated space when it is no longer needed. The basic idea is to iterate through each single linked list with an AdjList array, freeing all edge nodes, and finally freeing the space of the AdjList array.

Void DestroyGraph(AdjGraph * &g) // DestroyGraph {int I; ArcNode *pre,*p; for (i=0; i<G->n; {pre=G-> adjList [I].firstarc; if (pre! =NULL) { p=pre->nextarc; while (p! // Free adjList [I] {free(pre); pre=p; P = p - > nextarc; } free (pre); } } free(G); // free the array of headers that G refers to}Copy the code

2.4 Output graph algorithm

Output the adjacency list storage structure of Figure G to the screen.

Void DispGraph(AdjGraph *G) {ArcNode *p; int i; for (i=0; i<G->n; Printf (" [%2d]", I); printf(" [%2d]", I); p=G->adjlist[i].firstarc; //p refers to the first adjacent point if (p! = NULL) printf (" - > "); while (p! =NULL) { printf(" %d(%d)",p->adjvex,p->weight); p=p->nextarc; } printf("\n"); }}Copy the code

2.5 Computing algorithm of vertex degree

For undirected graphs and directed graphs, vertex degree is different. According to the definition, the algorithm for finding the degree of vertex V in undirected graph G is as follows:

Int Degree1(AdjGraph *G,int v) // Find the vertex v in the undirected graph {int d=0; ArcNode *p; if (v<0 || v>=G->n) return -1; P =G-> adjList [v]. Firstarc; while (p! =NULL) // count the number of edge nodes in the single list of v vertices {d++; p=p->nextarc; } return d; } int Degree2(AdjGraph *G,int v) {int I,d1=0,d2=0,d; ArcNode *p; If (v < 0 | | v > = G - > n) return 1; P =G-> adjList [v]. Firstarc; while (p! =NULL) // count the number of edge nodes in a single linked list {d1++; p=p->nextarc; } for (i=0; i<G->n; {p=G->adjlist[I]. Firstarc; while (p! If (p->adjvex==v) d2++; p=p->nextarc; } } d=d1+d2; return d; }Copy the code

2.6 the main function

int main(int argc, char** argv) { AdjGraph *G; int n=5,e=7,i; Int A [MAXVEX] [MAXVEX] = {{0,1,2,6, INF}, {INF, 0, INF, 4, 5}, {INF, INF, 0, INF, 3}, {INF, INF, INF, 0, INF}, {INF, INF, INF, 7, 0}}; CreateGraph(G,A,n,e); // Set up the adjacency list printf(" memory structure of graph G :\n"); DispGraph(G); Printf (" Degree of all vertices in graph G :\n"); Printf (" vertex \t degree \n"); for (i=0; i<G->n; i++) printf(" %d\t%d\n",i,Degree2(G,i)); DestroyGraph(G); return 0; }Copy the code

The time relation blogger won’t show the effect, just copy this code over

Conclusion:

Figure in the store we learn about, adjacency matrix was a storage vertex array and a two dimensional array, a two-dimensional array to subscript to said vertex and edge connection, have this side to put the two subscripts array assignment 1, 0, no assignment adjacency list is have more than one list, one used to hold head node, Each header points to a linked list that is used to store the index of the array of vertices. ** ** Good this article blogger finish school, pass is not easy, praise attention comment collection, thank you!!