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

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

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

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

 

1.floyd：

 

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

dijkstra：

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

图论的题侧重点在于抽象

难点在建图！！！！

2.朴素Dijstra算法

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

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

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

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

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

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;
    }
};

模板题：

#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;
    }
};

模板题：

#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;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/150106.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

闲聊从零开发一个2D数字人流程实战

闲聊从零开发一个2D数字人流程实战

.2D数字人技术 百度&#xff0c;腾讯&#xff0c;等大厂都有自己的数字平台制作&#xff08;套壳&#xff1a;api后台转发vue前端&#xff09;&#xff0c;国外也有出名的heygen&#xff08;非常厉害一个&#xff09;通过开源项目组合实现&#xff0c;再打通每个项目已api的形…
阅读更多...
LCD1602命令代码整合

LCD1602命令代码整合

本文为博主 日月同辉&#xff0c;与我共生&#xff0c;csdn原创首发。希望看完后能对你有所帮助&#xff0c;不足之处请指正&#xff01;一起交流学习&#xff0c;共同进步&#xff01; > 发布人&#xff1a;日月同辉,与我共生_单片机-CSDN博客 > 欢迎你为独创博主日月同…
阅读更多...
C语言查看main函数的参数

C语言查看main函数的参数

这里写自定义目录标题 argc 代表参数的个数argv 代表参数的具体值&#xff0c;其中argv[0]代表的是可执行文件的名字&#xff0c;参考上图
阅读更多...
微信这4个功能容易暴露隐私，记得关闭

微信这4个功能容易暴露隐私，记得关闭

每天高频使用微信的我们&#xff0c;常常觉得安全无忧&#xff0c;然而这样的想法并不准确。尽管微信本身的安全性能极高&#xff0c;但若我们不主动设置相关功能&#xff0c;个人隐私和位置信息仍可能被暴露。 在微信朋友圈上&#xff0c;有些人喜欢分享生活的点滴&#xff0c…
阅读更多...
爆款标题怎么出来的？媒介盒子揭秘产出技巧

爆款标题怎么出来的？媒介盒子揭秘产出技巧

用户点开一篇文案的主要因素取决于标题是否具有吸引力&#xff0c;直观判断可能只需要半秒钟&#xff0c;用户的操作也决定了文章的点击率与阅读完成率。 然而有许多人为了取标题想破脑袋也想不出来&#xff0c;甚至文案内容出来了标题还没出来&#xff0c;今天媒介盒子就来为…
阅读更多...
Java GUI小程序之图片浏览器

Java GUI小程序之图片浏览器

以下是一个简单的图片浏览器示例代码&#xff0c;它包含了图片放大缩小、拖拽、上一张/下一张查看等功能。你可以根据它进行扩展&#xff0c;提高用户体验。 import java.awt.BorderLayout; import java.awt.Dimension; import java.awt.event.ActionEvent; import java.awt.e…
阅读更多...
土木非科班转码测开，斩获10家大厂offer

土木非科班转码测开，斩获10家大厂offer

大家好&#xff0c;我是洋子 24届秋招基本已经落下了帷幕&#xff0c;各大互联网大厂基本也开奖完毕&#xff0c;还没有拿到满意offer的同学也不要灰心&#xff0c;积极备战明年的春招。另外&#xff0c;25届想要找暑期实习的同学也可以开始准备起来了&#xff0c;基本大厂在春…
阅读更多...
UI自动化测试(弹出框，多窗口)

UI自动化测试(弹出框，多窗口)

一、弹出框实战 1、在UI自动化测试中经常会遇到Alert弹出框的场景。Alert类是对话框的处理&#xff0c;主要是对alert警告框。confirm确认框&#xff0c;promp消息对话框。 text():获取alert的文本 dismiss ():点击取消 accept():接受 send-keys():输入 from selenium import …
阅读更多...
split loop

split loop

// refactoringmotherfucker.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。 //#include <iostream> #include <vector> #include <memory>// before refactoring of split loop class People { public:People(double _age,double _…
阅读更多...
＜C++＞ 优先级队列

＜C++＞ 优先级队列

目录 前言 一、priority_queue的使用 1. 成员函数 2. 例题 二、仿函数 三、模拟实现 1. 迭代器区间构造函数 && AdjustDown 2. pop 3. push && AdjustUp 4. top 5. size 6. empty 四、完整实现 总结 前言 优先级队列以及前面的双端队列基本上已经脱离了队列定…
阅读更多...
单pipeline部署一套代码，多项目

单pipeline部署一套代码，多项目

单pipeline部署一套代码&#xff0c;多项目 pipeline {agent anyparameters {gitParameter(name: BRANCH_TAG, type: PT_BRANCH_TAG, branchFilter: origin/(.*), defaultValue: main, selectedValue: DEFAULT, sortMode: DESCENDING_SMART, description: 请选择需要部署的代码…
阅读更多...
【Regulatory Genomics】Part2 BPNet、DeepLIFT

