Acwing-Algorithm Basic Course-Notes (9)

Acwing-Algorithm Basic Course-Notes (9)

Search and Graph Theory (3)

This section explains the minimum spanning tree and bipartite graph

Minimum spanning tree

What is the minimum spanning tree? 1. given an undirected connected graph G with n nodes and m edges.

Then the undirected connected graph composed of all n nodes and n-1 edges is called a spanning tree of G. Among all spanning trees of G, the spanning tree with the smallest sum of edge weights is It is called the minimum spanning tree of G.

There are two common algorithms:

  • Prim algorithm (prime)

    • Simple version of Prim (time complexity O(n^2^), suitable for dense graphs)
    • Heap optimized version Prim (time complexity O(mlogn), suitable for sparse graphs)
  • Kruskal algorithm (Kruskal)

    Suitable for sparse graphs, time complexity O(mlogm)

For the minimum spanning tree problem, if it is a dense graph, the naive Prim algorithm is usually used because its idea is simpler and the code is shorter. If it is a sparse graph, the Kruskal algorithm is usually used because its idea is simpler and clearer than Prim. The heap optimized version of Prim is usually not used much.

Prim algorithm

Here only talk about the plain version of Prim. The algorithm flow is as follows

(Where the collection

s
Indicates that all points currently in the connected block)

1. Initialize the distance, initialize the distance of all points to + 2. n cycles 1. t <- find the closest point that is not in the set s 2. Use t to update the distance from other points to the set s 3. Add t to the set s Copy code

Note that the distance from a point t to the set s refers to if the point t and three points in the set s are connected by an edge. Then the distance from the point t to the set s is the weight of the edge with the smallest weight among the edges where t is connected to the 3 points.

Practice picture: acwing-858: Prim algorithm for minimum spanning tree

Solution: (C++)

# include <iostream> # include <cstring> using namespace std ; const int N = 510 , INF = 0x3f3f3f3f ; int n, m; int g[N][N], d[N]; bool visited[N]; void prim () { memset (d, 0x3f , sizeof d);//Initialization distance is positive infinity int sum = 0 ; for ( int i = 1 ; i <= n; i++) { //loop n times //choose The point with the smallest distance set s int t = 0 ; for ( int j = 1 ; j <= n; j++) { if (!visited[j] && d[j] <= d[t]) t = j;//Use <= here to avoid making special judgments on the first point selection } if (i == 1 ) d[t] = 0 ; //The first point added to the set, the distance to the set is 0 if (d[t] == INF) { //The distance of the selected point is positive infinity , Invalid printf ( "impossible\n" ); return ; } //Put this point in the set s visited[t] = true ; sum += d[t]; //This time I put it in //Update the distance from other points to the set s, for ( int j = 1 ; j <= n; j++) { if (!visited[j] && g [t][j] != INF && g[t][j] <d[j]) { d[j] = g[t][j]; } } } printf ( "%d\n" , sum); } int main () { memset (g, 0x3f , sizeof g); scanf ( "%d%d" , &n, &m); while (m--) { int x, y, w; scanf ( "%d%d %d" , &x, &y, &w); g[x][y] = min(g[x][y], w); g[y][x] = g[x][y]; } prim(); return 0 ; } Copy code

Solution: (Java)

