图论

2022/9/1 23:26:03

本文主要是介绍图论,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

多源最短路(在曼哈顿图中)(无例题)(使用BFS,队列):

  操作的地图要有两个特点:既可以表示结果中所要的最短距离,又能记录这个点是否走过,那就全部memset为一个特殊的数-1(这里一定要专门设计一个结果图,不能只用最初的图,让最初的图承担三个责任,它哪里做的到啊(表示举例,判重,记录最初信息)(非要做的话,你可以想象,如果发现一个点可以是起点,那就改变其值为0,这个0要如何与其他没去过的点的0区分呢,如果另开一个数组那就可以区分了,起点处是0,没去过的地方是-1)),这就是个特殊的判重技巧:另开一个数组。

  本题代码有个bug,不知道为什么输出结果有误,以后改过来。

  题目:

  code:

View Code

dijkstra算法:

问题:给出一个有向图,请问图中某一个点(这个点记作源点)到其余各点的最短距离是多少?

思路:(基于贪心算法)

  1.将所有点到源点的距离初始化为无穷大

  2.找到图中目前为止距离源最近的点

  3.更新这个点的所有邻点的距离(松弛操作)

  4.反复2,3操作直到遍历所有点为止

时间复杂度:O(n^2+m)

缺点:不能找出带有负边权的图,不能解决带有负环的图

注:vector是一个什么样的数据结构呢?vector是一个动态数组,像vector <int>a;这样就已经创建了一个整型数组。

题目:洛谷P3371

#include <bits/stdc++.h>
using namespace std;
struct edge{int v,w;};
int n,m,s,visit[10005],d[10005];
vector<edge>ed[10005];
#define inf 2147483647
void dijkstra(){
    for(int i=1;i<n;i++){
        int u=0;
        for(int j=1;j<=n;j++)
            if(d[j]<d[u] && visit[j]==0)u=j;
        visit[u]=1;
        for(edge e:ed[u]){
            int v=e.v,w=e.w;
            if(d[v]>d[u]+w)d[v]=d[u]+w;
        }
    }
}
int main(){
    cin>>n>>m>>s;
    for(int i=0;i<=n;i++)d[i]=inf;
    d[s]=0;
    int u,v,w;
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        ed[u].push_back({v,w});
    }
    dijkstra();
    for(int i=1;i<=n;i++)cout<<d[i]<<' ';
    return 0;
}

dijkstra可以用堆来优化,得到heap-dijkstra算法

学会了dijkstra算法的堆优化,其实就是用一个小根堆来维护队列,将距离的相反数储存起来,这样堆顶的元素距离就最小(相反数最大)。

随后遍历每个点,已经遍历过的就打上visit标记不再遍历。题目:洛谷P4779.代码:

View Code

 解析错误RE(runtime error):

1.数组开的小了,但题目数据规模大于数组的大小,所以根本给不出结果

2.数组开的太大了,系统根本给不出这么大的空间

3.除数是0

 bellman-ford算法:

问题:给出从一个点到其他点的最短距离,存在权值为负的边。

思路:

  1.进行n轮判断

  2.每轮判断中,对每条边都进行更新

  3.如果某一轮没有再更新,那就停止判断

时间复杂度:一共n轮判断,每轮m条边,所以时间复杂度O(nm)

优点:可以判断负环

名词解释:什么是负环?

图中有一条路经过的边的权值之和是负数。这样一个图没有最短路,因为每走一遍这条路,权值都会变小。

如何用bellman-ford判断负环?

答:bellman-ford算法通过迭代算最短路径,每轮至少更新一个结点,最多更新n-1个结点,如果第n轮时发现仍有可以被更新的结点,那么存在负环。

题目:P3385

代码:

View Code

注:这个代码没过,而且不知道为啥过不去

 

背诵一个数字:2的32次方-1是21 47 48 36 47

生成树:

  在一个连通图中,如果一个连通子图用n-1条边连接了全部N个点,这个连通子图就可以被称为生成树。

  在一个带权图中,各边权值最小的生成树就是最小生成树。(MST,minimum spanning tree)

  题目:洛谷P3366