【Regulatory Genomics】Part2 BPNet、DeepLIFT

文章目录 Deep learning at base-resolution reveals cis-regulatory motif syntaxproblemBPNet: predicting base-resolution profiles from DNA sequenceInterpreting the predictions of BPNet1 DeepLIFT2 TF-MoDISCO3 motif syntax derived TF cooperativity Experimental …
阅读更多...
人工智能基础_机器学习036_多项式回归升维实战3_使用线性回归模型_对天猫双十一销量数据进行预测_拟合---人工智能工作笔记0076

人工智能基础_机器学习036_多项式回归升维实战3_使用线性回归模型_对天猫双十一销量数据进行预测_拟合---人工智能工作笔记0076

首先我们拿到双十一从2009年到2018年的数据 可以看到上面是代码,我们自己去写一下 首先导包,和准备数据 from sklearn.linear_model import SGDRegressor import numpy as np import matplotlib.pyplot as plt X=np.arange(2009.2020)#左闭右开，2009到2019 获取从2009到202…
阅读更多...
Python如何使用Pyecharts+TextRank生成词云图？

Python如何使用Pyecharts+TextRank生成词云图？

Python如何使用PyechartsTextRank生成词云图&#xff1f; 1 应用场景2 关于Pyecharts2.1 Pyecharts简介2.2 Pyecharts安装2.3 Pyecharts支持的图形2.4 Pyecharts的一个示例 3 关于TextRank3.1 TextRank简介3.2 TextRank安装 4 词云图的生成过程4.1 导入需要的包4.2 目标文件4.3…
阅读更多...
使用c++程序，实现图像平移变换，图像缩放、图像裁剪、图像对角线镜像以及图像的旋转

使用c++程序，实现图像平移变换，图像缩放、图像裁剪、图像对角线镜像以及图像的旋转

数字图像处理–实验三A图像的基本变换 实验内容 A实验&#xff1a; &#xff08;1&#xff09;使用VC设计程序&#xff1a;实现图像平移变换&#xff0c;图像缩放、图像裁剪、图像对角线镜像。 &#xff08;2&#xff09;使用VC设计程序&#xff1a;对一幅高度与宽度均相等的…
阅读更多...
计算机网络五层协议的体系结构

计算机网络五层协议的体系结构

计算机网络中两个端系统之间的通信太复杂&#xff0c;因此把需要问题分而治之&#xff0c;通过把一次通信过程中涉及的所有问题分层归类来进行研究和处理 体系结构是抽象的&#xff0c;实现是真正在运行的软件和硬件 1.实体、协议、服务和服务访问点 协议必须把所有不利条件和…
阅读更多...
Java GUI实现五子棋游戏

Java GUI实现五子棋游戏

五子棋是一种双人对弈的棋类游戏&#xff0c;通常在棋盘上进行。棋盘为 1515 的方格&#xff0c;黑白双方各执棋子&#xff0c;轮流在棋盘的格点上落子&#xff0c;先在横、竖、斜线上形成五个相连的同色棋子者获胜。五子棋规则简单&#xff0c;易学难精&#xff0c;兼具攻防和…
阅读更多...
java，springboot钉钉开发连接器，自定义连接器配合流程使用，流程加入连接器，连接器发送参数，然后你本地处理修改值，返回给流程

java，springboot钉钉开发连接器，自定义连接器配合流程使用，流程加入连接器，连接器发送参数，然后你本地处理修改值，返回给流程

1.绘制连接器&#xff0c;注意出餐入参的格式&#xff0c; 2.绘制流程&#xff0c;绑定连接器&#xff0c;是提交后出发还是表单值变化后 3.编写本地接口&#xff08;内网穿透&#xff09;&#xff0c;绑定连接器 钉钉开发连接器&#xff0c;自定义连接器配合流程使用&#x…
阅读更多...
安防监控系统EasyCVR平台调用hls地址生成流的时间过长，该如何解决？

安防监控系统EasyCVR平台调用hls地址生成流的时间过长，该如何解决？

安防视频监控/视频集中存储/云存储/磁盘阵列EasyCVR平台可拓展性强、视频能力灵活、部署轻快&#xff0c;可支持的主流标准协议有国标GB28181、RTSP/Onvif、RTMP等&#xff0c;以及支持厂家私有协议与SDK接入&#xff0c;包括海康Ehome、海大宇等设备的SDK等。平台可拓展性强、…
阅读更多...
报错缺少class(org.apache.hadoop.hdfs.DistributedFileSystem)

报错缺少class(org.apache.hadoop.hdfs.DistributedFileSystem)

平台报错缺少 java.lang.RuntimeException:java.lang.ClassNotFoundException: Class org.apache.hadoop.hdfs.DistributedFileSystem not found 实则是缺少jar包 hadoop-hdfs-client-3.1.1.3.1.0.0-78.jar 找到对应的jar放到程序的lib中即可
阅读更多...
最新文章

Copyright @ 2022~2023