AI 助理
备案控制台
开发者社区 人工智能 文章 正文

一题带你写出图论算法模板！！！

2023-12-12 68
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 一题带你写出图论算法模板！！！

3.png这题是道基础的图论算法题目


注释很重要！！！！！！！


在做这道题之前，我们先了解一下基础的图论算法吧！！！

4.png5.png

1.floyd：

6.png7.png

这样可以求出所有点到任意一点的最短路径和距离

8.png

dijkstra：


最短路问题考察的是我们如何抽象成一个模型


图论的题侧重点在于抽象


难点在建图！！！！


2.朴素Dijstra算法


Dijkstra算法算是贪心思想实现的，首先把起点到所有点的距离存下来找个最短的，然后松弛一次再找出最短的，所谓的松弛操作就是，遍历一遍看通过刚刚找到的距离最短的点作为中转站会不会更近，如果更近了就更新距离，这样把所有的点找遍之后就存下了起点到其他所有点的最短距离

9.png10.png11.png

3.dijkstra算法（堆优化，c++直接用STL优先队列）


能使用的核心是堆中出来的点一定是最小的，且不会被更新的

12.png

4.spfa算法（没有负环就可以用）


可以用于适合dijkstra解决的问题

13.png

14.png

floyd方法:

class Solution {
public:
    int dist[1100][1100];
    void floyd(int n)
    {
        //floyd本质是试点探测法
        for(int k = 0;k < n;k++)
          for(int i = 0;i < n;i++)
           for(int j = 0;j < n;j++)
           {
               //试点探测
               dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j]);
           }
    }
    int ans[1110];
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) 
    {
       //这题一看求的就是多源最短路
       //计算出当前点到所有点的最短距离，小于distance距离的点加入到当前点的数组的中
       //多源最短路有floyd算法，最常用的算法
       //也可以用单源最短路算法spfa和dijkstra，bellmanford(一般不用，复杂度有点高)
       //1.dijkstra算出当前点到所有点的距离，小于distance距离的点加入到当前点的数组的中
       //再遍历下一个点，往返加入
       int m = edges.size();
       memset(dist,0x3f,sizeof(dist));//初始化为无穷，方便后续试点判断的时候，不把无穷的点加入
       //无向图
       for(int i = 0;i < m;i++)
       {
          int a = edges[i][0];
          int b = edges[i][1];
          int c = edges[i][2];
          dist[a][b] = c;
          dist[b][a] = c;
          dist[a][a] = 0;
          dist[b][b] = 0;
       }
       floyd(n);
       int min_val = 0x3f3f3f3f;
       for(int i = 0;i < n;i++)
       {
           cout<<i<<" ";
          for(int j = 0;j < n;j++)
          {
            if(j == i) continue;
            if(dist[i][j] <= distanceThreshold) ans[i]++;
          }
          min_val = min(ans[i],min_val);
          cout<<ans[i]<<endl;
       }
       int res = -0x3f3f3f3f;
       for(int i = 0;i < n;i++)
       {
           if(ans[i] == min_val && res < i) res = i;
       }
       return res;
    }
};

spfa方法：

