代码随想录Day17 图论-3

🕗 发布于 2024-09-29 10:37 图论算法 c++ 数据结构

并查集理论基础

学习并查集我们就要知道并查集可以解决什么问题

并查集主要有两个功能：

将两个元素添加到一个集合中
判断两个元素在不在同一个集合

以下是代码模板

int n = 1005; // n根据题目中节点数量而定，一般比节点数量大一点就好
vector<int> father = vector<int> (n, 0); // C++里的一种数组结构

// 并查集初始化
void init() {
    for (int i = 0; i < n; ++i) {
        father[i] = i;
    }
}
// 并查集里寻根的过程
int find(int u) {
    return u == father[u] ? u : father[u] = find(father[u]); // 路径压缩
}

// 判断 u 和 v是否找到同一个根
bool isSame(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}

// 将v->u 这条边加入并查集
void join(int u, int v) {
    u = find(u); // 寻找u的根
    v = find(v); // 寻找v的根
    if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
    father[v] = u;
}

在并查集中find是寻找根的操作

如下图第二步 8的根是1 3的根就是3 所以加入之后由1指向3

107. 寻找存在的路径

本题就是判断是否存在路径由source到destinaion 在无向图当中我们只要判断这两个节点在一个集合里面就说明他们是可以相互到达的所以我们就可以用到并查集的知识

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<int> father = vector<int>(101,0);

void init(){
    for(int i=1;i<=n;i++){
        father[i]=i;
    }
}

int find(int u){
    return u==father[u] ? u : father[u]=find(father[u]);
}

bool isSame(int u,int v){
    u=find(u);
    v=find(v);
    return u==v;
}

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

int main(){
    int M,s,t,a,b;
    cin>>n>>M;
    init();
    while(M--){
        cin>>s>>t;
        join(s,t);
    }
    cin>>a>>b;
    if(isSame(a,b)) cout<<1<<endl;
    else cout<<0<<endl;
}

108. 冗余连接

这一题就是给你一棵树然后让你删掉一条边使其变成合法的树要求如果有多个答案需要我们输出最后出现的那条边

如果要加入树的两个节点已经在一个集合里面了然后再相连的话就会产生环所以我们可以从头遍历然后只要这两个节点不在同一个集合我们就让他们加入否则就可以直接打印答案

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<int> father = vector<int> (1005,0);

void init(){
    for(int i=0;i<=n;i++){
        father[i]=i;
    }
}

int find(int u){
    return u==father[u] ? u : father[u]=find(father[u]);
}

bool isSame(int u,int v){
    u=find(u);
    v=find(v);
    return u==v;
}

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

int main(){
    int s,t;
    cin>>n;
    init();
    for(int i=0;i<n;i++){
        cin>>s>>t;
        if(isSame(s,t)){
            cout<<s<<" "<<t<<endl;
            return 0;
        }else{
            join(s,t);
        }
    }
}

109. 冗余连接II

这一题变成了有向图

我们要想到有向树的性质有向树是只有根节点的入度为0 其他节点的入度都是1 然后我们删除的边肯定是造成节点入度为2的如果没有入度为2的节点那肯定就是有环我们只需要删除环的一个边可以了

处理入度为2的节点的情况是分两个边来出来主要逻辑是遍历的时候如果遍历到了要删除的节点就不做任何处理然后如果最后没有形成环说明删除该边是对的反之就删除另一个边

处理有环的情况就是一旦加入树后就形成了环那么加入的一条边就是我们要删除的那个边

#include <iostream>
#include <vector>
using namespace std;
int n;
vector<int> father (1001, 0);
// 并查集初始化
void init() {
    for (int i = 1; i <= n; ++i) {
        father[i] = i;
    }
}
// 并查集里寻根的过程
int find(int u) {
    return u == father[u] ? u : father[u] = find(father[u]);
}
// 将v->u 这条边加入并查集
void join(int u, int v) {
    u = find(u);
    v = find(v);
    if (u == v) return ;
    father[v] = u;
}
// 判断 u 和 v是否找到同一个根
bool same(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}

// 在有向图里找到删除的那条边，使其变成树
void getRemoveEdge(const vector<vector<int>>& edges) {
    init(); // 初始化并查集
    for (int i = 0; i < n; i++) { // 遍历所有的边
        if (same(edges[i][0], edges[i][1])) { // 构成有向环了，就是要删除的边
            cout << edges[i][0] << " " << edges[i][1];
            return;
        } else {
            join(edges[i][0], edges[i][1]);
        }
    }
}

