图论–最小生成树
本小章节的内容颇多，但是董事很经典的内容，由于主包也是一名实用主义，所以不适用的知识我们也直接不讲了！
我们的最小生成树内容有如下
啊，图上也打对叉了，这个Prim堆优化版本十分不常用，一般都是用克鲁斯卡尔来代替，因为克鲁斯卡尔时间复杂度比它快个常数倍，然后苏里还很好理解。
二分图也是一个很常考，很重要的算法，在这里一并讲解了。
最小生成树：
Prim（朴素版本）
克鲁斯卡尔
二分图
染色法
匈牙利算法
点击上方专辑试试呢！
最小生成树
Prim（朴素版本）
Prim算法是一个很经典的找最小生成树问题，其板子如下
P3366 【模板】最小生成树 – 洛谷
其做法就是先建图这个图论的很多问题都是先建图，之后直接进入Prim函数来运行，那么我们的Prim怎么做呢？首先我们把所有的点都初始化为INF，只有点1的距离是0，那么对于n个点，我们遍历n次，对于每一个点，如果它没有被标记过，并且它如果是找到的第一个没被标记的点，或者这个点比上一个点距离更加近，那么我们就把指针变到j，最后如果没找到或者这个点的距离是正无穷，那么肯定是不符合题意的，直接退出函数输出orz，否则我们就把这个最小距离的点标记为true，紧接着我们对于长度进行记录累加，然后我们对于这个最近点的一些连接点进行遍历，更新其一些点的最小距离。这整一个过程遍历n遍就行了。(等我们代码写出来，会发现，它的代码逻辑和Dijkstra十分相似)
#include<bits/stdc++.h>
using namespace std;
const int N=5010;
const int INF=0x3f3f3f3f;
int n,m;
int g[N][N];
int dist[N];
bool st[N];
int ans=0;
void prime()
{
memset(dist,0x3f,sizeof dist);
dist[1]=0;
ans=0;
for(int i=0;i<n;i++)
{
int t=–1;
for(int j=1;j<=n;j++)
if(!st[j]&&(t==–1||dist[t]>dist[j]))
t=j;
if(t==–1||dist[t]==INF) {
ans=–1;
return;
}
st[t]=true;
if(i) ans+=dist[t];
for(int j=1;j<=n;j++) {
if(!st[j]&&g[t][j]<dist[j]) dist[j]=g[t][j];
}
}
}
int main()
{
cin>>n>>m;
memset(g,0x3f,sizeof g);
for(int i=0;i<m;i++)
{
int a,b,c;
cin>>a>>b>>c;
g[a][b]=min(g[a][b],c);
g[b][a]=min(g[b][a],c);
}
prime();
if(ans==–1) cout<<"orz"<<endl;
else cout<<ans<<endl;
}
这个过程和Dijkstra基本一致，但是由于一个是最短路径，一个是最小生成树，所以这里写法会有点不同，但是我们理解起来就很好了。
克鲁斯卡尔算法
这个算法可以处理边稀疏问题，并且时将复杂度上也比Prim好一个log级别，它的思路和Prim不同的是，那个是找从一个集合出发的最短路径，而这个算法我们找的是整局的最短路径，只要不会造成重复和成环，最终我们只要达到n个点选择n-1个点就行了。
堆，还有一点区别就是，Prim算法一般都是给你一个点进行选择线段来生成最小树，而克鲁斯卡尔是不给你点，让你自己来选选择一个点，所以还有这点差别，并运用了并查集的知识。首席按选择最短边这个过程我们就需要进行结构体排序，然后我们进行遍历结构体的一个一个点，进行并查集来判断这个点是否已经在一个集合里面，要是不在，我们就要它并累加权值，最后我们输出累加权值就行了。
其一个很标准的题目：挖沟
它就是一个很标准的克鲁斯卡尔板子题目，先定义一个结构体，然后输入之后我们进行排序，之后先初始化所有点的跟是自己，然后进行遍历所有边，对于边的两个点，我们看看他们的根是不是一个，不是我们就选，然后把他们连接起来(连城一个根)，然后累加权值，如果选了n-1个边我们就提前结束(剪枝)，最后输出权值和就行了。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=100005;
int n,m;
int p[N];
struct node{
int u,v,w;
};
vector<node> g;
bool cmp(node a,node b)
{
return a.w<b.w;
}
int find(int x){
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
signed main()
{
cin>>n>>m;
for(int i=0;i<m;i++)
{
int u,v,w;
cin>>u>>v>>w;
g.push_back({u,v,w});
}
sort(g.begin(),g.end(),cmp);
for(int i=1;i<=n;i++) p[i]=i;
int ans=0;
int cnt=0;
for(int i=0;i<m;i++)
{
int u=g[i].u,v=g[i].v,w=g[i].w;
u=find(u),v=find(v);
if(u!=v){
p[u]=v;
ans+=w;
cnt++;
if(cnt==n–1) break;
}
}
cout<<ans<<endl;
}
二分图
染色法
一个十分经典的算法，其而二分图可将顶点集合划分为两个独立集，且所有边均连接不同集合的图。
那么对于不是二分图的，即不能构成，那么就是会成为奇环，由于我们染色法的规则是相邻的颜色不同，而如果有一个奇环那么必定会起冲突
对于这个图形来讲，我们的1点可以用二分图的染色法进行染色，但是最终会把1染成1或者2，这样就起冲突了，所以它就够不成二分图，那么对于染色判别我们就也知道了。
【模板】二分图结构Ⅰ-A ‖ 染色判定：DFS_牛客题霸_牛客网
这里有一道很经典的用染色法判断二分图模型，那么就根据之前所说染色方法，判断是不是二分图。
首先就是建图，然后定义一个color数组来存每一个点的颜色，然后我们遍历n个点，来判断它们的每个颜色是不是空的，要是空的我们就判断它的分支有没有奇环，来一个find的bool函数，那么这么find函数怎么判断呢？首先颜色我们先给它染上，然后遍历它的所有点，如果它的点被染上颜色并且和它颜色一样，那么肯定是奇环，直接退出false，要是没染色，在判断它的分支是不是奇环，是就直接退出false，最后判断玩所以，就退出为true。
这个过程的思路就是递归，然后一层一层进，一层一层出，一层一层判断来实现。
#include<bits/stdc++.h>
using namespace std;
const int N=300005;
vector<int> g[N];
int color[N];
int n,m;
bool find(int x,int cnt)
{
color[x]=cnt;
for(int v:g[x]){
if(color[v]==0){
if(!find(v,3–cnt)) return false;
}else if(color[v]==cnt) return false;
}
return true;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
for(int i=1;i<=n;i++)
{
if(color[i]==0){
if(!find(i,1)){
cout<<"NO"<<endl;
return 0;
}
}
}
cout<<"YES"<<endl;
return 0;
}
匈牙利算法
这个算法就是在我们同个染色法进行分组之后，我们来进行匹配问题的过程。
P3386 【模板】二分图最大匹配 – 洛谷
这里的一道模板题是在二分图构建完成后的匹配问题。我们思路就是建图，然后遍历每一个点看看有没有适合的匹配，有就累加，最后输出数量，那么这个判断适合的过程怎么办呢？我们再定义一个判断函数，对于这个函数而言，我们遍历这个点的所有连接点，如果它的连接点被判断过直接结束这次循环，然后就是判断这个点是否已经被连接，没有被连接或者已经被链接，但是我们能通过find函数再找到一个能和它匹配的，那么这个点就可以被我们判断进来的这个点所连接。
整个过程还是运用了递归思想，就是说如果你的"心上人"已经梅花有主了，但是她的另一半还有"暗恋者"，那么我们就看看他的”暗恋者“是不是无主之人，如果是就直接匹配，如果不是那么接着递归判断她的"心上人"是不是还有"暗恋着"，这样最终我们就可以达到尽可能多的所有人都有匹配对。
#include<bits/stdc++.h>
using namespace std;
const int N=510;
vector<int> g[N];
int match[N];
bool st[N];
int n,m,e;
bool find(int x)
{
for(int v:g[x])
{
if(st[v]) continue;
st[v]=true;
if(match[v]==0||find(match[v])){
match[v]=x;
return true;
}
}
return false;
}
int main()
{
cin>>n>>m>>e;
for(int i=1;i<=e;i++)
{
int u,v;
cin>>u>>v;
g[u].push_back(v);
}
int res=0;
for(int i=1;i<=n;i++)
{
memset(st,false,sizeof st);
if(find(i)) res++;
}
cout<<res<<endl;
return 0;
}
学完这么多的知识，可以试着做一些图论相关题了，现在我们看到之后不至于一点思路都没有了。这些内容虽然不多，但是更多的是理解本质，如果真的理解了，那么其实也可以一句不说自在理解。
