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 n1 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
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: acwing858: 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:
First sort all edges according to weight, from small to large
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 acwing837: the number of points in connected blocks
Practice questions: acwing859: 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 wow;
}
}
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 n1
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 depthfirst 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
Oddnumbered 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 depthfirst 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: acwing860: 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 selfloop 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: acwing257: 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: acwing861: 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
Afterschool questions: acwing372: 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