import java.util.Scanner; /** * @Author yogurtzzz * @Date 2021/6/28 16:43 **/ public class Main { static int INF = 0x3f3f3f3f ; static Scanner scanner = new Scanner(System.in); public static void main (String[] args) { int n = readInt(), m = readInt(); int [][] g = new int [n + 1 ][n + 1 ]; for ( int i = 1 ; i <= n; i++) for ( int j = 1 ; j <= n; j++) g[i][j] = INF; while (m--> 0 ) { int u = readInt(), v = readInt(), w = readInt(); g[v][u] = g[u][v] = Math.min(g[u][v], w); //undirected graph, with two edges } int res = prim(g, n); if (res == INF) System.out.println( "impossible" ); else System.out.println(res); } static int prim ( int [][] g, int n) { int [] d = new int [n + 1 ]; boolean [] st = new boolean [n + 1 ]; for ( int i = 0 ; i < n + 1 ; i++) d[i] = INF; int sum = 0 ; //The sum of the edge weights of the minimum spanning tree //loop n times, each time selecting a point that is not in the set s, but the smallest distance to the set s for ( int i = 1 ; i <= n; i++ ) { //Traverse, find a point that is not in s and has the smallest distance int t = 0 ; for ( int j = 1 ; j <= n; j++) { if (!st[j] && d[j] < = d[t]) t = j; } if (i == 1 ) d[t] = 0 ; //The first selected point, the distance should be 0 if (d[t] == INF) return INF; //If the selected point is to the set The distance is positive infinity, it means that there is no connection sum += d[t]; //add this edge to the spanning tree st[t] = true ; //add point t to the set s //update other points to the set Distance, update only the edges connected to t for ( int j = 1 ; j <= n; j++) { if (!st[j] && g[t][j] != INF && d[j]> g[ t][j]) { d[j] = g[t][j]; } } } return sum; } static int readInt () { return scanner.nextInt(); } } Copy code

Kruskal algorithm

The basic idea:

  1. First sort all edges according to weight, from small to large

  2. Enumerate each edge from small to large (a, b, w)

    If a and b are not connected, add this edge to the set (connect point a and point b)

At the beginning of Kruskal's algorithm, it is equivalent to all points are independent, without any edges.

Kruskal does not need to use an adjacency list or adjacency matrix to store the graph, it only needs to store all the edges.

In fact, it is a simple application of union search, you can refer to acwing-837: the number of points in connected blocks

Practice questions: acwing-859: Kruskal algorithm for minimum spanning tree

Solution: (C++)

# include <iostream> # include <cstring> # include <algorithm> using namespace std ; const int N = 1e5 + 10 , M = 2e5 + 10 ; struct Edge { int a, b, w; bool operator <( const Edge& W) { return w <Ww; } } edges[M]; int n, m; int p[N]; int find ( int x) { if (x != p[x]) p[x] = find(p[x]); return p[x]; } void kruskal () { //Sort all edges from smallest to largest first sort(edges, edges + m); int totalW = 0 , edgeCtn = 0 ; //enumerate all edges for ( int i = 0 ; i <m; i++) { int a = edges[i].a, b = edges[i].b, w = edges[i].w; a = find(a); b = find(b); if (a != b) { //If a and b are not connected, add this edge p[a] = b; //connect a and b totalW += w; edgeCtn++; } } if (edgeCtn == n- 1 ) printf ( "%d\n" , totalW); else printf ( "impossible\n" ); } int main () { scanf ( "%d%d" , &n, &m); for ( int i = 0 ; i <m; i++) { int a, b, w; scanf ( "%d%d%d" , &a, &b, &w); edges[i] = {a, b, w}; } for ( int i = 1 ; i <= n; i++) p[i] = i; kruskal(); return 0 ; } Copy code

Solution: (Java)

import java.util.Arrays; import java.util.Scanner; /** * @Author yogurtzzz * @Date 2021/6/30 16:42 **/ public class Main { static class Edge implements Comparable < Edge > { int a, b, w; public Edge ( int a, int b, int w) { this .a = a; this .b = b; this .w = w; } @Override public int compareTo (Edge o) { return w-ow; } } static Scanner scanner = new Scanner(System.in); public static void main (String[] args) { int n = readInt(), m = readInt(); Edge[] edges = new Edge[m]; int [] p = new int [n + 1 ]; for ( int i = 0 ; i <m; i++) { int a = readInt(), b = readInt() , w = readInt(); edges[i] = new Edge(a, b, w); } //Initialize all points are isolated for ( int i = 1 ; i <= n; i++) p[i] = i; kruskal(edges, n, m, p); } static void kruskal (Edge[] edges, int n, int m, int [] p) { //1. 1. sort all edges according to the weight from small to large Arrays.sort(edges); int totalWeight = 0 , edgeCtn = 0 ; //2. Traverse all edges for ( int i = 0 ; i <m; i++) { int a = edges[i].a, b = edges[i].b, w = edges[i].w; a = find(a, p); b = find(b, p); if (a != b) { //a and b are not connected yet, then connect p[a] = b; totalWeight += w; edgeCtn++; } } //If there is a minimum spanning tree, the total number of edges added is n-1 if (edgeCtn == n- 1 ) System.out.println(totalWeight); else System.out.println( "impossible" ); } static int find ( int x, int [] p) { if (x != p[x]) p[x] = find(p[x], p); return p[x]; } static int readInt () { return scanner.nextInt(); } } Copy code

binary picture

First of all, what is a bipartite graph?

A bipartite graph means that all points in a graph can be divided into left and right parts, so that all edges in the graph are connected from the points in the left set to the points in the right set. There are no edges inside the left and right sets. The icon is as follows

This section talks about two parts, namely the coloring method and the Hungarian algorithm .

The coloring method is implemented by depth-first traversal, and the time complexity is O(n m); the time complexity of the Hungarian algorithm is theoretically O(n m), but the actual running time is generally much less than O(n m) .

An important property in graph theory: a graph is a bipartite graph, if and only if the graph does not contain odd rings

Odd-numbered ring refers to the odd number of edges in this ring. (The number of edges and the number of points in the ring are the same)

In a ring, suppose there are 4 points (even number) in total, because the bipartite graph requires that the points in the same set cannot be connected to each other.

Then point 1 belongs to set A, point 2 connected to point 1 should belong to set B, point 3 connected to point 2 should belong to set A, and point 4 connected to point 3 should belong to set B. Point 1 connected to point 4 should belong to set A. This can be dichotomy.

If the number of points in the ring is an odd number, it is assumed that point 1 belongs to set A at the beginning. After pushing around the ring, you will find that point 1 should belong to set B. This is a contradiction. So if there are odd rings, this graph must not be dichotomy.

You can use the coloring method to determine whether a graph is a bipartite graph. Use depth-first traversal to color each node in the graph from the root node. Each node is either black or white (2 types), as long as the coloring process If there is no contradiction, it means that the graph is a bipartite graph; otherwise, it is not a bipartite graph.

Dyeing method

Practice questions: acwing-860: Judging bipartite graphs by dyeing method

First wrong solution

# include <iostream> # include <cstring> # include <algorithm> using namespace std ; const int N = 1e5 + 10 , M = 2e5 + 10 ; //Use adjacency table to store graph int h[N], e[M ], ne[M], idx; int n, m; int color[N]; void add ( int x, int y) { //The head insertion method of the linked list e[idx] = y; ne[idx] = h[x]; h[x] = idx++; } bool dfs ( int x) { //Deep search all child nodes of this node for ( int i = h[x]; i != -1 ; i = ne[i]) { int u = e[i];//Child node if (color[u] == -1 ) { //If the child node has not been dyed, it is dyed directly and searched deeply color[u] = !color[x]; if (!dfs(u)) return false ; } else if (color[u] == color[x]) return false ; //If the color of the child node and the parent node are the same, it means a contradiction } //After the deep search is over, there is no contradiction, then the dyeing is successful, and the judgment is the bipartite graph return true ; } int main () { memset (h, -1 , sizeof h);//Initialize an empty linked list memset (color, -1 , sizeof color);//Initialize the color to -1, which means it has not been dyed scanf ( "%d% d" , &n, &m); while (m--) { int x, y; scanf ( "%d%d" , &x, &y); add(x, y); //undirected graph, add two edges add(y, x); } color[ 1 ] = 0 ; //Color point 1 first. //You can t directly dfs from one point, because the whole graph may not be a connected graph //and other connected blocks are not necessarily bipartite graphs //so to 1 ~ n all points sequentially stained IF (the DFS ( 1 )) printf ( "Yes/the n-" ); the else printf ( "No/the n-" ); return 0 ; } Copy code

It is not possible to perform dfs directly from one point, because the entire graph may not be a connected graph. If you perform dfs from one point, you can only color the connected blocks where this point is located, and you cannot touch other connected blocks. The connected block of is not necessarily a bipartite graph, so all the points from 1 to n must be colored sequentially to ensure that all points are colored.

The correct solution is as follows

# include <iostream> # include <cstring> # include <algorithm> using namespace std ; const int N = 1e5 + 10 , M = 2e5 + 10 ; //Since it is an undirected graph, two edges need to be built, so the number of edges Set to 2 times //Use the adjacency list to store the graph int h[N], e[M], ne[M], idx; //Note the implementation of the singly linked list here, the array size is M int n, m; int color[N]; void add ( int x, int y) { //The head insertion method of the linked list e[idx] = y; ne[idx] = h[x]; h[x] = idx++; } bool dfs ( int x) { //Deep search all child nodes of this node for ( int i = h[x]; i != -1 ; i = ne[i]) { int u = e[i];//Child node if (color[u] == -1 ) { //If the child node has not been dyed, it is dyed directly and searched deeply color[u] = !color[x]; if (!dfs(u)) return false ; } else if (color[u] == color[x]) return false ; //If the color of the child node and the parent node are the same, it means a contradiction, and the self-loop should also be a contradiction? } //After the deep search is over, there is no contradiction, then the dyeing is successful, and the judgment is the bipartite graph return true ; } int main () { memset (h, -1 , sizeof h);//Initialize an empty linked list memset (color, -1 , sizeof color);//Initialize the color to -1, which means it has not been dyed scanf ( "%d% d" , &n, &m); while (m--) { int x, y; scanf ( "%d%d" , &x, &y); add(x, y); add(y, x); } bool flag = true ; //Color all points in turn for ( int i = 1 ; i <= n; i++) { if (color[i] == -1 ) { //The point is not yet colored, just go straight Coloring, just dye a color (0 or 1), and after dfs, dfs is completed, the connected block where this point is located is dyed color[i] = 0 ; //do dfs, if you are doing this If there is a contradiction in the coloring process of connected blocks, then directly break if (!dfs(i)) { flag = false ; break ; } } } if (flag) printf ( "Yes\n" ); else printf ( "No\n" ); return 0 ; } Copy code

Problem solution: Java

import java.util.*; /** * @Author yogurtzzz * @Date 2021/6/30 16:42 **/ public class Main { static Scanner scanner = new Scanner(System.in); static int [] h, e, ne; static int idx; static int [] color; public static void main (String[] args) { int n = readInt(), m = readInt(); h = new int [n + 1 ]; e = new int [ 2 * m + 1 ]; ne = new int [ 2 * m + 1 ]; color = new int [n + 1 ]; Arrays.fill(h, -1 ); while (m--> 0 ) { int a = readInt(), b = readInt(); add(a, b); add(b, a); } boolean flag = true ; //dyed for ( int i = 1 ; i <= n; i++) { if (color[i] == 0 ) { //not yet dyed color[i] = 1 ; //dyed if (!dfs(i)) { //Deep search, after the end of the deep search, all points of the connected block where the point is located will be colored flag = false ; break ; } } } if (flag) System.out.println( "Yes" ); else System.out.println( "No" ); } static boolean dfs ( int x) { for ( int i = h[x]; i !=- 1 ; i = ne[i]) { int u = e[i]; if (color[u] == 0 ) { //Not yet dyed, dye directly color[u] = 3 -color[x]; //Deep search after dyeing if (!dfs(u)) return false ; } else if (color[u] == color[x]) return false ; } return true ; } static void add ( int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx++; } static String readString () { return scanner.next(); } static int readInt () { return scanner.nextInt(); } } Copy code

Homework Questions: acwing-257: Detaining Criminals

You can use bipartite graphs to do it, or you can use union search

//TODO copy code

Hungary algorithm

The Hungarian algorithm is used to find the maximum matching of the bipartite graph given a bipartite graph.

Given a bipartite graph G, in a subgraph M of G, any two edges in the edge set of M are not attached to the same vertex, then M is said to be a match . That is, each point is connected by only one edge, and there is no point, and multiple edges are connected at the same time. (Refer to the example of yxc: boys and girls are in love pairing, how many pairs can you make together)

The group of matches with the largest number of edges among all matches is called the maximum match of the bipartite graph. The number of edges is the maximum number of matches. Assuming a bipartite graph, some nodes on the left half represent boys, and some nodes on the right half represent girls. A boy node and a girl node are connected by an edge, which means that the two people have an emotional basis and can develop into a couple. When we put a pair of men and women into a pair, it is called the two nodes match. The core idea of the Hungarian algorithm is : we enumerate all boys (nodes) on the left half, and each time we try to find an object for the current boy. Let's first find all the girls that this guy likes. (That is, find all the nodes on the right side connected by this node). Traverse these girls, when a girl is not paired with other boys, directly match this girl with this boy. Then the boy is paired successfully. When the girl has been paired with other boys, try to find a spare tire for the girl s boyfriend. If this girl s boyfriend has other alternative spare tires. Then pair the girl's boyfriend with her spare tire. Then pair this girl with the current boy. Look for it like this...

Practice questions: acwing-861: the largest matching of bipartite graphs

# include <iostream> # include <cstring> # include <algorithm> using namespace std ; const int N = 1010 , M = 1e5 + 10 ; int h[N], e[M], ne[M], idx; int match[N]; bool st[N]; //state variables int n1, n2, m; void add ( int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx++; } //Find a girlfriend for a boy bool find ( int x) { //Find all the girls that the boy likes for ( int i = h[x]; i != -1 ; i = ne[i]) { int u = e[i]; //The girl s node number if (st[u]) continue ; //If the girl has been marked, skip st[u] = true ; //First mark the girl so that Skip this girl in subsequent recursion if (match[u] == 0 || find(match[u])) { //If the current girl is not matched, or can find another backup for the boy who has been matched by this girl Tire, you can match[u] = x; return true ; } } return false ; //I still can't find a circle } int main () { memset (h, -1 , sizeof h); scanf ( "%d%d%d" , &n1, &n2, &m); while (m--) { int a, b; scanf ( "% d%d" , &a, &b); add(a, b); //only connect from the left half to the right half } //enumerate all points on the left half int res = 0 ; for ( int i = 1 ; i <= n1; i++) { //every time a boy finds a girlfriend, clear the state variable memset (st, false , sizeof st); if (find(i)) res++; } printf ( "%d\n" , res); return 0 ; } Copy code

After-school questions: acwing-372: Chess and cards placement

//TODO copy code

summary

There are two main algorithms related to bipartite graphs

  • Coloring method: is used to judge whether a graph is a bipartite graph
  • Hungarian algorithm: it is used to find the maximum matching of the bipartite graph