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!