One, graph storage

Generally speaking, graphs can be stored in two ways: adjacency matrix and adjacency list. This section deals only with the form of an adjacency matrix.

Let the vertex labels of graph G(V,E) be 0,1… , n-1, then the two dimensions of the two-dimensional array G[N][N] can represent the vertex labels of the graph respectively, that is, if G[I][j] is 1, it means that there are edges between vertex I and vertex j; If G[I][j] is 0, then there are no edges between vertices I and j, and the two-dimensional array G[][] is called an adjacency matrix. In addition, if edge weights exist, then G[I][j] can store edge weights and set edge weights to 0, -1, or a large number for nonexistent edges. The diagram below:

　　

 

 

2. Depth-first Search (DFS)

Depth-first searches use “depth” as the first keyword, and each time they follow the path to the point where they can go no further, they fall back to the nearest fork in the road.

The basic idea of a DFS traversal graph is to set a vertex as visited, and not process it the next time the vertex is recursively encountered until the entire graph is marked as visited. The code is as follows:

1 int n, G[MAXV][MAXV]; Int vis[MAXV] = {0}; int vis[MAXV] = {0}; Void DFS(int u, int depth) {6 vis[u] =1; void DFS(int u, int depth) {6 vis[u] =1; // set vertex u to access 7 int v; 8 for(v=0; v<n; ++v) {// iterate over each vertex 9 // if vertex V is not visited and can reach 10 if(! vis[v] && G[u][v] ! = INF) { 11 DFS(v, depth+1); 17 void DFSTrave() {18 int u; 19 for(u=0; u<n; ++u) {// iterate over each vertex 20 if(! Vis [u]) {// If vertex u is not accessed 21 DFS(u, 1); // Access u and its connected block 22} 23} 24}Copy the code

 

 

 

Shortest path

Shortest path is a classic problem in graph theory: given graph G(V, E), find a path from the beginning to the end, so that the sum of the edge weights of all the edges passing along this path is minimized.

Common algorithms to solve the shortest path problem include Dijkstra algorithm and Floyd algorithm.

1. The Dijkstra algorithm

Dijkstra algorithm is used to solve the single-source shortest path problem, that is, given graph G and starting point S, the shortest distance from S to every other vertex can be obtained through the algorithm. The basic idea of Dijkstra is to set set S on graph G(V,E) to store the visited vertices, and then select the vertex (u) with the shortest distance to the starting point S from set V-S every time to access and join set S. Then, let vertex U be the intermediate point, and optimize the shortest distance between vertex V that can be reached from the starting point of u. This operation is performed n times (n is the number of vertices) until set S contains all vertices.

In order to write the code conveniently, we need to find a way to implement the two key things in the basic idea, namely the implementation of the set S and the minimum distance from the starting point S to the vertex Vi (0≤ I ≤n-1).

    1. The set S can be implemented with an array vis[] of type int, representing vertex V when vis[I]==1iHas been accessed. Vis [I]==0 represents vertex ViNot accessed.
    2. Let d[] indicate that s reaches ViIn the shortest path of s, all vertices are initially assigned a large number except d[s] of the starting point S, which is 0.

The code is as follows:

1 int n, G[MAXV][MAXV]; Int vis[MAXV] = {0}; int vis[MAXV] = {0}; Vis [I]=1 3 int d[MAXV]; 6 void Dijkstra(int s) {7 int I, j; 8 for(i=0; i<MAXV; D [I] = INF; 10 } 11 d[s] = 0; For (I =0; i<n; ++ I) {// int u=-1, MIN=INT_MAX; For (j=0; j<n; ++j) {15 if(! vis[j] && d[j] < MIN) { 17 u = j; 18 MIN = d[j]; 19 } 20 } 21 if(u == -1) return; Vis [u] = 1; // mark that node u has accessed 23 int v; 24 for(v=0; v<n; ++v) {25 // Not accessible, reachable, path length can be optimized vis[v] && G[u][v]! = INF && d [u] [u] [v] < d + G [v]) {27 / / optimization path length 28 d [v] [u] = d + G [u] [v]; 29} 30} 31} 32}Copy the code

 

If they give you an undirected edge, you just think of an undirected edge as two opposite directed edges. For an adjacency matrix, an undirected edge between u and v can be input with the same edge weights to G[u][v] and G[v][u] respectively.

We’ve been solving for the shortest distance, but we haven’t talked about solving for the shortest path itself. So let’s learn how to find shortest paths.

In Dijkstra we have this code:

1 int v; 2 for(v=0; v<n; ++v) {3 // Not accessible, reachable, path length can be optimized vis[v] && G[u][v]! = INF && d [u] [u] [v] < d + G [v]) {5 / / optimization path length 6 d [v] [u] = d + G [u] [v]; 8 7}}Copy the code

 

 

 

That is, the solution to making d[v] smaller is to have u as the previous vertex from s to v (that is, s→… To u, v). This gives us an idea: write this information down. We can then set the array pre[] so that pre[v] represents the number of the previous vertex of v on the shortest path from starting s to vertex V. The code is as follows:

1 int n, G[MAXV][MAXV]; Int vis[MAXV] = {0}; int vis[MAXV] = {0}; Vis [I]=1 3 int d[MAXV]; Int pre[MAXV]; int pre[MAXV]; 7 void Dijkstra(int s) {8 int I, j; 9 for(i=0; i<MAXV; ++ I) {// I = 0 d[I] = 0; 11 pre[i] = i; D [s] = 0; d[s] = 0; For (I =0; i<n; ++ I) {// int u=-1, MIN=INT_MAX; For (j=0; j<n; ++j) {17 if(! vis[j] && d[j] < MIN) { 19 u = j; 20 MIN = d[j]; 21 } 22 } 23 if(u == -1) return; Vis [u] = 1; // indicate that node u has accessed 25 int v; 26 for(v=0; v<n; ++v) {27 // Not accessible, reachable, path length can be optimized 28 if(! vis[v] && G[u][v]! = INF && d [u] [u] [v] < d + G [v]) {29 / / optimization path length 30 d [v] [u] = d + G [u] [v]; 31 pre[v] = u; U 32} 33} 34} 35}Copy the code

 

 

 

 

At this step, the precursor of each node on the shortest path is only worked out, requiring the whole path. It is necessary to continuously search for the precursor using the information of Pre [] from the termination node until it reaches the starting point and starts to output from the depth of recursion. The code is as follows:

2 void Path(int s, int v) {3 if(s == v) {4 printf("%d\n", s); 4 printf("%d\n", s); 5 return; 6 } 7 Path(s, pre[v]); Printf ("%d\n", v); // After returning from the deepest level, output the vertex number of each layer 9}Copy the code

 

 

 

 

The test code is as follows:

1 /* 2 graph algorithm 3 */ 4 5 #include <stdio.h> 6 #include <string.h> 7 #include <math.h> 8 #include <stdlib.h> 9 #include <time.h> 10 #include <limits.h> 11 12 #define MAXV 1000 13 #define INF 0x3fffffff 14 15 int n, m, s; Int G[MAXV][MAXV]; Int vis[MAXV] = {0}; // If vertex I is accessed, vis[I]=1 18 int d[MAXV]; Int pre[MAXV]; int pre[MAXV]; Void DFS(int u, int depth) {23 vis[u] = 1; void DFS(int u, int depth) {23 vis[u] = 1; Printf ("%d ", u); 25 int v; 26 for(v=0; v<n; ++v) {// traverses each vertex 27 // If vertex V is not visited and can reach 28 if(! vis[v] && G[u][v] ! = INF) { 29 DFS(v, depth+1); 35 void DFSTrave() {36 memset(vis, 0, sizeof(vis)); 37 int u; 38 for(u=0; u<n; ++u) {// iterate over each vertex 39 if(! Vis [u]) {// If vertex u is not accessed 40 DFS(u, 1); 46 void Dijkstra(int s) {47 int I, j; 48 for(i=0; i<MAXV; D [I] = INF; 50 pre[i] = i; 51} 52 d[s] = 0; For (I =0; i<n; Int u=-1, MIN=INT_MAX; For (j=0; j<n; ++j) {56 if(! vis[j] && d[j] < MIN) { 58 u = j; 59 MIN = d[j]; 60 } 61 } 62 if(u == -1) return; Vis [u] = 1; // indicate that node u has accessed 64 int v; 65 for(v=0; v<n; ++v) {66 // Not accessible, reachable, path length is optimized 67 if(! vis[v] && G[u][v]! = INF && d [u] [u] [v] < d + G [v]) {/ 68 / optimization path length 69 d = d [v] [u] [u] [v] + G; 70 pre[v] = u; // u 71} 72} 73} 74} 75 76 77 void Path(int s, int v) {78 if(s == v) {79 printf("%d\n", s); 80 return; 81 } 82 Path(s, pre[v]); Printf ("%d\n", v); 85 86 int main() {87 int u, v, w; / / start node and end node, weights 88 the scanf (" % d % d % d ", & n, & m, & s); For (u=0; u<MAXV; ++u) { 90 for(v=0; v<MAXV; ++v) { 91 G[u][v] = INF; 92 } 93 } 94 int i; 95 for(i=0; i<m; ++ I) {// Input edge 96 scanf("%d %d %d", &u, &v, &w); 97 G[u][v] = w; 98 } 99 Dijkstra(s); For (I =0; i<n; Printf ("%d ", d[I]); printf("%d ", d[I]); 102 } 103 printf("\n"); 104 Path(0, 5); // find the shortest path 105 DFSTrave(); // Depth-first search 106 107 return 0; 108}Copy the code

 

 

 

 

However, more often than not, there is more than one path with the shortest distance from the starting point to the end point. In this case, the problem will give a second ruler (the first ruler is the distance) and ask you to choose the path with the best second ruler among all the shortest paths. The second scale is commonly used in the following three methods or a combination of them:

    1. Add another edge weight (such as cost) to each edge, and then minimize the sum of costs along the path if there are multiple shortest paths.
    2. Add one point weight to each point (such as the amount of goods each city can collect), and then maximize the sum of point weights along the path if there are multiple shortest paths.
    3. I’m just asking you how many paths there are.

For each of the three methods, you only need to add an array to hold the new edge weights or point weights or the number of shortest paths, and then modify the d[v] optimization step in Dijkstra’s algorithm, leaving the rest unchanged.

  1. Added edge weights. Take the newly added edge weight representing cost as an example, cost[u][v] is used to represent the cost of u→v (input from the problem), and add an array C [], c[u] represents the minimum cost c[u] from the starting point S to the vertex U. Initially, only C [s] is 0, and the rest c[u] are INF. The code is as follows: 
    For (v=0; v<n; ++v) {3 // no access, up to 4 if(! vis[v] && G[u][v]! = {5 INF) if (d [u] [u] [v] < d + G [v]) {/ / u as intermediary can make 6 d d [v] better [v] [u] = d + G [u] [v]; 7 c[v] = c[u] + cost[u][v]; 8} else if (d + G [u] [u] [v] [v] = = d & c [u] + cost [u] [v] < c [v]) {9 / / at the same time to see if the shortest distance "to make c [v] better [u] [v] c = c + cost [u] [v]; 11} 12} 13}Copy the code

     

  2. Add point weights. Take the newly added point weight as an example to represent the materials that can be collected in the city, use weight[u] to represent the number of materials in the city u (input by the question), and add an array w[], w[u] means that the maximum materials that can be collected from the starting point S to the vertex u is W [u], Initially, only w[s] is weight[s], and the rest w[u] is 0. The code is as follows: 
    For (v=0; v<n; ++v) {3 // no access, up to 4 if(! vis[v] && G[u][v]! = {5 INF) if (d [u] [u] [v] < d + G [v]) {/ / u as intermediary can make 6 d d [v] better [v] [u] = d + G [u] [v]; 7 w[v] = w[u] + weight[v]; 8} else if (d + G [u] [u] [v] = = d [v] [u] && w + weight > w [v] [v]) {9 / / at the same time to see if the shortest distance "to make better w [v] [u] [v] = 10 w w + weight [v]; 11} 12} 13}Copy the code

     

  3. Find the number of shortest paths. You only need to add an array num[]. Num [u] represents the number of shortest paths from the starting point S to the vertex U. At the beginning, only num[s] is 1 and the rest num[u] are 0. The code is as follows: 
    For (v=0; v<n; ++v) {3 // no access, up to 4 if(! vis[v] && G[u][v]! = {5 INF) if (d [u] [u] [v] < d + G [v]) {/ / u as intermediary can make 6 d d [v] better [v] [u] = d + G [u] [v]; 7 num[v] = num[u]; 8} else if (d + G [u] [u] [v] = = d [v]) {9 / / and the shortest distance in accumulative num 10 num + = [v] num [u]; 11} 12} 13}Copy the code

     

    　　

2. Floyd algorithm

Floyd algorithm is used to solve the all-source shortest path problem, that is, given graph G(V,E), find the shortest path length between any two points u and V, and the time complexity is O(n3).

The algorithm is based on the fact that: When dis[I][k] + dis[k][j] < dis[I][j], when dis[I][k] + dis[k][j], Dis [I][j] = dis[I][k] + dis[k][j] (dis[I][j] is the shortest distance from vertex I to vertex j) The code is as follows:

5 #include <stdio.h> 6 #include <string.h> 7 #include <math.h> 8 #include <stdlib.h> 9 #include  <time.h> 10 11 #define INF 0x3fffffff 12 #define MAXV 200 13 int n, m; Int dis[MAXV][MAXV]; Void Floyd() {17 int I, j, k; 18 for(k=0; k<n; ++k) { 19 for(i=0; i<n; ++i) { 20 for(j=0; j<n; ++j) { 21 if(dis[i][k]! =INF && dis[k][j]! =INF && dis[i][k]+dis[k][j]<dis[i][j]) { 22 dis[i][j] = dis[i][k]+dis[k][j]; Int main() {30 int u, v, w; 31 scanf("%d %d", &n, &m); Int I, j; 33 for(i=0; i<n; ++ I) {// initialize dis array 34 for(j=0; j<n; ++j) { 35 dis[i][j] = INF; 36 } 37 dis[i][i] = 0; 38 } 39 for(i=0; i<m; + + I) {/ / edge input data of 40 the scanf (" % d % d % d ", & u, & v, & w); 41 dis[u][v] = w; 42 } 43 Floyd(); For (I =0; i<n; ++ I) {// For (j=0; j<n; ++j) { 46 if(dis[i][j] ! = INF) { 47 printf("%d ", dis[i][j]); 48 } else { 49 printf("INF "); 50 } 51 } 52 printf("\n"); 53 } 54 55 return 0; 56}Copy the code

 

 

 

 

Minimum spanning tree

Minimum spanning tree is to find a tree T in a given undirected graph G(V, E), such that the tree has all vertices in graph G, all edges come from edges in graph G, and satisfy the minimum sum of edge weights of the whole tree.

 

1. The prim algorithm

Prim algorithm is used to solve the problem of minimum spanning tree. Its basic idea is to set set S on graph G(V, E) to store the visited vertices, and then select the vertex (u) with the shortest distance to set S from set V-S every time to access and put into set S. Then, let vertex u be the intermediate point, and optimize the shortest distance between all vertices V reachable from u and set S. This operation is performed n times (n is the number of vertices) until set S contains all vertices.

The algorithm needs to realize two key concepts, namely, the realization of set S and the shortest distance between vertex Vi (0≤ I ≤n-1) and set S.

    1. The set S is implemented as in Dijkstra, using an array vis[] of type int to indicate whether a vertex has been accessed. Where VIS [I] == 1 represents vertex ViHas been accessed. 0 indicates that it has not been accessed.
    2. Let d[] hold vertex ViThe shortest distance from S. Initially, all vertices are assigned a large number, that is, unreachable, except for d[s] of the starting point S, which is assigned 0.

It can be found that prim algorithm and Dijkstra algorithm use almost exactly the same idea, except for the difference in the meaning of array D []. The code is as follows:

1 /* 2 figure _Prim algorithm 3 */ 4 5 #include <stdio.h> 6 #include <string.h> 7 #include <math.h> 8 #include < stlib. H > 9 #include <time.h> 10 11 #define MAXV 1000 12 #define INF 0x3fffffff 13 14 int n, m, G[MAXV][MAXV]; Int d[MAXV]; Int vis[MAXV] = {0}; 19 int prim() {20 int I, j; 21 d[0] = 0; // initialize d array 22 for(I =1; i<n; [I] = 0;} // if (I = 0, I = 0) { 24 } 25 int ans = 0; For (I =0; i<n; ++ I) {// int u=-1, MIN=INF; For (j=0; j<n; ++j) {29 // no access and less weight 30 if(! vis[j] && d[j]<MIN) { 31 u = j; 32 MIN = d[j]; 33 } 34 } 35 if(u == -1) return -1; Vis [u] = 1; Ans += d[u]; // Add the smallest edge to the minimum spanning tree 38 int v; 39 for(v=0; v<n; ++v) {// If (! vis[v] && G[u][v]! =INF && G[u][v]<d[v]) { 42 d[v] = G[u][v]; 43 } 44 } 45 } 46 return ans; 47 } 48 49 int main() { 50 int u, v, w; 51 scanf("%d %d", &n, &m); Int I, j; 53 for(i=0; i<n; For (j=0; j<n; ++j) { 55 G[i][j] = INF; 56 } 57 } 58 for(i=0; i<m; ++i) { 59 scanf("%d %d %d", &u, &v, &w); 60 G[u][v] = G[v][u] = w; } 62 int ans = prim(); Printf ("%d\n", ans); 64 65 return 0; 66}Copy the code

 

 

 

 

2. Kruskal algorithm

The basic idea of Kruskal algorithm is to hide all edges in the graph in the initial state, so that each vertex in the graph becomes a connected block by itself. Then perform the following steps:

    1. Sort all edges by edge weight from smallest to largest.
    2. Test all edges according to edge weight from small to large. If the two vertices connected by the current test edge are not in the same connected block, add this test edge to the current minimum spanning tree; Otherwise, discard the edge.
    3. Perform Step 2 until the minimum number of edges in the spanning tree is equal to the total number of vertices minus 1 or all edges are tested. If the number of edges in the minimum spanning tree is less than the total number of vertices minus 1, it indicates that the graph is not connected.

Let’s solve the problem of code implementation.

The first is the definition of an edge. For Kruskal algorithm, because it is necessary to judge whether the two endpoints of the edge are in different connected blocks, the numbers of the two endpoints of the edge must be needed. And the algorithm involves edge weight, so edge weight must also have. So the definition is as follows:

Typef struct {3 int u, v; // int cost; // 5} edge; 6 edge E[MAXE]; / / setCopy the code

 

 

 

 

We also need to customize the CMP function of qsort to sort array E by edge weight from smallest to largest:

1 int CMP (const void* a, const void* b) {3 edge* c = (edge*)a; 4 edge* d = (edge*)b; 5 return c->cost - d->cost; 6}Copy the code

 

 

 

 

There are two other details that don’t seem intuitive, namely

    1. How to determine if the two endpoints of the test edge are in different connected blocks.
    2. How to add test edges to the minimum spanning tree.

If each connected block is treated as a set, then the problem can be transformed to determine whether two endpoints are in the same set, which can be used to look up the set. And the search set can be used to determine whether the two nodes are in the same set by querying whether the root of the set is the same. The merge function can solve the second detail mentioned above, that is, as long as the two endpoints of the test edge are merged, the edge can be added to the minimum spanning tree.

1 int father[MAXV]; 4 int father (int x) {5 int a = x; // save the node 6 while(x! = father[x]) {// father[x] = father[x]; } 9 // Go through the process of finding the root node again. = father[a]) { 11 int z = a; A = father[a]; Father [z] = x; // change the parent of all nodes to root x 14} 15 16 return x; // n is the number of points, m is the number of edges, Int krustal(int n, int m) {21 int ans=0, Num_Edge=0; 23 int i; 24 for(i=0; i<n; ++i) { 25 father[i] = i; 28 qsort(E, m, sizeof(E[0]), CMP); 29 for(i=0; i<m; ++i) { 30 int faU = findFather(E[i].u); Int faV = findFather(E[I].v); int faV = findFather(E[I].v); 32 if(faU ! Father [faU] = faV; // father[faU] = faV; // merge set 34 ans += E[I].cost; // Num_Edge++; If (Num_Edge == n-1) break; 37 } 38 } 39 if(Num_Edge ! = n-1) return -1; // There are multiple connected blocks 40 else return ans; // Return the sum of the minimum spanning tree edge weights 41}Copy the code

 

 

 

 

The test code is as follows:

5 #include <stdio.h> 6 #include <string.h> 7 #include <math.h> 8 #include <stdlib.h> 9 #include <time.h> 10 11 #define MAXV 110 12 #define MAXE 10010 14 // int cost; } edge; 19 edge E[MAXE]; Int father[MAXV]; 24 int CMP (const void* a, const void* b) {25 edge* c = (edge*)a; 26 edge* d = (edge*)b; 27 return c->cost - d->cost; 31 int father (int x) {32 int a = x; // save 33 while(x! = father[x]) {// father[x] = father[x]; 35} 36 // Go through the process of finding the root. = father[a]) { 38 int z = a; A = father[a]; Father [z] = x; // change the parent of all nodes to root x 41} 42 43 return x; // n = number of points, m = number of edges, 47 int krustal(int n, int m) {49 int ans=0, Num_Edge=0; 49 int ans=0, Num_Edge=0; 50 int i; 51 for(i=0; i<n; ++i) { 52 father[i] = i; 55 qsort(E, m, sizeof(E[0]), CMP); 56 for(i=0; i<m; ++i) { 57 int faU = findFather(E[i].u); Int faV = findFather(E[I].v); int faV = findFather(E[I].v); 59 if(faU ! Father [faU] = faV; // father[faU] = faV; Ans += E[I].cost; // Num_Edge++; 63 if(Num_Edge == n-1) break; 64 } 65 } 66 if(Num_Edge ! = n-1) return -1; // There are multiple connected blocks 67 else return ans; 69 70 int main() {71 int n, m; Scanf ("%d %d", &n, &m); 73 int i; 74 for(i=0; i<m; ++i) { 75 edge t; 76 scanf("%d %d %d", &t.u, &t.v, &t.cost); 77 E[i] = t; 78 } 79 int ans = krustal(n, m); 80 printf("%d\n", ans); 81 82 return 0; 83}Copy the code

 

 

 

Input:

6. 1 1 2 2 1 3 3 6 2 5 5 5 4 5 5 4 4 5 5Copy the code

 

 

 

Output:

11Copy the code