// 删一条边之后判断是不是树
bool isTreeAfterRemoveEdge(const vector<vector<int>>& edges, int deleteEdge) {
    init(); // 初始化并查集
    for (int i = 0; i < n; i++) {
        if (i == deleteEdge) continue;
        if (same(edges[i][0], edges[i][1])) { // 构成有向环了，一定不是树
            return false;
        }
        join(edges[i][0], edges[i][1]);
    }
    return true;
}

int main() {
    int s, t;
    vector<vector<int>> edges;
    cin >> n;
    vector<int> inDegree(n + 1, 0); // 记录节点入度
    for (int i = 0; i < n; i++) {
        cin >> s >> t;
        inDegree[t]++;
        edges.push_back({s, t});
    }

    vector<int> vec; // 记录入度为2的边（如果有的话就两条边）
    // 找入度为2的节点所对应的边，注意要倒序，因为优先删除最后出现的一条边
    for (int i = n - 1; i >= 0; i--) {
        if (inDegree[edges[i][1]] == 2) {
            vec.push_back(i);
        }
    }
    // 情况一、情况二
    if (vec.size() > 0) {
        // 放在vec里的边已经按照倒叙放的，所以这里就优先删vec[0]这条边
        if (isTreeAfterRemoveEdge(edges, vec[0])) {
            cout << edges[vec[0]][0] << " " << edges[vec[0]][1];
        } else {
            cout << edges[vec[1]][0] << " " << edges[vec[1]][1];
        }
        return 0;
    }

    // 处理情况三
    // 明确没有入度为2的情况，那么一定有有向环，找到构成环的边返回就可以了
    getRemoveEdge(edges);
}

prim算法

题意很简单就是要我们求一个最小路径联通所有节点

prim算法有三部曲

1.我们要找到距离最小生成树最近的那个节点

2.将该节点加入到最小生成树种

3.更新minDest数组

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main(){
    int v,e;
    int s,t,k;
    cin>>v>>e;
    vector<vector<int>> grid(v+1,vector<int>(v+1,10001));
    while(e--){
        cin>>s>>t>>k;
        grid[s][t]=k;
        grid[t][s]=k;
    }
    //所有节点距离最小生成树的距离
    vector<int> minDist(v+1,10001);
    vector<bool> isIntree(v+1,false);
    for(int i=1;i<v;i++){
        //prim三部曲 第一步 选取距离最小生成树最近的节点
        int cur=-1;
        int minVal=INT_MAX; //记录最小的距离
        for(int j=1;j<=v;j++){
            if(!isIntree[j] && minVal>minDist[j]){
                minVal=minDist[j];
                cur=j;
            }
        }
        
        //prim三部曲 第二步 将最近的节点加入生成树
        isIntree[cur]=true;
        
        //prim三部曲 第三步 更新minDist数组
        for(int j=1;j<=v;j++){
            if(!isIntree[j] && minDist[j]>grid[cur][j]){
                minDist[j]=grid[cur][j];
            }
        }
    }
    int ans=0;
    for(int i=2;i<=v;i++){
        ans+=minDist[i];
    }
    cout<<ans<<endl;
}

kruskal算法

kruskal算法也可以解决上一道题不过该算法是处理边的 prim算法是处理点的

kruskal算法的思路是我们先把所有边的权值从小到大排序然后从头开始遍历边利用并查集我们要判断边的两个节点是不是在一个集合找出两个节点的祖先如果不在同一个集合就可以作为最小生成树的边然后加入到同一个集合

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// l,r为 边两边的节点，val为边的数值
struct Edge {
    int l, r, val;
};

// 节点数量
int n = 10001;
// 并查集标记节点关系的数组
vector<int> father(n, -1); // 节点编号是从1开始的，n要大一些

// 并查集初始化
void init() {
    for (int i = 0; i < n; ++i) {
        father[i] = i;
    }
}

// 并查集的查找操作
int find(int u) {
    return u == father[u] ? u : father[u] = find(father[u]); // 路径压缩
}

// 并查集的加入集合
void join(int u, int v) {
    u = find(u); // 寻找u的根
    v = find(v); // 寻找v的根
    if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
    father[v] = u;
}