class Solution {
public:
    int h[11100],w[11100],ne[11100],e[11100],idx = 0;
    int dist[11100];
    void add(int a,int b,int c)
    {
        e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++;
    }
    queue<int> q;
    int st[1100];
    void spfa(int start)
    {
         dist[start] = 0;
         q.push(start);//队列里放着要被更新的点，这个点要去松弛边
         st[start] = 1;
         while(!q.empty())
         { 
            auto t = q.front();
            q.pop();
            st[t] = 0;//该点出队更新其他点(松弛边)
            for(int i = h[t];i != -1;i = ne[i])
            {
               int b = e[i];
               int c = w[i];
               if(dist[b] > dist[t] + c)
               {
                   dist[b] = dist[t] + c;
                   if(!st[b]) 
                   {
                     q.push(b);//如果该点不在队列里面，并且连接该点的边又被更新，那么我们一定要加入到队列，再更新一次
                     st[b] = 1;
                   }
               }
            }
         }
         //题目没有负权边
    }
    int ans[1100];
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        memset(h,-1,sizeof(h));
        int m = edges.size();
        for(int i = 0;i < m;i++)
        {
           int a = edges[i][0];
           int b = edges[i][1];
           int c = edges[i][2];
           add(a,b,c);
           add(b,a,c);
        }
        int min_val = 0x3f3f3f3f;
        for(int i = 0;i < n;i++)
        {
           int start = i;
           memset(dist,0x3f,sizeof(dist));
           memset(st,0,sizeof(st));
           spfa(start);
           for(int j = 0;j < n;j++)
           {
              if(j == start) continue;
              if(dist[j] <= distanceThreshold) ans[start]++;
           }
           cout<<start<<" "<<ans[start]<<endl;
           min_val = min(ans[start],min_val);
        }
       cout<<min_val<<endl;
       int res = -0x3f3f3f3f;
       for(int i = 0;i < n;i++)
       {
           if(ans[i] == min_val && res < i) res = i;
       }
       return res;
    }
};

dijkstra方法：

class Solution {
public:
    int h[11100],w[11100],ne[11100],e[11100],idx = 0;
    int dist[11100];
    void add(int a,int b,int c)
    {
        e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++;
    }
    //st数组保存的是已经被拿来更新过的点
    //我们每次取的就是，从未被更新过的点集中选出一个离更新过的点的点集(距离点集中的源点最近)最近的点
    //更新过的点的点集我们记为V,未更新过的点的点集记为E
    int st[11000];
    void dijkstra(int start,int n)
    {
        dist[start] = 0;
        for(int i = 0;i < n;i++)
        {  
          int t = -1;
           for(int j = 0;j < n;j++)
           {
              if(!st[j] && (t == -1 || dist[t] > dist[j])) //要拿出的点必须是未更新过的点集中的点，
              //并且是离V的点集(距离点集中的源点)，也就是距离源点距离最短的点
              {
                t = j;
              }
           }
           st[t]  = 1;
              for(int i = h[t];i != -1;i = ne[i])//用t去更新邻边
              {
                 int b = e[i];
                 int c = w[i];
                 dist[b] = min(dist[b],dist[t] + c); 
              }
        }
    }
    int ans[1100];
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        memset(h,-1,sizeof(h));
        int m = edges.size();
        for(int i = 0;i < m;i++)
        {
           int a = edges[i][0];
           int b = edges[i][1];
           int c = edges[i][2];
           add(a,b,c);
           add(b,a,c);
        }
        int min_val = 0x3f3f3f3f;
        for(int i = 0;i < n;i++)
        {
           int start = i;
           memset(dist,0x3f,sizeof(dist));
           memset(st,0,sizeof(st));
           dijkstra(start,n);
           for(int j = 0;j < n;j++)
           {
              if(j == start) continue;
              if(dist[j] <= distanceThreshold) ans[start]++;
           }
           cout<<start<<" "<<ans[start]<<endl;
           min_val = min(ans[start],min_val);
        }
       cout<<min_val<<endl;
       int res = -0x3f3f3f3f;
       for(int i = 0;i < n;i++)
       {
           if(ans[i] == min_val && res < i) res = i;
       }
       return res;
    }
};

模板题：

15.png

