算法--最小生成树和二分图

这里写目录标题

Xmind
最小生成树
- Prim算法
- - 思想
  - 例子+题解
- kruskal算法
- - 思想
  - 例子+题解
二分图
- 染色法
- - 思想
- 二级目录
- 二级目录
一级目录
- 二级目录
- 二级目录
- 二级目录
一级目录
- 二级目录
- 二级目录
- 二级目录
一级目录
- 二级目录
- 二级目录
- 二级目录

Xmind

在这里插入图片描述

最小生成树

Prim算法

思想

在这里插入图片描述
对于dist数组，仍然是一个点到某个东西的距离，只不过这里是到集合的距离
同时我们有一个集合s，表示已经在最小树里的点，表示出来就是数组st[ ]为真或假，某个点的st为真，那么就在集合s中

首先初始化dist数组为正无穷
之后对于遍历n次，
对于每次遍历
找到集合外距离最近的点，实际上就是目前dist[ ]中在s集合之外的最小值的点，给到t
之后用t来更新其他点到集合的距离，实际上是更新dist数组，判断该点到某个点的距离是否小于某个点现有的dist数组的值，如果小于则更新那个点的dist
然后将t加入到集合s，即st[t]=true

最后所生成的最小树，点就是集合s中的那些点
边，就是每个点的dist数组中所存的权值对应的边，如果对于一个点的dist的值有两条边，那么随意选一条即可

至于一个点到集合的距离，就是该点到集合中所有点的距离的最小值，如下图，实际上就是上面维护的dist数组，
在这里插入图片描述

例子+题解

在这里插入图片描述

在这里插入图片描述
对于数据，如果边的数量与点的平方的数量相当，那么就是稠密图

在这里插入图片描述
首先初始值都为无穷，之后由于都是无穷，所以随便拿一个，就拿一号点作为起点，
所以一号点是t，之后用该点去更新其他点的dist，
之后，从其他点的dist中，找到dist值最小的那个点，二号点，用该点去更新其他点，
对于三号点，旧值（到一号点的距离）是2，新值（到二号点的距离）是2，所以无需更新
对于四号点，从二号点无法到达四号点，所以无需更新
之后将二号点加入到s集合，也就是st[2]=true

之后再从其他点的dist中，找到值最小的那个点，三号点，…依次执行
在这里插入图片描述
数据分析：对于稠密图，使用邻接矩阵，即二维数组g[N][N]
宏定义INF为0x3f3f3f3f

在prim算法中
首先初始化为无穷
之后，根据题目，要有一个res来接收结果，初始化为0

然后有一个for循环，进行n次遍历
对于每次遍历，
首先初始化t为-1；
之后，遍历一号点到n号点，j从1到n
判断j点不在集合s，同时 t==-1 或者 dist[t]>dist[j]
（因为t==-1主要是为了应对初始状态都是正无穷时，将一号点当做起点；之后dist[t]>dist[j]是因为dist[t]是上一轮中的dist的最小值，如果找到dist[j]<dist[t]，那么j就是现在这轮中最小的，这里无需考虑初始时的特殊情况，只需要考虑一般情况，因为特殊情况有t==-1兜住）
如果判断成立，那么取出j给到t
之后，如果不是第一个点，同时dist的值为无穷，那么意味着存在一个点与树是不连通的，直接返回INF
之后，如果不是第一个点，将dist的值加入到res中，
（接下来就是在为下一次循环做数据准备了，上面在进行最小树构造，所以有关从最小树获取某些信息的操作，在这一步之前进行比较稳妥）
之后，用t来更新其他点到集合的距离，即对于j从1到n，dist[j]=min(disy[j],g[t][j]);
（直接拿着t到其他点的距离来更新）
最后将t加入到s中

函数最后返回res；
在这里插入图片描述

kruskal算法

思想

在这里插入图片描述
对于稀疏图寻找最小生成树，使用该算法
首先将所有的边按照权重从小到大进行排序，排序到一个结构体数组里
之后，枚举每条边ab，以及权重c
如果ab不连通，那么将ab加入到最小生成树集合中

例子+题解

在这里插入图片描述

在这里插入图片描述
这里定义一个结构体，Edge结构体，里面有元素a，b，w
重载运算符小于号<
方便结构体直接进行比较

二分图

染色法

思想

在这里插入图片描述
二分图：一个图中相连的两个点，分别在不同的集合中，如下图：

当图中不含奇数环的话，染色过程就没有矛盾，也就是相连的两个点所染得色不同，是相反的
在这里插入图片描述

数据分析，用邻接表来存，
N是点的数量，M是边的数量，因为邻接表中，边的权值存在数组里，且是无向图，所以，M要取真正边数的两倍

定义一个color数组，表示某个点被染成白还是黑
在这里插入图片描述
上图中，首先是一个add函数，仍然采用头插法
之后main函数里，先进行初始化，将h数组初始化为-1
之后，对于m个询问，分别输入点并调用add函数

然后定义一个fiag值，用来记录是否出现矛盾，初始化为true

之后遍历i从1到n
if i没被染色，
那么调用dfs并染成1：dfs（i，1）
同时再次判断：如果返回dfs结果是假，那么就表明出现了矛盾，flag更新为false

对于dfs：
在这里插入图片描述
首先第一行就是一个染色的功能
color[u]=c;
根据二分染色的规则，一个连通图中，一旦一个点被染色了，那么其他点的颜色都被定了
第一个for循环，是遍历u所有的出边e[i]号结点，也就是j号结点
如果j点没被染色，那么染成相反的颜色（用2表示，也就用3-c来实现），同时放入if函数进行判断，如果dfs返回了false，那么就是有冲突，那么就返回false
else，如果j点被染色，那么比较该点是否与传进来的c一样，如果一样，就矛盾，返回false