The recent epidemic situation in Xi'an is indeed serious. I received a notice from the school this morning that all students should return to the dormitory for isolation. I hope the epidemic situation will pass as soon as possible. At the same time, I also pay tribute to those epidemic prevention personnel who are fighting on the front line.

Near the end of the term, I have to review as soon as possible. Today, I will write an article about graphs.

The first is storage. I choose the storage method of adjacency matrix,

The defined storage structure should include the following:

1. For the vertex information of the graph, to put it bluntly, that is, the name of the vertex. I choose the character type.

2. The relationship between edges is stored in a two-dimensional array, such as Ai and Aj. If there is an edge connected between them, then a[i][j]=w, where w represents the weight. If there is no edge, it is set to infinity (infinity here). I defined it in advance in the macro definition

3. Number of vertices and edges, because the number of vertices and edges can be input next

4. I define the type of graph as shaping, 0 as undirected graph and 1 as directed graph, so if undirected graph a[i][j]=a[j][]i], it should be well figured out

Then let's take a look at the structure I defined. I won't say much. I'll go directly to the code

#define MAX 10 / / define the maximum number of vertices #define INFINITY 65535 / / define infinity typedef struct { char vexs[MAX];//Define vertex information int arc[MAX][MAX];//Define edge relationships int numVertexes;//Define vertex number int numEdges;//Define the number of edges int type;//Define directed graph or undirected graph }MGraph;//chart

The one-dimensional array in the book stores vertex information, and the two-dimensional array defines edge relationship

Before understanding the search, you also need to define a one-dimensional array to mark the visited vertices. After reading the following search process, you will understand why you need this tag array.

int visited[MAX];//Mark vertices that have been accessed //0 means you haven't accessed it yet, and 1 means you have accessed it. Remember to initialize it before searching!

So let's create a picture

