大纲
最小生成树 对应的图一般为无向图
Prim算法:
稠密图:朴素版Prim算法 O(n^2)
稀疏图:堆优化版Prim算法 O(mlogn) 不常用
Cruskal算法
O(mlogm): 常用在稀疏图
二分图
染色法(判别是否是二分图) O(n + m)
匈牙利算法(求二分图最大匹配)o(mn) 但实际运行时间一般远小于O(mn)
朴素版Prim算法 稠密图
思想
假设初始所有边均未连接,以某一点开始,逐步找各顶点上权值最小的边来构建生成树
流程:
1.把所有距离初始化成正无穷
2.n次迭代:
找到集合外距离集合最近的点加入集合
用该点更新其他点到 集合 的距离(在dijkstra中更新的是到 起点 的距离 )
int g[N][N];
int dist[N];
bool st[N];
int Prim()
{
memset(dist,0x3f,sizeof dist);
int res = 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(i && dist[t] == INF) return INF; //如果不是第一个加入的点,或者距离为INF则不连通
if(i) res += dist[t];
for(int j=1;j<=n;j++) dist[j] = min(dist[j],g[t][j]); //此处不同于dijkstra
st[t] = true;
}
return res;
}
Cruskal算法 O(mlogm) 稀疏图
思想
令最小生成树初始状态为只有n个顶点而无边的非连通图;
将所有边按权值排序,每次选择权值最小的边;
若该边所依附的顶点在不同的连通分量上,则将该边加入生成树集合
否则,选择下一条代价最小的边进行判断
流程
1.将所有边按权重从小到大排序 O(mlogm)常数很小,所以效果很好
2.枚举每一条边ab,权重为c:
若ab不连通:将这条边加入到集合中
步骤2(利用并查集):连通块中点的数量
代码
struct Edge
{
int a,b,w;
bool operator< (const &W)const
{
return w < W.w;
}
}
int kruskal()
{
sort(edges,edges+m);
for(int i=1;i<=n;i++) p[i] = i;
int res = 0,cnt = 0;
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)
{
res += w;
cnt ++;
p[a] = b;
}
}
if(cnt < n-1) return INF;
else return cnt;
}
重载运算符<:
第一个const,即const Nodea表示的是nodea必须为const;第二个const,即函数声明之后的那个const,
表示的是运算符<可以被const类型的nodeb调用。有了这两个const,才能满足两个const类型的元素进行比较。
染色法 O(n+m)
二分图
一个无向图的所有顶点能被分为不同的子集,并且图中的每条边所联系的两个顶点都属于
不同的顶点集,则称这个图位二分图;边都在两集合之间,集合内部没有边;
二分图不一定是连通图
染色
给定无向连通图和m种不一样的颜色。用这些颜色为图G的各顶点着色,每一个顶点着一种颜色。
是否有一种着色法使G中每条边的两个顶点有不一样的颜色。
不含有奇数环,染色过程一定没有矛盾;
性质(充要条件)
一个图是二分图:当且仅当图中不含奇数环;即当且仅当图能被2染色
思想
对n个节点遍历,如果节点i没有染色,便用dfs(代码少)对i所在的连通块染色;
ps:二分图不一定是连通图;
dfs染色法
int h[N],e[M],ne[M],idx;
int color[N];
bool dfs(int u,int c) //编号u,染成c色
{
color[u] = c; //对c染色
for(int i = h[u];i != -1;i = ne[i])
{
int j = e[i];
if(!color[j])
{
if(!dfs(j,3-c)) return false; //染成1或者2色,3-c可自动将1和2互换;
}
else if(color[j] == c) return false;
}
return true;
}
匈牙利算法 O(mn)实际时间远小于O(mn)
ps: 唯一一个稠密图用邻接表存储的算法;因为只需要访问男生的邻居,不需要访问另一组的邻居;
原理
给定一个二分图,求二分图的最大匹配
匹配:在二分图G的一个子图M中,M的边集{E}的任意两条边都不依附于同一个顶点
理解
一堆男生和一堆女生,互相有边则相当于有好感;
当一对男女相互有好感,且男生和女生没有再和别人匹配在一起时;
即男生和女生都很专一,没有脚踏两条船时,则称该男生和女生匹配成功
一个人只能有一个对象
思路
遍历所有男生进行匹配;对于每个男生:
每次询问所有有好感并且能预定的女生,若该女生单身,则匹配;
否则询问当前女生的对象能否换对象,若可以换,则仍和这个女生匹配,否则放弃;
代码
int h[N],e[M],ne[M],idx;
int march[N]; //记录女生匹配的对象编号
bool st[N]l; //记录女生是否可以预定;仅当男生拱手相让时才会出现不能预定
bool find(int x)
{
for(int i=h[x];i != -1;i = ne[i])
{
int j = e[i];
if(!st[j])
{
st[j] = true;
if(march[j] == 0 && find(march[j])) return true;
}
}
return false;
}
int main()
{
// -------略
int res = 0
for(int i=1;i<=n;i++)
{
if(find(i)) res ++;
}
printf("%d\n",res);
}