int main() {

    int v, e;
    int v1, v2, val;
    vector<Edge> edges;
    int result_val = 0;
    cin >> v >> e;
    while (e--) {
        cin >> v1 >> v2 >> val;
        edges.push_back({v1, v2, val});
    }

    // 执行Kruskal算法
    // 按边的权值对边进行从小到大排序
    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
            return a.val < b.val;
    });

    // 并查集初始化
    init();

    // 从头开始遍历边
    for (Edge edge : edges) {
        // 并查集，搜出两个节点的祖先
        int x = find(edge.l);
        int y = find(edge.r);

        // 如果祖先不同，则不在同一个集合
        if (x != y) {
            result_val += edge.val; // 这条边可以作为生成树的边
            join(x, y); // 两个节点加入到同一个集合
        }
    }
    cout << result_val << endl;
    return 0;
}

拓扑排序

拓扑排序就是打个比方大学排课，例如先上A课，才能上B课，上了B课才能上C课，上了A课才能上D课，等等一系列这样的依赖顺序。问给规划出一条完整的上课顺序。

概括来说给出一个有向图然后让我们把这个有向图转成线性排序就是拓扑排序它也可以用来判断一个有向图是否有环

如下图我们自己模拟肯定是把0放入结果集然后1和2都可以放入结果集我们可以发现放入结果集的都是没有依赖的也就是说它的入度是为0的

我们就可以利用邻接表将0放入结果集之后遍历邻接表0 把后面所连接的元素的入度要减1 然后减1过后入度为0 就让它入队

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
using namespace std;

int main(){
    int n,m;
    cin>>n>>m;
    int s,t;
    vector<int> inDegree(n,0);
    unordered_map<int, vector<int>> umap; 
    vector<int> ans;
    while(m--){
        cin>>s>>t;
        umap[s].push_back(t);
        inDegree[t]++;
    }
    queue<int> que;
    for(int i=0;i<n;i++){
        if(inDegree[i]==0){
            que.push(i);
        }
    }
    
    while(que.size()){
        int cur=que.front();
        que.pop();
        ans.push_back(cur);
        vector<int> file=umap[cur];
        if(file.size()){
            for(int i=0;i<file.size();i++){
                inDegree[file[i]]--;
                if(inDegree[file[i]]==0){
                    que.push(file[i]);
                }
            }
        }
    }
    if (ans.size() == n) {
        for (int i = 0; i < n - 1; i++) cout << ans[i] << " ";
        cout << ans[n - 1];
    } else cout << -1 << endl;
}

dijkstra（朴素版）

该题求小明从起点到终点所花费的最小时间 dijksta算法和prim算法思路很像也有三部曲

1.找到距离源点最近的节点（注意不是最小生成树）

2.把该节点标记为访问过

3.更新minDest数组

#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
    int n, m, p1, p2, val;
    cin >> n >> m;

    vector<vector<int>> grid(n + 1, vector<int>(n + 1, INT_MAX));
    for(int i = 0; i < m; i++){
        cin >> p1 >> p2 >> val;
        grid[p1][p2] = val;
    }

    int start = 1;
    int end = n;

    // 存储从源点到每个节点的最短距离
    std::vector<int> minDist(n + 1, INT_MAX);

    // 记录顶点是否被访问过
    std::vector<bool> visited(n + 1, false);

    minDist[start] = 0;  // 起始点到自身的距离为0

    for (int i = 1; i <= n; i++) { // 遍历所有节点

        int minVal = INT_MAX;
        int cur = 1;

        // 1、选距离源点最近且未访问过的节点
        for (int v = 1; v <= n; ++v) {
            if (!visited[v] && minDist[v] < minVal) {
                minVal = minDist[v];
                cur = v;
            }
        }

        visited[cur] = true;  // 2、标记该节点已被访问

        // 3、第三步，更新非访问节点到源点的距离（即更新minDist数组）
        for (int v = 1; v <= n; v++) {
            if (!visited[v] && grid[cur][v] != INT_MAX && minDist[cur] + grid[cur][v] < minDist[v]) {
                minDist[v] = minDist[cur] + grid[cur][v];
            }
        }

    }

    if (minDist[end] == INT_MAX) cout << -1 << endl; // 不能到达终点
    else cout << minDist[end] << endl; // 到达终点最短路径

}

类比一下prim算法

prim 更新 minDist数组的写法：

for (int j = 1; j <= v; j++) {
    if (!isInTree[j] && grid[cur][j] < minDist[j]) {
        minDist[j] = grid[cur][j];
    }
}

dijkstra 更新 minDist数组的写法：

dijkstra是前一个节点的minDest加上到该节点的权值要小于该节点原本的minDest数组

for (int v = 1; v <= n; v++) {
    if (!visited[v] && grid[cur][v] != INT_MAX && minDist[cur] + grid[cur][v] < minDist[v]) {
        minDist[v] = minDist[cur] + grid[cur][v];
    }
}