#include <bits/stdc++.h>
using namespace std;
int n,m,ans,d[5005],visit[5005],cnt;
struct edge{int v,w;};
vector<edge>ed[5005];
const int inf=2147483647;
int prim(){
    for(int i=0;i<=n;i++)d[i]=inf;
    d[1]=0;
    for(int i=1;i<=n;i++){
        int u=0;
        for(int j=1;j<=n;j++){//找出最近的点 
            if(visit[j]==0 && d[j]<d[u])u=j;
        }
        
        
        visit[u]=1;//标记出圈 
        ans+=d[u];
        
        
        if(d[u]!=inf)cnt++;//有一个点被画出圈外
        
        for(edge e:ed[u]){
            int v=e.v,w=e.w;
            if(d[v]>w)d[v]=w;
        }
    }
    return cnt==n;
}
int main(){
    cin>>n>>m;
    int a,b,c;
    for(int i=1;i<=m;i++){
        cin>>a>>b>>c;
        ed[a].push_back({b,c});
        ed[b].push_back({a,c});
    }
    if(prim())cout<<ans;
    else cout<<"orz";
    return 0;
}

 

  寻找方法:PRIM算法,思想贪心。

bellman-ford算法优化算法:  spfa(shortest path faster algorithm)(戏称shortest path fake algorithm)

考虑到在bellman-ford算法中每轮的判断其实不用考虑每一条边,只用考虑那些可能更新的边,所以开数组visit和队列q,visit用来标记点是否在队列内,相当于给队列加个扩展的小功能。在队列中进行大家习惯的更新操作。加一个cnt数组记录边数(某一条路径上经过了多少边)。

题目:P3385

代码:

View Code

注:还是过不去,不知道为啥。

全源最短路算法(DP算法):(思想:动态规划,插点法)

  1.遍历每个点作为插点

  2.某个点作为插点时,更新从i到j的距离

图的储存方法:邻接矩阵法

优点:可以解决负权和负环问题。

最小环问题,使用floyd算法。P6175

View Code

思路:插值,假设图中序号最大的点序号是k,k的邻居是i,j。看看i,k,j是不是最短路,不是的话就考虑下一个K。在此过程中用floyd算法不断更新i,j之间的距离备用。

模板:

View Code

最小生成树:

稠密图用prim,稀疏图用kruskal。

题目:洛谷P3366.

思想:运用并查集与贪心算法求最小生成树

步骤:

1.初始化并查集,将n个点放入n个独立集合。

2.将每条边按照边权从小到大排序。

3.枚举每条边,如果边上的两个点不在同一个集合,那就合并起来并且加入最小生成树;如果在同一集合,那就跳过。

4.重复步骤3直到选取了n-1条边。如果不是连通图的话就选不了n-1条边。

View Code

复杂度:O(mlogm)(来自于排序sort)

这题过不了。。。。

lowest common ancestor最近公共祖先:

倍增算法:最经典的LCA算法。

预处理:

两个数组dep[u]结点u的深度,fa[u][i]结点u向上跳2的i层的祖先。

步骤:1.DFS求出两个数组,称为求ST表  2.在已经求好的ST表中求LCA,步骤有2,首先将u,v跳至同一层,其次将u和v跳至LCA的下一层

题目:洛谷P3379

View Code

 

最近公共组先tarjan(塔杨算法)算法:

使用并查集进行离线(全部输入)计算。

在线计算:一般输入一边计算。

View Code

 

树剖算法写LCA:

洛谷3379:

View Code

算法复杂度:dfs1:O(n)  dfs2:O(n)  lca:O(mlog(n))(这是因为最多log(n)个重链)  一共O(n+mlog(n))

fa:父节点

son:重儿子

sz:该结点子树的结点数目

top:结点所在重链的根结点。轻儿子的根节点是它自己
dep:结点的深度

重儿子:子结点中sz最大的那个

轻儿子:除了重儿子之外的都是轻儿子
重链:重儿子们集合起来的链

 

三种算法比较:

倍增算法:最经典

tarjan:最高效

树剖:另有他用

 

DAG:有向无环图

AOV:activity on vertex network,用顶点表示活动的网络

我们往往用AOV或者DAG来表示一个大工程中各个小工程的前后顺序,而拓扑排序就是在AOV或DAG中找到一个可以正确施工的流程。

拓扑排序步骤:

1.将入度为0的点放入栈中

2.弹栈,将入度为0的点周围的邻点做处理:使邻点的入度减一,如果领点入度为0则入栈

反复执行第二步直到栈空

1.邻接矩阵法

View Code

 时间复杂度==空间复杂度==O(n^2),建议用在点不多的稠密图中

2.边集数组

View Code

时间复杂度O(n*m),空间复杂度O(m)

3.邻接表

View Code

时间复杂度O(n+m),原因:每个点都要遍历,总体来看每条边都要遍历;空间复杂度:O(n+m)。时间复杂度大大降低,但可惜不能处理反向边。

4.链式邻接表

5.链式前向星

学不会,先看别的,等哪天要用的时候再回来补上

手敲了两遍三种存储方式就十点半了。。时间贵如油哦。



这篇关于图论的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程