精华内容
下载资源
问答
  • 2021-12-04 11:15:11


    前言

    弗洛伊德算法是一种重要的图论算法,这篇文章将简单介绍它。



    一、弗洛伊德算法是什么?

     Floyd算法又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法。 

                                                                                                                          ——百度百科


    二、适用情况


    求多对点之间的最短路问题

    时间复杂度:O(n^3)

    空间复杂度:O(n^2)

    可以看出时间复杂度是非常惊人的,可是它有一个很重要的特性:

    Floyd最终求出了每对点之间的最短路

    因此在求多对点之间的最短路时,它是非常有优势的。



    三、代码实现

    (如果前面讲得不是很清楚,可以仔细阅读一下代码的注释。)

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    int m,n,d[301][301];
    int main()
    {
    	memset(d,0x3f,sizeof(d));//这里不能赋值为127,否则之后的加法会爆 
    	for(int i=1;i<=n;i++) d[i][i]=0;//自己到自己的距离为0(也可以不写) 
    	cin>>n>>m;//n为点数,m为边数 
    	for(int i=1;i<=m;i++)
    	{
    		int u,v,w;//u,v,w分别为起点、终点、权值 
    		cin>>u>>v>>w;
    		d[u][v]=min(d[u][v],w);//处理重边 
    		d[v][u]=min(d[v][u],w);//无向图的双向性 
    	}
    	for(int k=1;k<=n;k++)//一定要先枚举中转点 
    	{
    		for(int i=1;i<=n;i++)//枚举起点 
    		{
    			for(int j=1;j<=n;j++)//枚举终点 
    			{
    				//核心代码 
    				if(d[i][k]+d[k][j]<d[i][j])//如果经过中转点可以使直接从i到j的路费减少 
    				{
    					d[i][j]=d[i][k]+d[k][j];//松弛操作 
    				}
    			}
    		}
    	}
    	cout<<endl;//美观 
    	//输出
    	for(int i=1;i<n;i++)
    	{
    		for(int j=i+1;j<=n;j++)
    		{
    			if(d[i][j]!=1061109567)
    				cout<<i<<'-'<<j<<':'<<d[i][j]<<endl;
    		}
    	}
    	return 0;
    }

    带权值的无向图:(手绘略显粗糙)

     输入:

    输出:

     

     (全文终)

    更多相关内容
  • C++ 图论的基本应用

    2017-11-05 19:53:12
    图论的基本应用,对刚接触数据结构的小白们是很实用的
  • C++图论

    2021-12-26 14:17:58
    C++图论

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述


    在这里插入图片描述

    在这里插入图片描述

    //Author:PanDaoxi 
    #include <iostream>
    using namespace std;
    int g[1001][1001];
    int main(){
    	int n,e,a,b;
    	cin>>n>>e; //顶点和边数
    	//接收边的状态
    	for(int i=1;i<=e;i++){
    		cin>>a>>b;
    		g[a][b]=1;
    		g[b][a]=1;
    	} 
    	//邻接矩阵
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=n;j++){
    			cout<<g[i][j];
    		}
    		cout<<endl; 
    	}
    	return 0;
    } 
    
    展开全文
  • c++入门——图论基础,带标程,带习题,赶紧下载吧
  • C++图论简单介绍

    2020-12-25 09:22:07
    哈喽,大家好,我是赏月君,今天讲一下图论,废话少说,走起。 图由顶点( vertex, node )和边( edge)组成。顶点代表对象。在示意图中,我们使用点或圆来表示。边表示的是两个对象的连接关系。在示意图中,我们使用...

    哈喽,大家好,我是赏月君,今天讲一下图论,废话少说,走起。
    图由顶点( vertex, node )和边( edge)组成。顶点代表对象。在示意图中,我们使用点或圆来表示。边表示的是两个对象的连接关系。在示意图中,我们使用连接两顶点之间的线段来表示。顶点的集合是V、边的集合是E的图记为G =(V, E),连接两点u和v的边用e=(u, v)表示。
    图的例子
    1.图的种类
    图大体上分为2种。边没有指向性的图叫做无向图,边具有指向性的图叫做有向图。表示朋友关系的图(顶点表示人、边表示朋友关系的图)和路线图是无向图。表示数值的大小关系的图(顶点表示数值、A>B时从A向B连一条边得 到的图)和流程图是有向图。
    无向图的例子
    有向图的例子
    我们可以给边赋子各种各样的属性。比较具有代表性的有权值( cost)。边上带有权值的图叫做带权图。在不同问题中,权值可以代表距离、时间以及价格等不同的属性。
    2.无向图的术语
    两个顶点之间如果有边连接,那么就视为两个顶点相邻。相邻顶点的序列称为路径。起点和终点重合的路径叫做圈。任意两点之间都有路径连接的图叫做连通图。顶点连接的边数叫做这个顶点的度。
    路径和圈的例子

    连通图
    度
    没有圈的连通图叫做树( tree),没有圈的非连通图叫做森林。一棵树的边数恰好是顶点数-1。反之,边数等于顶点数-1的连通图就是一棵树。
    如果在树上选择一个顶点作为根( root),就可以把根提到最上面,而离根越远的顶点越往下安排其位置。这样的树叫做有根树。不过,对于无根树,有时选择适当的顶点作为根使之变成有根树,可以使问题得到简化。如果把有根树看作家谱图,则可以在顶点之间建立父子关系。也可以认为这是给边加上了方向。

    有根树的例子
    树的例子
    3.有向图的术语
    以有向图的顶点v为起点的边的集合记作E+(v), 以顶点v为终点的边的集合记作E_(v)。|E+(v)|叫做v的出度,|E_(v)|叫做边的入度。
    出度和入度
    没有圈的有向图叫做DAG ( Directed Acyclic Graph)。例如,让我们用顶点表示整数,n能整除m时从n向m连一条边的图,这就构成一个DAG。 像下图一样, 在DAG中我们可以给顶点标记一个先后顺序。
    DAG的例子
    对于每个顶点我们给它一个编号,第i号顶点叫做vi。那么存在从顶点vi到顶点vj的边时就有i<j成立,这样的编号方式叫做拓扑序。
    上图的拓扑序
    如果把图中的顶点按照拓扑序从左到右排列,那么所有的边都是从左指向右的。因此,通过这样的编号方式,有些DAG问题就可以使用DP来解决了。求解拓扑序的算法叫做拓扑排序。

    图的表示

    为了能在程序中对图进行处理,需要把顶点和边用具体的数据结构存储下来。在图的表示方法中,比较具有代表性的有邻接矩阵和邻接表。需要注意的是,两种表示方法都有各自的优缺点,根据问题的不同,使用不同的存储方式可能会影响算法的时间复杂度。接下来,记顶点和边的集合为V和E,|V|和|E|表示顶点和边的个数。另外,在V中,顶点被编号为0~|V|-1。
    1.邻接矩阵
    邻接矩阵使用|V|x|V|的二维数组来表示图。g[i][j]表示的是 顶点i和顶点j的关系。
    由于在无向图中,只需知道“顶点i和顶点j之间是否有边连着”这样的信息,因此如果顶点i和顶点j之间有边相连,那么g[i][j]和g[j][i]就设为1,否则设为0。这样就可以表示一个无向图了。
    无向图和对应的邻接矩阵
    由于在有向图中,只需要知道“是否有从顶点i发出指向顶点j的边”这样的信息,因此如果顶点i有一条指向顶点j的边,那么g[i][j]就设为1,否则设为0。这样就可以表示一个有向图了。 有向图与无向图不同,并不需要满足g[i][j]= g[j][i]。
    有向图和对应的邻接矩阵
    在带权图中,8[i][j]表示的是顶点i到顶点j的边的权值。由于在边不存在的情况下,如果将g[i][j]设为0,就无法和权值为0的情况区分开来,因此选取适当的较大的常数INF (只要能和普通的权值区别开来就可以了),然后令g[i][j]=INF就好了。当然,在无向图中还是要保持g[i][j]=g[i][j]。在一条边上有多种不同权值的情况下,定义多个同样的|V|x|V|数组,或者是使用结构体或类作为数组的元素,就可以和原来一样对图进行处理了。
    带权图和对应的邻接矩阵
    使用邻接矩阵的好处是可以在常数时间内判断两点之间是否有边存在,但是需要花费O(|V|²)的空间。在边很少的稀疏图里十分浪费。例如,如果图是一棵树,因为边数只有|V|-1条,所以数组g绝大部分的元素都变成了0。在|V|达到1000000时,即使g的每个元素只需要1个字节的空间,整个数组也需要1TB才能存下。
    此外,两点之间有重边或者某个顶点有自环(参照下图)的情况需要特别注意。在无权图中,只需要设g[i][j]为顶点i到顶点j的边数即可,但是在带权图中却无法这样。大部分情况下,只需要保存权值最小(最大)的边就可以了,所以在这种情况下可以无视其他的边。必须保存所有的边时,可以使用邻接表。
    重边和自环
    2.邻接表
    用邻接矩阵表示稀疏图会浪费大量内存空间。而在邻接表中,是通过把“从顶点0出发有到顶点2, 4, 5的边”这样的信息保存在链表中来表示图的。这样只需要O(|V|+|E|)的内存空间。
    邻接表
    事实上,实现邻接表的方式多种多样,每个人的写法可能都有所不同。下面是邻接表的一种实现方式。输人数据如下所示。

    3 3	//(顶点数边数)
    0 1 //(有一条0到1的边)
    0 2 //(有一条0到2的边)
    1 2 //(有一条1到2的边)
    

    样例

    vector<int> G[MAX_V];
    int main(){
    	int V,E;
    	scanf("%d %d",&V, &E);
    	for(int i=0;i<E;i++){
    		//从s向t连边
    		int s,t;
    		scanf("%d %d",&s,&t);
    		G[s].push_back(t);
    		//如果是无向图,则需要再从t向s连边
    	}
    	return 0;
    }
    
    展开全文
  • 找第K短路 c++ 图论

    2013-08-06 16:23:22
    这是运用C++求出来的第k短路,属于图论
  • C++图论(第二弹)

    2022-01-02 13:41:10
    元旦快乐呀! 祝大家2022心想事成、工作顺利! 今天我们继续来学习图论,和弗洛伊德算法。

    元旦快乐呀!
    祝大家2022心想事成、工作顺利!


    今天我们继续来学习图论,和弗洛伊德算法
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    来做一道案例:
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    根据以上内容可以推出:
    在这里插入图片描述
    注意:
    在这里插入图片描述
    因此可写代码:

    //Author:PanDaoxi
    #include <iostream>
    using namespace std;
    int e[101][101];
    int n,m; //n=顶点数 m=边数
    int p,q,t; //p=p点 q=q点 t=路程
    int s=100001; 
    int main(){
    	cin>>n>>m; //输入顶点和边数
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=n;j++){
    			if(i==j){
    				e[i][j]=0; //如果点是当前位置,则距离为0 
    			} 
    			else{
    				e[i][j]=s;
    			}
    		}
    	} 
    	//路程的设定
    	for(int i=1;i<=m;i++){
    		cin>>p>>q>>t;
    		e[p][q]=t; //有向图  
    	} 
    	//弗洛伊德算法
    	for(int k=1;k<=n;k++){
    		//城市i到城市j的不同组合 
    		for(int i=1;i<=n;i++){
    			for(int j=1;j<=n;j++){
    				//判断最短路径
    				if(e[i][j]>e[i][k]+e[k][j]){
    					e[i][j]=e[i][k]+e[k][j];
    				} 
    			}
    		}
    	} 
    	 
    	//最短路径
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=n;j++){
    			cout<<e[i][j]<<" ";
    		}
    		cout<<endl;
    	} 
    	return 0;
    } 
    

    测试数据:

    4 8
    1 2 2
    1 3 6
    1 4 4
    2 3 3
    3 1 7
    3 4 1
    4 1 5
    

    在这里插入图片描述


    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • C++ 图论之最短路径

    千次阅读 2019-04-09 19:09:05
    C++代码: // // 1447.cpp // 最短路 // // Created by chenmeiqi on 2019/4/9. // Copyright © 2019年 chenmeiqi. All rights reserved. // #include <iostream> using namespace std...
  • ![图片说明]... 我的想法是 一个红色单元有4个顶点,相邻的单元是共享一个节点的 有没有什么算法是让他们往外面跑一圈,形成一个回路。就像从左上角出发,沿着边边走一圈。如果最终回到原点。...
  • C++ 图论 离散数学

    2014-03-30 22:50:23
    以偶对的形式输入一个无向简单图的边,建立该图的邻接矩阵,判断图是否连通(A)。并计算任意两个结点间的距离(B)。对不连通的图输出其各个连通支(C)。
  • 题目描述: C 国有 n个大城市和m 条道路,每条道路连接这n 个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这m 条道路中有一部分为单向通行的道路,一部分为双向通行的道路,双向通行的道路在...
  • c++图论基础——邻接图、邻接表模板
  • C++关于图论的入门常识(一)

    千次阅读 2019-01-30 20:35:18
    这篇文章咩,主要给大家讲一下图论的有关知识和基本算法
  • 图论代码大全(C++)

    2021-11-06 16:42:10
    系统性去总结图论的知识点,有关于邻接矩阵等多方面知识点,有利于我巩固专业课上的知识点,也是自己认真去了解各项学习任务的进度。 图的表示,矩阵,邻接矩阵 用邻接矩阵表示顶点间的相邻关系 用一个顺序表来...
  • 图论搜索技术深度优先搜索 (应用——求重心)广度优先搜索 (应用——图中的层次遍历)有向图的拓扑排序最短路问题Dijkstra算法(朴素版)Dijkstra算法 (堆优化)bellman_ford算法spfa算法spfa判负权Floyd算法最...
  • C++图论强连通分量讲解

    千次阅读 2019-05-30 17:39:00
    前言: 强连通分量好强,老师好喜欢(考)。 概念: 在有向图G中,如果两点互相可达,则称这两个点强连通,如果G中任意两点互相可达,则称G是强连通图。 1、一个有向图是强连通的,当且仅当G中有一个回路,它至少...
  • 用一个Edge类描述顶点与边 #pragma once #include <iostream> #include <cassert> using namespace std; template<typename Weight> class Edge { private: int a, b;... this-
  • 图论基本算法c++实现

    2019-10-31 18:40:48
    #include<iostream> #include<vector> #include<set> #include<map> #include<list> #include<float.h> #include <regex> #include <string>...fstream...
  • 图论问题的算法 (C++)

    2022-04-07 19:41:53
    图论问题的算法 有向图的拓扑排序 单源最短路径算法 多源最短路径算法 最小生成树算法 染色法判定二分图
  • Graph_cpp:C ++图论算法

    2021-02-15 13:49:09
    C ++图论算法
  • C++ 图论之邻接链表的实现

    千次阅读 2019-04-02 19:53:42
    为了使用vector我们还需在C++源文件头部添加相应的头文件。   下面,我们学习如何为这些“单链表”添加和删除信息。 利用 for(int i=0;i;i++){ // 遍历所有结点 eage[i].clear(); // 清空其单链表 }...
  • 图论的学习

    2019-02-13 18:12:33
    图论的练习。
  • dijkstra堆优化 + 优先队列 题中是有向图,求最短路径, 若不能达到,便输出2的31次方-1 样例分析: 可以使用多种方法,但题中已经说明:不得使用SPFA 所以此处使用的是dijkstra算法 代码如下: ...
  • [C++图论] 强连通

    千次阅读 2019-06-05 14:21:27
    文章目录概念 概念 在一个有向图中,如果说有两个点互相可达,那么这两个点就可说是 强连通。当然,官方语言(度娘解释)是这样的: 强连通(Strongly Connected)是指一个有向图(Directed Graph)中任意两点...
  • 板题——最优布线问题 题目描述 学校有n台计算机,为了方便数据传输,现要将它们用数据线连接起来。两台计算机被连接是指它们中间有数据线连接。由于计算机所处的位置不同,因此不同的两台计算机的连接费用往往是...
  • 浅析图论算法 引言 众所周知,图论在现实中应用广泛,本文旨在巩固本人的数据结构与算法基础,也希望能帮助算法学习者快速理解图论基本算法,现就其作如下浅析。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 16,371
精华内容 6,548
关键字:

c++ 图论

c++ 订阅
友情链接: q0w9qo.zip