图论0

0.1. 岛屿

0.2. 图查找算法

0.2.1. 并查集的实现 并查集理论基础 | 代码随想录

1. 并查集，是将一个集合内所有数据放入一个连通图中，即为father[u]= v；
2. 查询一个并查集，是查询根节点是否相同，find(u)== find(v)
3. 初始化，所有的并查集都指向自身
4. 路径压缩，节点在find过程中都执行根节点

// 使用数据存放并查集

vector<int> father(n, 0);
void init(){
    for(int i = 0;i< father.size();i++){
        father[i]= i;
    }
}

int find(int u){
    if(father[u]==u) return u;
    else {
        father[u]=find(father[u]);// 路径压缩，指向根节点
    }
    return father[u];
}

int is_same(int u, int v){
    int a = find(u);
    int b = find(v);
    if(a == b) return 1;
    else return 0;
}

void join(int u, int v){
    int a = find(u);
    int b = find(v);
    if(a == b) return ;
    father[u]= v;
    return ;
}

0.2.2. prim算法

1. 选择最小边e,v（e是树中，v是树外的数据）
2. 将节点v加入树中
3. 更新与v的节点的权重
   1. 此处记录树的连接关系，记录当前节点的父亲

0.2.3. kruskal 算法

1. 完成并查集
2. 对边的权重排序
3. 选择最小边
   1. 如果在并查集中，跳过
   2. 不在并查集中，加入节点树种

0.2.4. 拓扑排序

1. 计算节点入度
2. 选择入度为0 的节点，加入处理队列q, 并将入度替换为-1
3. 处理队列q
   1. cur指向的所有节点，入度减1
   2. 如果入度等于1，加入处理队列q, 并将入度替换为-1
   3. 记录出队元素cur.

出队元素不等于总元素数量时， 判断有向图中 存在环

0.2.5. dijkstra算法

权值不能为负数，prim算法权值可以是负数，负数情况使用ford算法

1. 选择最小边并且该节点没有被访问过
2. 标记该节点，已经被访问过
3. 更新非访问节点到源点的最小距离，同时当前节点的父亲

0.2.6. 使用边权重的dijkstra算法

使用边的权值进行计算

1. 建立小顶堆
2. 从小顶堆中选择最小的边
3. 标记边连线的点已经被访问过了
4. 更新edge相连的顶点的权重

0.3. 附录

0.3.1. 建立小顶堆

#include <queue>
class mycomparison{
    bool operator(const pair<int, int>& a, const pair<int, int>& b){
        return a.second> b.second;
    }
}
priority_queue<pair<int, int>, vector<pair<int,int>> , mycomparison> p;
/*
    a> b时 ，是小顶堆；
    a< b时， 是大顶堆；
*/

0.3.2. 对vector数组进行排序

#include <algorithm>
vector<int> edges;
sort(edges.begin() , edges.end(), [](const edge& a, const edge& b){
    return a< b;
});
/*
    a< b， 升序排序；
    a> b， 降序排序；
    默认情况是升序排序；
*/