以上代码都是我们从节点的角度去考虑的所以需要我们有两层for循环

dijkstra堆优化版

我们可以用小顶堆来让边权值最小的永远在堆顶

dijkstra三部曲依然不变我们取距离源点最近的点就是堆顶权值最小的边然后标记该点访问过

我们只需要在第三步用到一个for循环来更新一下minDest数组然后因为cur节点的加入要让新链接上的边加入队列

#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <climits>
using namespace std;

class mycomparsion{
public:
    bool operator()(const pair<int,int>& lrs, const pair<int,int>& rhs){
        return lrs.second>rhs.second;
    }
};

struct Edge{
  int to;
  int val;
  Edge(int t,int w):to(t),val(w){}
};

int main(){
    int n,m;
    cin>>n>>m;
    int s,e,v;
    vector<list<Edge>> grid(n+1);
    for(int i=0;i<m;i++){
        cin>>s>>e>>v;
        grid[s].push_back(Edge(e,v));
    }
    int start=1,end=n;
    vector<int> minDest(n+1,INT_MAX);
    vector<bool> visited(n+1,false);
    priority_queue<pair<int,int>, vector<pair<int,int>>, mycomparsion> pq;
    pq.push(pair<int, int>(start,0));
    minDest[start]=0;
    
    while(!pq.empty()){
        pair<int,int> cur=pq.top();
        pq.pop();
        if(visited[cur.first]) continue;
        visited[cur.first]=true;
        for(Edge edge:grid[cur.first]){
            if(!visited[edge.to] && minDest[cur.first]+edge.val<minDest[edge.to]){
                minDest[edge.to]=minDest[cur.first]+edge.val;
                pq.push(pair<int,int>(edge.to,minDest[edge.to]));
            }
        }
    }
    if (minDest[end] == INT_MAX) cout << -1 << endl; // 不能到达终点
    else cout << minDest[end] << endl; // 到达终点最短路径
}

原文地址：https://blog.csdn.net/m0_73740071/article/details/142620812

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

MySQL数据库基础
在过去的mysql中主要是使用的utf8mb3，但是mysql显示的就是utf8，中mysql8中区分显示了。类似于不同的编译器，虽然C/C++的代码是一样的，但是预处理、编译、汇编、链接这些过程却不
阅读更多2024-09-30
Percona Monitoring and Management
Percona Monitoring and Management (PMM)是一款开源的专用于管理和监控MySQL、MongoDB、PostgreSQL。
阅读更多2024-09-30
鸿蒙开发（NEXT/API 12）【已连接穿戴设备查询】手机侧应用开发
Wear Engine提供查询用户已连接的穿戴设备列表（即支持Wear Engine能力且与手机侧运动健康App处于连接状态的穿戴设备）的接口。
阅读更多2024-09-30
Redis数据库
本篇文章介绍了redis的相关知识，并使用springboot集成redis，实现缓存和分布式锁，后续会对文章勘误及更新~~
阅读更多2024-09-30
旧版的存档
【代码】旧版的存档。
阅读更多2024-09-30
Spring Boot 封装统一返回结果及全局异常处理
为了更细致地控制异常处理，我们可以定义一些自定义异常。然后，在全局异常处理器中添加对自定义异常的处理。通过封装统一的返回结果和全局异常处理，我们可以让Spring Boot应用更加健壮和易于维护。这种
阅读更多2024-09-30
【C++】IO流
C++IO流，包含输入输出流、文件流、字符流
阅读更多2024-09-30
低至1元/小时：国庆七天，30元通关《黑神话：悟空》！
随着《黑神话：悟空》自8月20日全球同步上线，正式登陆PC、PS5平台以来，以其精湛的画面和流畅的战斗体验，在发售三天后，该作的全平台销量超过1000万套，打破中国游戏历史记录，被媒体称为“中国首款3
阅读更多2024-09-30
阿里巴巴国际站获取商品详情item_get接口技术分享
item_get API接口是阿里巴巴开放平台提供的一个重要接口，它允许商家通过API调用，获取阿里巴巴平台上的商品详细信息。这些信息包括商品标题、价格、库存、属性、描述等，为商家提供了全面、准确的商
阅读更多2024-09-30
软件测试谣言二三事，认真你就输了
软件测试的职业寿命，取决于互联网行业能存活多久，至少目前看来，这个职业没有消失的风险，至于你能在这个职业待多久，那取决于你自己的能力，我见过不少超过35岁的老员工还在测试的职位上兢兢业业。以广州为例，
阅读更多2024-09-30