void Create(MGraph * G) { int i,j,k,w; printf("Please enter the number of vertices and edges of the graph:\n"); scanf("%d%d",&G->numVertexes,&G->numEdges); fflush(stdin); for(i=0;i<G->numVertexes;++i) { printf("No.%d Vertices: ",i+1); scanf("%c",&G->vexs[i]);//Enter a name for the vertex getchar(); } for(i=0;i<G->numVertexes;++i)//There is no relation before initializing the edge relation matrix input { for(j=0;j<G->numVertexes;++j) { G->arc[i][j]=INFINITY;//It doesn't matter until you enter it } } for(k=0;k<G->numEdges;++k) { printf("Input edge( Vi,Vj)Superscript and subscript of i,j And right w(Space separated): "); scanf("%d%d%d",&i,&j,&w); G->arc[i][j]=w; if(G->type==0)//Judge undirected graph and directed graph { G->arc[j][i]=G->arc[i][j]; } } }

So let's take a look at search after we understand the relevant knowledge of storage.

Depth first search is adopted for search. In my summary, it is:

First, you have to understand the traversal of the graph:

Traversal of a graph refers to the process of traversing a graph from a vertex, visiting other vertices in the graph, and making each vertex in the graph accessed only once

Basic idea of depth first search:

1. Starting from a vertex V0 in the figure, first access v0

2. Find the first unreachable adjacency point of the vertex just accessed, and then access the vertex. Take this vertex as a new vertex and repeat this step until the newly accessed vertex has no adjacent points that are not accessed

3. Return to the vertex of the previous visited and there is still no unreachable adjacency point, find the next unreachable adjacency point of the vertex, and access the vertex. Then proceed to step 2

If it is a non connected graph, there must be some vertices in the graph that have not been accessed. Select another vertex from the graph that has not been accessed as the starting point, and repeat the above process

Please understand these basic ideas by yourself. Look at the video, draw with a pen, and then think about it, and then digest and understand it slowly. I remember that when I first learned the linked list at that time.

Then the next step is the search function

//Depth first traversal void DFS(MGraph G, int i) { int j; visited[i]=1;//Once this vertex is accessed, it is assigned a value of 1 printf("%c->",G.vexs[i]); for(j=0;j<G.numVertexes;++j)//Here you search for vertices that are connected to this vertex and have not been accessed { if(G.arc[i][j]==1&&!visited[j]) { DFS(G,j); } } } void DFStraverse(MGraph G) { int i; for(i=0;i<G.numVertexes;++i) { visited[i]=0;//Initialization of search tags } for(i=0;i<G.numVertexes;++i) { if(!visited[i]) { DFS(G,i); } } }

ok, so that you can finally see it, let's output the input adjacency table. You can understand it as soon as you read it

//For you to see more clearly, we also output the adjacency matrix by the way void Output(MGraph * G) { int i,j,count=0; for(i=0;i<G->numVertexes;++i) { printf("\t%c",G->vexs[i]);//Output vertex name horizontally first } printf("\n"); for(i=0;i<G->numVertexes;++i) { printf("%4c",G->vexs[i]);//Each line outputs the vertex information first for(j=0;j<G->numVertexes;++j) { printf("\t%d",G->arc[i][j]);//Output the edge relationship of each vertex count++; if(count%G->numVertexes==0)//Basic operation of line feed,, { printf("\n"); } } } }

Then you can finally call the main function

int main() { MGraph G; int i,j; printf("Enter the type of generated graph(Undirected graph 0/Directed graph 1): "); scanf("%d",&G.type); Create(&G); printf("\n"); DFStraverse(G); printf("\n Graph traversal completed"); printf("\n Output of adjacency matrix:\n"); Output(&G); }

Here is the complete code

#include<stdio.h> #include<stdlib.h> #define MAX 10 / / define the maximum number of vertices #define INFINITY 65535 / / define infinity typedef struct { char vexs[MAX];//Define node information int arc[MAX][MAX];//Define edge relationships int numVertexes;//Define vertex number int numEdges;//Define the number of edges int type;//Define directed graph or undirected graph }MGraph;//chart int visited[MAX];//Mark vertices that have been accessed void Create(MGraph * G) { int i,j,k,w; printf("Please enter the number of vertices and edges of the graph:\n"); scanf("%d%d",&G->numVertexes,&G->numEdges); fflush(stdin); for(i=0;i<G->numVertexes;++i) { printf("No.%d Vertices: ",i+1); scanf("%c",&G->vexs[i]); getchar(); } for(i=0;i<G->numVertexes;++i)//There is no relationship between the input of the initialization edge relationship matrix { for(j=0;j<G->numVertexes;++j) { G->arc[i][j]=INFINITY; } } for(k=0;k<G->numEdges;++k) { printf("Input edge( Vi,Vj)Superscript and subscript of i,j And right w(Space separated): "); scanf("%d%d%d",&i,&j,&w); G->arc[i][j]=w; if(G->type==0)//Judge undirected graph and directed graph { G->arc[j][i]=G->arc[i][j]; } } } //Depth first traversal void DFS(MGraph G, int i) { int j; visited[i]=1; printf("%c->",G.vexs[i]); for(j=0;j<G.numVertexes;++j)//Here you search for vertices that are connected to this vertex and have not been accessed { if(G.arc[i][j]==1&&!visited[j]) { DFS(G,j); } } } void DFStraverse(MGraph G) { int i; for(i=0;i<G.numVertexes;++i) { visited[i]=0; } for(i=0;i<G.numVertexes;++i) { if(!visited[i]) { DFS(G,i); } } } //For you to see more clearly, we also output the adjacency matrix by the way void Output(MGraph * G) { int i,j,count=0; for(i=0;i<G->numVertexes;++i) { printf("\t%c",G->vexs[i]); } printf("\n"); for(i=0;i<G->numVertexes;++i) { printf("%4c",G->vexs[i]); for(j=0;j<G->numVertexes;++j) { printf("\t%d",G->arc[i][j]); count++; if(count%G->numVertexes==0) { printf("\n"); } } } } int main() { MGraph G; int i,j; printf("Enter the type of generated graph(Undirected graph 0/Directed graph 1): "); scanf("%d",&G.type); Create(&G); printf("\n"); DFStraverse(G); printf("\n Graph traversal completed"); printf("\n Output of adjacency matrix:\n"); Output(&G); }

ok, after the battle, you can run the test below:

Enter the type of generated graph(Undirected graph 0/Directed graph 1): 0 Please enter the number of vertices and edges of the graph: 5 4 No.1 Vertices: 0 No.2 Vertices: 1 No.3 Vertices: 2 No.4 Vertices: 3 No.5 Vertices: 4 Input edge( Vi,Vj)Superscript and subscript of i,j And right w(Space separated): 0 1 2 Input edge( Vi,Vj)Superscript and subscript of i,j And right w(Space separated): 1 2 4 Input edge( Vi,Vj)Superscript and subscript of i,j And right w(Space separated): 0 2 6 Input edge( Vi,Vj)Superscript and subscript of i,j And right w(Space separated): 4 3 8 0->1->2->3->4-> Graph traversal completed Output of adjacency matrix: 0 1 2 3 4 0 65535 2 6 65535 65535 1 2 65535 4 65535 65535 2 6 4 65535 65535 65535 3 65535 65535 65535 65535 8 4 65535 65535 65535 8 65535 -------------------------------- Process exited after 91.99 seconds with return value 0 Please press any key to continue. . . ok,That's all for sharing in this issue. Thank you! If there are mistakes, please correct them in time. I hope you can make progress together! Finally, please go there early. I want to go home for the New Year!