图论 <最短路问题>模板

这篇具有很好参考价值的文章主要介绍了图论 <最短路问题>模板。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

图论 <最短路问题>

有向图

1.邻接矩阵,稠密图

2.邻接表 (常用)单链表,每一个点都有一个单链表 ,插入一般在头的地方插,

图的邻接表的存储方式

树的深度优先遍历

特殊的深度优先搜索,难点是如何实现,一条道走到黑

const int N=100010,M=n*2;
int h[N],e[N],ne[N],idx;
bool st[N];//记录状态

void add(int a,int b)
{
	e[idx]=b;
	ne[idx]=h[a];
	h[a]=idx++;
}
void dfs(int u)
{
	st[u]=true;
	for(i=h[u];i!=-1;i=ne[i])
	{
		int j=e[i];//当前节点对应的图的值;
		if(!st[j])dfs(j);
	}
}
int main()
{
	memset(h,-1,sizeof(h));
	
	return 0;
}
树的宽度优先遍历

例题:图的层序搜索

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;

const int N=100010;
int n,m;
int d[N];
int e[N],h[N],idx,ne[N];
void add(int a,int b)
{
	e[idx]=b;
	ne[idx]=h[a];
    h[a]=idx++;
}
void bfs()
{memset(d,-1,sizeof d);
	queue<int> q;
	d[1]=0;
	q.push(1);
	while(q.size())
	{
		auto t=q.front();
		q.pop();
		for(int i=h[t];i!=-1;i=ne[i])
		{
			int j=e[i];
			if(d[j]==-1)
			{
				d[j]=d[t]+1;
				q.push(j);
			}
		}
	}
	printf("%d",d[n]);
}
int main()
{
	cin>>n>>m;
	memset(h,-1,sizeof h);
	for(int i=0;i<m;i++)
	{
		int a,b;
		cin>>a>>b;
		add(a,b);
	}
	bfs();
	
	return 0;
}
拓扑序列(有向图)

例题 :有向图的拓扑序列文章来源地址https://www.toymoban.com/news/detail-633037.html

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m;
int h[N], e[N], ne[N], idx;
int d[N];
int q[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

bool topsort()
{
    int hh = 0, tt = -1;

    for (int i = 1; i <= n; i ++ )
        if (!d[i])
            q[ ++ tt] = i;

    while (hh <= tt)
    {
        int t = q[hh ++ ];

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (-- d[j] == 0)
                q[ ++ tt] = j;
        }
    }

    return tt == n - 1;
}

int main()
{
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);

    for (int i = 0; i < m; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);

        d[b] ++ ;
    }

    if (!topsort()) puts("-1");
    else
    {
        for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);
        puts("");
    }

    return 0;
}
迪杰斯特拉算法(朴素版)
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int a1=510;
int n,m;
int g[a1][a1];
int dist[a1];
bool st[a1];
int dijk()
{
	memset(dist,0x3f,sizeof dist);
	dist[1]=0;
	for(int i=0;i<n-1;i++)
	{
		int t=-1;
		for(int j=1;j<=n;j++)
		{
			if(!st[j]&&(t==-1||dist[t]>dist[j]))t=j;
		}
		for(int j=1;j<=n;j++)
		dist[j]=min(dist[j],dist[t]+g[t][j]);
		
		st[t]=true;
	}
	if(dist[n]==0x3f3f3f3f)return -1;
	return dist[n];
}
int main()
{
	cin>>n>>m;
	memset(g,0x3f,sizeof g);
	while(m--)
	{
		int a,b,c;
		cin>>a>>b>>c;
		g[a][b]=min(g[a][b],c);
	}
	cout<<dijk();
	return 0;
}
迪杰斯特拉算法(堆优化版)
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
typedef pair<int,int> pii;
const int N =1e6 + 10;
int n,m,a,b,c;
int h[N],e[N],ne[N],w[N],idx;
int 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 dijk()
{
	memset(dist,0x3f3f3f3f,sizeof dist);
	dist[1]=0;
	priority_queue<pii, vector<pii>, greater<pii>> heap;
	heap.push({0,1});
	while(heap.size())
	{
		auto t=heap.top();
		heap.pop();
		int ver=t.second,distance=t.first;
		if(st[ver])continue;
		st[ver]=true;
		for(int i=h[ver];i!=-1;i=ne[i])
		{
			int j=e[i];
			if(dist[j]>dist[ver]+w[i])
			{
				dist[j]=dist[ver]+w[i];
				heap.push({dist[j],j});
			}
		}
	}
	if(dist[n]==0x3f3f3f3f)return -1;
	return dist[n];
}
int main()
{
	cin>>n>>m;
	memset(h,-1,sizeof h);
	while(m--)
	{
		cin>>a>>b>>c;
	    add(a,b,c);
	}
	cout<<dijk();
	return 0;
}