#include <iostream>
//因为题目给出500个点，100000条边，说明是个稠密图
//所以我们用邻接矩阵去存储
//朴素dijkstra算法
//三步骤
//1.初始化dist[1] = 0，其余的为正无穷，可以用0x3f3f3f表示
//2for循环n次
//3.遍历dist数组，找到一个节点，找到一个距离最短的值，假设最短的值的节点为j
//每次从 「未求出最短路径的点」中 取出 距离距离起点 最小路径的点，并把这个最短路径的点标记
//4.遍历从i节点后继的所有节点，更新节点，例如i节点后面是j，如果dist[j] > dist[i] + w
//w：i到j的边的距离，那么就更新dist[j] = dist[i] + w;
//1 3 4，1 3 4，1 3 4，重复循环完，1步骤是遍历所有节点 
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 510;
int n,m;
int g[N][N],dist[N];//g是邻接矩阵，dist表示起点到当前节点的最短距离，下标就是顶点
//又因为这里我们是带权的，权不一样，所以g二维数组里面的元素表示的是从前一个顶点到这个
//点的边权（距离）,每行每列的下标都代表顶点，元素是边权，边权为0就是两顶点没边
bool st[N];//默认为false，找到这个点的最短路径的话，就标记下来，不用再找了
//算法模板中第一个节点实际上被再次遍历了同时初始化了下一层的所有节点距离
int dijkstra()
{
    dist[1] = 0;//源点的距离我们默认为1
    for(int i = 1;i <= n;i++)
    {
        int t = -1;//因为dijkstra算法不适用于负权边，所以我们用这个判断可以把第一个点
        //加入
        for(int j = 1;j <= n;j++)//遍历数组找到从当前顶点直达的最小的路径
        //为什么可以直接找到直达的，因为我们初始化时，不可达到的距离我们设为正无穷
        //所以说每次最多能达到初始化过dist的下标，没初始化过的其实就不会去执行t = j了
        {
            if(!st[j] && (t == -1 || dist[t] > dist[j]))//后面的或号我们叫短路操作
            //dist[t] > dist[j]确保了不是直接连通的顶点不会去执行这条语句
            {
                t = j;
            }
        }
        st[t] = true;
        //算法模板中第一个节点实际上被再次遍历了同时初始化了下一层的所有节点距离
        for(int j = 1;j <=n;j++)//用t去更新最短距离，枚举经过确定t顶点到直达的顶点的距离
        //并初始化
        //0x3f3f3f确保了不会执行不是直达的,不过我们还是要遍历n次，可能他由t出发的直达的
        //边有n条，因为稠密图是假设起点是st那么st的出边可能就有n条边，那么遍历完需要n个起点
        //稀疏图假设起点是st，出边最多可能有n条边，但是因为n和m相同，所以我们只是o(N)
        {
            dist[j] = min(dist[j],dist[t] + g[t][j]);
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    else return dist[n];
}
int main()
{
    memset(dist,0x3f,sizeof dist);
    memset(g,0x3f,sizeof g);
    cin>>n>>m;
    for(int i = 0;i < m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        g[a][b] = min(g[a][b],c);
    }
    printf("%d",dijkstra());
    return 0;
}

dijkstra(堆优化版)方法：

class Solution {
public:
    int h[11100],w[11100],ne[11100],e[11100],idx = 0;
    int dist[11100];
    void add(int a,int b,int c)
    {
        e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++;
    }
    //st数组保存的是已经被拿来更新过的点
    //我们每次取的就是，从未被更新过的点集中选出一个离更新过的点的点集(距离点集中的源点最近)最近的点
    //更新过的点的点集我们记为V,未更新过的点的点集记为E
    int st[11000];
    typedef pair<int,int> PII;
    priority_queue<PII,vector<PII>,greater<PII>> heap;
    void dijkstra_heap(int start,int n)
    {
        dist[start] = 0;
        heap.push({0,start});
        while(!heap.empty())
        {
            auto t = heap.top();//选出距离源点最小的点，按照dist(距离)排序
            int dist_u = t.first;
            int u = t.second;
            heap.pop();
            //如果该点是已经之前更新过的点(已经选中去松弛过的点)，那不能被松弛，跳过
            if(st[u]) continue;
            else st[u] = 1;
            for(int i = h[u];i != -1;i = ne[i])
            {
               int b = e[i];
               int c = w[i];
               if(dist[b] > dist[u] + w[i])
               {
                   //如果该点被更新了，那么要再加入更新一下
                   dist[b] = dist[u] +w[i];//因为该边被更新了，那么他的邻边也需要更新
                   heap.push({dist[b],b});
               }
            }
        }
    }
    int ans[1100];
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        memset(h,-1,sizeof(h));
        int m = edges.size();
        for(int i = 0;i < m;i++)
        {
           int a = edges[i][0];
           int b = edges[i][1];
           int c = edges[i][2];
           add(a,b,c);
           add(b,a,c);
        }
        int min_val = 0x3f3f3f3f;
        for(int i = 0;i < n;i++)
        {
           int start = i;
           memset(dist,0x3f,sizeof(dist));
           memset(st,0,sizeof(st));
           dijkstra_heap(start,n);
           for(int j = 0;j < n;j++)
           {
              if(j == start) continue;
              if(dist[j] <= distanceThreshold) ans[start]++;
           }
           min_val = min(ans[start],min_val);
        }
       cout<<min_val<<endl;
       int res = -0x3f3f3f3f;
       for(int i = 0;i < n;i++)
       {
           if(ans[i] == min_val && res < i) res = i;
       }
       return res;
    }
};

模板题：

16.png

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
typedef pair<int,int> pll;
const int N = 200010;
int h[N],e[N],ne[N],idx;
int n,m,w[N],dist[N];
bool st[N];
void add(int a,int b,int c)
{
    e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;
}
int dijkstra_2()
{
    dist[1] = 0;//初始话为0
    priority_queue<pll,vector<pll>,greater<pll>> heap;
    //加入第一个
    heap.push({0,1});//左边是顶点，右边是起点到当前顶点的距离
    while(!heap.empty())
    {
        auto t =heap.top();//大根堆，拿出最小的
        heap.pop();
        int k = t.second,dis = t.first;//k代表当前顶点
        if(st[k]) continue;//如果枚举过了就不用在枚举了
            st[k] = true;//
        for(int i = h[k];i != - 1;i = ne[i])//枚举当前最短距离的顶点，找到最小的边，加入
        {
            int j = e[i];//找到当前顶点直达的顶点
            if(dist[j] > dist[k] + w[i])//初始化当前最短的顶点直达的边的距离
            {
                dist[j] = dist[k] + w[i];
                heap.push({dist[j],j});//把顶点和距离加入，优先队列会维护这个队列的
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) return 0;
    else return dist[n];
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    memset(dist,0x3f,sizeof dist);
    for(int i = 0;i < m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    if(dijkstra_2() == 0) printf("-1\n");
    else printf("%d",dijkstra_2());
    return 0;
}


文章标签：
算法
C++
关键词：
图论算法
算法模板
图论算法模板
乖的小肥羊
目录
相关文章
闻缺陷则喜何志丹
|
7月前
|
机器学习/深度学习 安全 算法
【图论】【割点】【C++算法】928. 尽量减少恶意软件的传播 II
【图论】【割点】【C++算法】928. 尽量减少恶意软件的传播 II
闻缺陷则喜何志丹
67 0
闻缺陷则喜何志丹
|
7月前
|
算法 测试技术 C++
【动态规划】【图论】【C++算法】1928规定时间内到达终点的最小花费
【动态规划】【图论】【C++算法】1928规定时间内到达终点的最小花费
闻缺陷则喜何志丹
98 2
睡觉待开机
|
4月前
|
算法
【算法】前缀和——二维前缀和模板题
【算法】前缀和——二维前缀和模板题
睡觉待开机
39 0
路人与大师
|
1月前
|
JSON 算法 数据挖掘
基于图论算法有向图PageRank与无向图Louvain算法构建指令的方式方法 用于支撑qwen agent中的统计相关组件
利用图序列进行数据解读，主要包括节点序列分析、边序列分析以及结合节点和边序列的综合分析。节点序列分析涉及节点度分析（如入度、出度、度中心性）、节点属性分析（如品牌、价格等属性的分布与聚类）、节点标签分析（如不同标签的分布及标签间的关联）。边序列分析则关注边的权重分析（如关联强度）、边的类型分析（如管理、协作等关系）及路径分析（如最短路径计算）。结合节点和边序列的分析，如子图挖掘和图的动态分析，可以帮助深入理解图的结构和功能。例如，通过子图挖掘可以发现具有特定结构的子图，而图的动态分析则能揭示图随时间的变化趋势。这些分析方法结合使用，能够从多个角度全面解读图谱数据，为决策提供有力支持。
路人与大师
95 0
多多!
|
6月前
|
算法 Java 数据处理
Java算法模板 数据流快读
Java算法模板 数据流快读
多多!
52 2
朝阳39
|
5月前
|
设计模式 JavaScript 算法
vue2 原理【详解】MVVM、响应式、模板编译、虚拟节点 vDom、diff 算法
vue2 原理【详解】MVVM、响应式、模板编译、虚拟节点 vDom、diff 算法
朝阳39
197 0
多多!
|
6月前
|
算法 前端开发 安全
C++算法模板
C++算法模板
多多!
36 0
算精通
|
7月前
|
算法 Python
Python中实现图论算法
Python中实现图论算法 “【5月更文挑战第20天】”
算精通
54 3
数据分析螺丝钉
|
6月前
|
算法 数据挖掘 定位技术
算法必备数学基础：图论方法由浅入深实践与应用
算法必备数学基础：图论方法由浅入深实践与应用
数据分析螺丝钉
113 0
碳基肥宅
|
7月前
|
算法
简记二分算法模板与代码案例：整数二分和浮点数二分
本文介绍了两种算法模板，分别是整数二分和浮点数二分。
碳基肥宅
57 0

热门文章

最新文章

  • 1
    机器学习-特征选择：如何使用递归特征消除算法自动筛选出最优特征？
  • 2
    领域最全 | 计算机视觉算法在路面坑洼检测中的应用综述(基于2D图像/3D LiDAR/深度学习)（上）
  • 3
    【WSN定位】基于chan算法实现多基站目标定位附Matlab代码
  • 4
    openssl中算法的组织方式
  • 5
    OpenCV 1 图像分割--分水岭算法代码
  • 6
    Linux内核中的有关Page的算法
  • 7
    缓存、缓存算法(转)
  • 8
    算法笔记之回溯法（2）
  • 9
    图解算法：摘取位运算的王冠「八皇后问题」！| 算法必看系列十七
  • 10
    Console-算法[for]-输出等腰三角形
  • 1
    【Paddle】PCA线性代数基础 + 领域应用：人脸识别算法（1.1w字超详细：附公式、代码）
    119
  • 2
    BASE64的算法说明
    69
  • 3
    算法人生（1）：从“强化学习”看如何“战胜拖延”
    115
  • 4
    理解并应用机器学习算法：决策树
    145
  • 5
    【机器学习】在使用K-means聚类算法时，如何选择K的值？
    425
  • 6
    【机器学习】为什么K-means算法使用欧式距离度量？
    413
  • 7
    【机器学习】描述K-means算法的步骤
    153
  • 8
    【机器学习】K-means和KNN算法有什么区别？
    652
  • 9
    C语言易混淆、简单算法、结构体题目练习、常见关键字总结-2
    58
  • 10
    C语言易混淆、简单算法、结构体题目练习、常见关键字总结-1
    61

    • 相关课程

    更多
  • 智能运维赛（复赛）：利用数据和算法，快速定位系统异常并进行根因分析
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台

    • 相关实验场景

    更多
  • 使用Swing算法实现商品推荐
  • RSA密码算法设计与实现
  • RSA非对称加密算法
  • 欧拉图的构造性证明与算法实现
  • 推荐系统入门之使用ALS算法实现打分预测
    • 下一篇
    DataWorks售前咨询