title: Chain Forward Star Storage Graph, Hungarian Algorithm for Bipartite Matching Template & Analysis (Storage)
link: Chain Forward Star Storage Graph, Hungarian Algorithm for Bipartite Matching Template & Analysis (Storage)
catalog: true
lang: en
date: 2020-10-23 13:34:43
subtitle: The topic of training 8 during the summer vacation is bipartite matching. Since I have never tried chain forward star storage graph before, I also learned chain forward star storage graph before learning this algorithm (although bipartite graph algorithm generally does not use this storage method).
tags:
- c++
- bipartite matching
- chain forward star
categories: - [Notes, Data Structures]
Reference blog: Chain Forward Star - The Most Understandable Explanation, Algorithm Explanation: Bipartite Matching [Graph Theory], Hungarian Algorithm, Hungarian Algorithm and Augmenting Paths
I forgot to post it during the summer vacation 2333
@[TOC](Table of Contents)
1. Chain Forward Star#
1. What is it#
If the adjacency list is difficult to write but efficient, and the adjacency matrix is easy to write but inefficient, then the chain forward star is a relatively moderate data structure. The chain forward star is better, but the efficiency is not high. After optimizing to the chain forward star, the efficiency has been greatly improved. Although the use of chain forward star in the world is not very extensive, it is still an excellent data structure when you don't want to write a complex adjacency list.
- Excerpt from Baidu Baike
The chain forward star is actually a statically built adjacency list, a special edge set array, with a time efficiency of O(m) and a space efficiency of O(m). The traversal efficiency is also O(m), and it can conveniently find all adjacent edges of each node.
2. How to Store the Graph#
We need the following arrays:
- head[i] array, which represents the index of the first edge with i as the starting point. It is usually initialized as -1, indicating that there are no edges with this edge as the starting point.
- edge[i] structure array, where edge[i].to represents the end point of the i-th edge, edge[i].Next represents the storage position of the next edge with the same starting point as the i-th edge, and edge[i].w represents the edge weight.
Definition and Initialization#
const int maxn = 10000; // maximum number of vertices
int N, M, mcnt; // number of vertices, number of edges
int head[maxn]; // the index of the first edge with i as the starting point in the edge array
struct Edge {
int to, w, Next; // end point, edge weight, index of the next edge with the same starting point
} edge[maxn];
void init() {
memset(head, -1, sizeof(head));
mcnt = 0;
}
Add Edge#
void add_edge(int u, int v, int w) {
edge[mcnt].to = v;
edge[mcnt].w = w;
edge[mcnt].Next = head[u]; // assign the index of the next edge to Next
head[u] = mcnt++; // update the head array
}
Traversal#
for(int i = 1; i <= N; ++i) {
for(int j = head[i]; j != -1; j = edge[j].Next) { // traverse the edges with i as the starting point
// other operations
}
}
2. Bipartite Matching#
1. Bipartite Graph#
According to Baidu Baike:
A bipartite graph, also known as a bipartite set, is a special model in graph theory. Given a graph G=(V,E), if the vertices V can be divided into two disjoint subsets (A,B), and each edge (i,j) in the graph is associated with two vertices i and j belonging to these two different subsets (i in A, j in B), then the graph G is called a bipartite graph.
In simple terms, a graph is divided into two parts, and there are only edges between different parts, and there are no edges between the same parts.
2. Matching#
- Given a bipartite graph G, in a subgraph M of G, if any two edges in the edge set {E} of M are not attached to the same vertex, then M is called a matching.
- Maximal Matching is a matching in which it is not possible to increase the number of matching edges by adding unmatched edges under the current completed matching.
- Maximum Matching is the largest matching among all maximal matchings. The subset of edges with the largest number of edges is called the maximum matching of the graph.
- If every vertex in a matching is associated with an edge in the graph, the matching is called a complete matching or perfect matching.
- If P is a path in graph G that connects two unmatched vertices and the edges on P alternate between belonging to M and not belonging to M, then P is called an augmenting path relative to M.
3. Hungarian Algorithm#
The Hungarian algorithm can be used in bipartite matching except for multiple matching in bipartite graphs. It is almost the core algorithm of bipartite matching. In fact, it is a kind of network flow algorithm, and its core is to find an augmenting path. The specific operation is well... matching.
For more details, you can refer to this blog: Hungarian Algorithm
Here is a summary: Seize the opportunity, and if there is no opportunity, create one and seize it
Core Code#
Recursive function to find a girl【not really】
bool find(int x){
int i,j;
for (j=1;j<=m;j++){ // scan each girl
if (line[x][j]==true && used[j]==false)
// if there is an ambiguous relationship and it has not been marked yet (the mark here means that the attempt to change the ownership of the girl has been made in this search, but it was not successful, so there is no need to waste time)
{
used[j]=1;
if (girl[j]==-1 || find(girl[j])) {
// if the girl is single or there is a place available, use recursion
girl[j]=x;
return true;
}
}
}
return false;
}
In the main program, scan each boy, and note that used needs to be cleared to 0
for (i=1;i<=n;i++)
{
memset(used,0,sizeof(used)); // clear it in each step
if find(i) all+=1;
}
Several Example Problems#
A - Fire Net#
Problem Description and Approach#
Description:
Given an N*N city map, "." represents a small castle that can shoot in four directions, "X" represents a wall that can block the shots. Place as many small castles as possible in the city so that no two small castles can destroy each other. The configuration of the small castle is legal only if there are no two small castles located on the same horizontal or vertical line, unless there is at least one wall separating them.
Approach:
First, traverse each row. If there is a wall in the middle, it is considered as a different column and is treated as an X region in the bipartite graph. Then traverse each column. If there is a wall in the middle, it is considered as a different row and is treated as a Y region in the bipartite graph. edge[i][j] represents whether there is an edge between point i in the X region and point j in the Y region. Find the maximum matching of this bipartite graph (the small castle is placed at the intersection of rows and columns, and the intersection is unique). Obviously, using adjacency matrix to store the converted graph is more convenient and efficient...
Code#
Note that the col array needs to be initialized as -1
// A - Fire Net
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;
#define div 1000000007
const int maxn = 1005;
const int inf = 0x3f3f3f;
int N,M,rcnt,ccnt,ans;
string str;
struct Vertex {
char flag;
int r, c; // the real row and column where the point is located
}map[maxn][maxn],now;
int edge[maxn][maxn];
int col[maxn];
bool used[maxn];
void init() {
rcnt = ccnt = ans = 0;
memset(used, 0, sizeof(used));
memset(col, -1, sizeof(col));
memset(edge, 0, sizeof(edge));
}
bool find_x(int x) {
for(int j = 0; j < ccnt; ++j) {
if(edge[x][j] == 1 && !used[j]) {
used[j] = true;
if(col[j] == -1 || find_x(col[j])) {
col[j] = x;
return true;
}
}
}
return false;
}
int main(){
ios::sync_with_stdio(false);
while(cin >> N && N) {
init();
for(int i = 0; i < N; ++i) {
cin >> str;
for(int j = 0; j < N; ++j) {
map[i][j].flag = str[j];
}
}
for(int j = 0; j < N; ++j, ++ccnt) {//each column
for(int i = 0; i < N; ++i) {
if(map[i][j].flag == 'X' && i+1 < N && map[i+1][j].flag != 'X')
++ccnt; //each column with no connection is considered as a different column
map[i][j].c = ccnt;
}
}
for(int i = 0; i < N; ++i, ++rcnt) {//each row
for(int j = 0; j < N; ++j) {
if(map[i][j].flag == 'X' && j+1 < N && map[i][j+1].flag != 'X')
++rcnt; //each row with no connection is considered as a different row
map[i][j].r = rcnt;
}
}
for(int i = 0; i < N; ++i) {
for(int j = 0; j < N; ++j) {
if(map[i][j].flag == '.') {
now = map[i][j];
edge[now.r][now.c] = 1;
}
}
}
for(int i = 0; i < rcnt; ++i) {
memset(used, 0, sizeof(used));
if(find_x(i)) ans++;
}
cout << ans << endl;
}
return 0;
}
B - The Accomodation of Students#
Problem Description and Approach#
Description:
Given n students and m pairs of students who know each other. Divide the students into two groups so that any two students in the same group do not know each other. If this goal can be achieved, arrange them in double rooms. Please note that only students who are known can live in the same room, which means that only known students can live in the same room. Calculate the maximum number of pairs that can be arranged in these double rooms.
Approach:
Use the coloring method to determine whether it is a bipartite graph, and use the Hungarian algorithm for matching.