到了这里,关于图论 <最短路问题>模板的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • [算法日志]图论: 深度优先搜索(DFS)

    ​ 深度优先搜索算法是一种遍历图这种数据结构的算法策略,其中心思想是朝图节点的一个方向不断跳转,当该节点无下一个节点或所有方向都遍历完时,便回溯朝上一个节点的另一个方向继续遍历。这种搜索策略与回溯法有异曲同工之妙。 正因为和回溯法有相似之处,所

    2024年02月03日
    浏览(62)
  • Python 图算法,图最短路径,图广度优先搜索,图深度优先搜索,图排序

    一、图数据库相关算法 图数据库是一种专门用来存储和处理图数据的数据库系统。它使用图结构来表示数据之间的关联关系,以及节点和边之间的属性信息。以下是一些常用的图数据库算法: 1. 最短路径算法:最短路径算法用于计算图中两个节点之间的最短路径,例如Dijk

    2024年02月15日
    浏览(34)
  • 图论与算法(3)图的深度优先遍历

    图的遍历 是指按照一定规则访问图中的所有顶点,以便获取图的信息或执行特定操作。常见的图遍历算法包括深度优先搜索(DFS)和广度优先搜索(BFS)。 深度优先搜索 (DFS):从起始顶点开始,递归或使用栈的方式访问相邻的顶点,直到所有顶点都被访问过为止。DFS通过

    2024年02月06日
    浏览(47)
  • 图论与算法(7)最短路径问题

    最短路径问题是指在一个加权图中寻找两个顶点之间的最短路径,其中路径的长度由边的权重确定。 常见的最短路径算法包括: Dijkstra算法 :适用于解决单源最短路径问题,即从一个固定的起点到图中所有其他顶点的最短路径。该算法通过不断选择当前路径上权重最小的顶

    2024年02月06日
    浏览(41)
  • 图论算法|深度优先搜索理论基础|797.所有可能的路径|广度优先搜索BFS理论基础|200. 岛屿数量

    dfs是可一个方向去搜,不到黄河不回头,直到遇到绝境了,搜不下去了,在换方向(换方向的过程就涉及到了回溯)。 递归和回溯是相辅相成的 https://leetcode.cn/problems/all-paths-from-source-to-target/ 有向无环图(DAG): 有环无向图是指在图中存在至少一个环(Cycle)的无向图。环是

    2024年02月15日
    浏览(58)
  • 广度优先搜索(BFS)算法求解单源最短路径问题

      单源最短路径问题是图论中一类重要且常见的应用问题。在这个问题中,我们需要找到从一个给定源节点到其他节点的最短路径。广度优先搜索(BFS)算法是一种常用且有效的求解这一问题的算法。   本篇博客将重点讨论单源最短路径问题及其实际应用,同时简要介绍

    2024年02月13日
    浏览(45)
  • 【算法导论】图论(图的基本概念,图上的深度优先搜索(DFS),广度优先搜索(BFS),最小生成树(MST)及Prim,Kruskal算法)

    图(Graph)是一种包含节点与节点的边的集合,记作G=(V,E),V是节点的集合,E是边的集合。 有向图 一个有向图G=(V,E),E中每个元素是V上的一个二值关系:一条从a出发的连向b的边e可以记作一个 有序 对e = (a,b) 。 无向图 一个无向图G=(V,E),E的每个元素e可以表示V上的一个 无序 对,记

    2024年02月03日
    浏览(49)
  • Python算法:深度优先搜索—DFS(模板及其样例)

    • 沿着一条路径一直搜索下去,在无法搜索时,回退到刚刚访问过的节点。 • 并且每个节点只能访问一次。 • 本质上是持续搜索,遍历了所有可能的情况,必然能得到解。 • 流程是一个树的形式,每次一条路走到黑。 • 目的主要是达到被搜索结构的叶结点直到最后一层

    2024年03月24日
    浏览(48)
  • 数学建模十大算法04—图论算法(最短路径、最小生成树、最大流问题、二分图)

    一、最短路径问题 从图中的某个顶点出发,到达另一个顶点的 所经过的边的权重之和最小 的一条路径。 1.1 两个指定顶点之间的最短路径 问题如下:给出了一个连接若干个城镇的铁路网络,在这个网络的两个指定城镇间,求一条最短铁路线。 1.1.1 Dijkstra算法 迪杰斯特拉(D

    2024年02月02日
    浏览(71)
  • DFS (深度优先搜索) 算法详解 + 模板 + 例题,这一篇就够了

    深度优先搜索算法 (Depth First Search,简称DFS):一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件,搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所

    2024年02月02日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包