Search and Graph Theory (III)
This section covers minimum spanning trees and binary graphs
Minimum spanning tree
What is a minimum spanning tree? First, an undirected connected graph G with n nodes and m edges is given.
Then, an 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 called the minimum spanning tree of G.
There are two common algorithms:
-
Prim algorithm (Prim)
- Naive Prim (time complexity O(n^2^), for dense graphs)
- Heap-optimized Prim (Time complexity O(Mlogn) for sparse graphs)
-
Kruskal algorithm (Kruskar)
Suitable for sparse graph, time complexity O(Mlogm)
For the minimum spanning tree problem, if it is a dense graph, the naive version of Prim algorithm is usually used, because its ideas are concise and the code is short; if it is a sparse graph, Kruskal algorithm is usually used, because its ideas are simpler and clearer than Prim. Heap-optimized versions of Prim are usually not used very much.
Prim algorithm
I’m just going to talk about the plain version of Prim. The algorithm flow is as follows
(where, set S represents all points that are currently in the connected block)
1. Initialize the distance, initialize the distance of all points to +∞ 2. N times loop 1. Use t to update the distance from other points to set S. 3. Add t to set SCopy the codeNote that the distance between a point t and set S is the same as that between t and three points in set S. The distance between t and s is the weight of the least weighted edge of the three points that connect T.
Practice figure: ACwing-858: Prim algorithm for minimum spanning tree
(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(a) {
memset(d, 0x3f.sizeof d); // Initialize the distance to infinity
int sum = 0;
for(int i = 1; i <= n; i++) {
// loop n times
// select the point with the smallest distance from set s
int t = 0;
for(int j = 1; j <= n; j++) {
if(! visited[j] && d[j] <= d[t]) t = j;// use <= to avoid making a special judgment on the first selection
}
if(i == 1) d[t] = 0;// The distance from the first point to the set is 0
if(d[t] == INF) {
// The selected point is infinitely distant, invalid
printf("impossible\n");
return;
}
// Put this point in set s
visited[t] = true;
sum += d[t]; // This time
// Update the distance between other points and 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(a) {
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 the codeSolution :(Java)
import java.util.Scanner;
/ * * *@Author yogurtzzz
* @Date2021/6/28 departed * * /
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 minimum spanning tree edge weights
// Loop n times, each time select a point not in set s, but the smallest distance from set s
for(int i = 1; i <= n; i++) {
// 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 distance from the first point should be 0
if (d[t] == INF) return INF; // If the distance between the selected points and the set is infinity, then there is no connection
sum += d[t]; // Add this edge to the spanning tree
st[t] = true; // add point t to set s
// Update the distance from other points to set, only the edge 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(a) {
returnscanner.nextInt(); }}Copy the codeKruskal algorithm
Basic idea:
So let’s sort all the edges, by weight, from smallest to largest
Enumerate each edge from small to large (a, b, w)
If a and B are disconnected, add this edge to the set.
At the beginning of Kruskal’s algorithm, all points are independent without any edges.
Kruskal doesn’t need an adjacency list or an adjacency matrix to store the graph, just all the edges
In fact, it is a simple application of parallel search set, can refer to ACwing-837: the number of connected block midpoints
Exercise: ACwing-859: Kruskal algorithm for minimum spanning tree
(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 < W.w;
}
} 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(a) {
// Sort all edges from smallest to largest
sort(edges, edges + m);
int totalW = 0, edgeCtn = 0;
// Enumerates 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 disconnected, add this edge
p[a] = b; // Connect a to BtotalW += w; edgeCtn++; }}if(edgeCtn == n - 1) printf("%d\n", totalW);
else printf("impossible\n");
}
int main(a) {
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 the codeSolution :(Java)
import java.util.Arrays;
import java.util.Scanner;
/ * * *@Author yogurtzzz
* @Date2021/6/30 * * / calm
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) {
returnw - o.w; }}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 to be 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. Sort all edges by weight from smallest to largest
Arrays.sort(edges);
int totalWeight = 0, edgeCtn = 0;
// 2. Iterate over 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) {// If a and B are not connected, connect themp[a] = b; totalWeight += w; edgeCtn++; }}// If there is a minimum spanning tree, n-1 edges are added
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(a) {
returnscanner.nextInt(); }}Copy the codeBinary chart
First of all, what is a binary graph?
A binary graph is a graph where you can divide all the points in the graph into the left and right so that all the edges of the graph are connected from the points in the set on the left to the points in the set on the right. The left and right sets have no edges inside them. Here is the following
This section covers two parts, namely the dyeing method and the Hungarian algorithm.
The dyeing method is realized by depth-first traversal, and the time complexity is O(n×m). The time complexity of Hungarian algorithm is O(n×m) in theory, but the actual running time is generally far less than O(n×m).
An important property in graph theory: A graph is a bisection graph if and only if the graph contains no odd rings
An odd ring means that the ring has an odd number of edges. (The number of edges in a ring is the same as the number of points)
In a ring, suppose there are four points (an even number), since the binary graph requires that points in the same set cannot be connected to each other.
So point 1 belongs to set A, point 2 connected to point 1 belongs to set B, point 3 connected to point 2 belongs to set A, and point 4 connected to point 3 belongs to set B. Point 1, which is connected to point 4, should be A member of set A. So it can be dichotomized.
If the number of points in the ring is odd, point 1 is supposed to belong to set A at the beginning. After pushing around the ring, point 1 will be found to belong to set B. That’s a contradiction. So if there’s an odd number of cycles, this graph can’t be dichotomized.
The staining method can be used in judging whether a graph is binary chart, using the depth-first traversal, starting from the root node to the dyeing, each node in the graph of each node are either black or white (2), as long as no contradiction in the process of dyeing, illustrate the picture is a binary chart, otherwise, the description is not binary chart.
staining
Exercise: ACwing-860: Dichotomous graph judged by staining method
So let’s do the wrong solution
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10, M = 2e5 + 10;
// Use adjacency lists to store graphs
int h[N], e[M], ne[M], idx;
int n, m;
int color[N];
void add(int x, int y) {
// List header
e[idx] = y;
ne[idx] = h[x];
h[x] = idx++;
}
bool dfs(int x) {
// Search through all the children of this node
for(inti = h[x]; i ! =- 1; i = ne[i]) {
int u = e[i]; / / child nodes
if(color[u] == - 1) {
// If the child node is not yet stained, it is stained directly and searched deeplycolor[u] = ! color[x];if(! dfs(u))return false;
} else if(color[u] == color[x]) return false; // If the color of the child node is the same as that of the parent node, there is a contradiction
}
// When the deep search is complete and no contradiction appears, the staining is successful
return true;
}
int main(a) {
memset(h, - 1.sizeof h); // Initializes the empty linked list
memset(color, - 1.sizeof color); // The color is initialized to -1, indicating that it is not dyed yet
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 spot # 1 first
// DFS cannot be performed directly from a point because the whole graph may not be a connected graph
// Other connected blocks are not necessarily binary graphs
// All points from 1 to n should be stained successively
if(dfs(1)) printf("Yes\n");
else printf("No\n");
return 0;
}
Copy the codeCannot directly from one point to DFS directly, because may be the whole figure is not a connected graph, if at this time from one point to DFS, only put the point where the connecting piece dyeing, unable to reach the other connecting pieces, while the rest of the connecting block does not necessarily is a binary chart, so 1 ~ n all the points in turn to be dyed, make sure that all points have been dyed.
The correct solution is as follows
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10, M = 2e5 + 10; // As an undirected graph, we need to build two edges, so the number of edges is set to 2
// Use adjacency lists to store graphs
int h[N], e[M], ne[M], idx; // Notice the implementation of the single list, the array size is open M
int n, m;
int color[N];
void add(int x, int y) {
// List header
e[idx] = y;
ne[idx] = h[x];
h[x] = idx++;
}
bool dfs(int x) {
// Search through all the children of this node
for(inti = h[x]; i ! =- 1; i = ne[i]) {
int u = e[i]; / / child nodes
if(color[u] == - 1) {
// If the child node is not yet stained, it is stained directly and searched deeplycolor[u] = ! color[x];if(! dfs(u))return false;
} else if(color[u] == color[x]) return false; // If the color of the child node is the same as that of the parent node, then there is a contradiction.
}
// When the deep search is complete and no contradiction appears, the staining is successful
return true;
}
int main(a) {
memset(h, - 1.sizeof h); // Initializes the empty linked list
memset(color, - 1.sizeof color); // The color is initialized to -1, indicating that it is not dyed yet
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) {
// If the point is not stained, it can be stained directly, just dye a random color (0 or 1), and DFS. After DFS is completed, all connected blocks of the point are stained
color[i] = 0;
// If there is a conflict in the process of dyeing the connected block, break it directly
if(! dfs(i)) { flag =false;
break; }}}if(flag) printf("Yes\n");
else printf("No\n");
return 0;
}
Copy the codeAnswer key: Java
import java.util.*;
/ * * *@Author yogurtzzz
* @Date2021/6/30 * * / calm
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;
/ / dyeing
for(int i = 1; i <= n; i++) {
if (color[i] == 0) {
// It has not been stained
color[i] = 1; / / dyeing
if(! dfs(i)) {// After the deep search, all points of the connected block where the point is located will be stained
flag = false;
break; }}}if (flag) System.out.println("Yes");
else System.out.println("No");
}
static boolean dfs(int x) {
for(inti = h[x]; i ! = -1; i = ne[i]) {
int u = e[i];
if (color[u] == 0) {
// Not yet dyed, directly dyed
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(a) {
return scanner.next();
}
static int readInt(a) {
returnscanner.nextInt(); }}Copy the code1. Acwing-257 is a prison for criminals
You can do this using a binary graph, or you can use and look up sets
//TODO
Copy the codeHungarian algorithm
Hungarian algorithm, is given a bisection graph, used to find the maximum match of bisection graph.
Given a bisection graph G, in a subgraph M of G, any two horizon of the edge set of M are not attached to the same vertex, then M is said to be a match. That is, each point has only one edge connected to it, no point has more than one edge connected to it. (Refer to the yXC example: how many couples can you make?)
The set of matches that contains the most edges among all matches is called the maximum match of a binary graph. The number of edges is the maximum number of matches. Suppose a dichotomous graph where the left half of the nodes represent boys and the right half of the nodes represent girls. When a male node and a female node are connected by an edge, it means that the two people have an emotional basis and can develop into a couple. These two nodes are said to match when we make a pair of men and women into a pair. The core idea of the Hungarian algorithm is: we enumerate all the boys on the left side (nodes), and each time we try to find a partner for the current boy. Let’s start by finding all the girls this guy’s interested in. (that is, find all the nodes to the right that this node is connected to). You go over these girls, and when one girl isn’t paired with another guy, you pair this girl with this guy. The boy is matched successfully. When the girl has been paired with another boy, try to find a back-up for the girl’s boyfriend. If the girl’s boyfriend has a backup option. They paired the girl’s boyfriend with her spare. The girl was then paired with the current man. And so on…
Exercise: ACwing-861: Maximum matching of binary 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 guy
bool find(int x) {
// Find out all the girls the guy likes
for(inti = h[x]; i ! =- 1; i = ne[i]) {
int u = e[i]; // Female node id
if(st[u]) continue; // If the girl is already marked, skip it
st[u] = true; // Mark the girl first so that the girl is skipped in subsequent recursions
if(match[u] == 0 || find(match[u])) {
// If the current girl is not matched, or the girl already matched boy can be found a backup
match[u] = x;
return true; }}return false; // Look around, but it doesn't work
}
int main(a) {
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); // Connect only from left to right
}
// Enumerates all points on the left side
int res = 0;
for(int i = 1; i <= n1; i++) {
// Every time you find a girlfriend for a guy, clear the status variable
memset(st, false.sizeof st);
if(find(i)) res++;
}
printf("%d\n", res);
return 0;
}
Copy the codeAcwing-372: Chess and card placement
//TODO
Copy the codesummary
There are two algorithms for binary graph correlation
- Staining is used to determine whether a graph is a binary graph
- Hungarian algorithm: is used to find the maximum match of binary graph