建设银行北京招聘网站,吉安企业做网站,成免费crm特色,售后服务 网站建设图 1. 图的基本概念2. 图的存储结构2.1 邻接矩阵2.2 邻接表2.3 邻接矩阵的实现2.4 邻接表的实现 3. 图的遍历3.1 图的广度优先遍历3.2 图的深度优先遍历 4. 最小生成树4.1 Kruskal算法4.2 Prim算法 5. 最短路径5.1 单源最短路径--Dijkstra算法5.2 单源最短路径--Bellman-Ford算… 图 1. 图的基本概念2. 图的存储结构2.1 邻接矩阵2.2 邻接表2.3 邻接矩阵的实现2.4 邻接表的实现 3. 图的遍历3.1 图的广度优先遍历3.2 图的深度优先遍历 4. 最小生成树4.1 Kruskal算法4.2 Prim算法 5. 最短路径5.1 单源最短路径--Dijkstra算法5.2 单源最短路径--Bellman-Ford算法5.3 多源最短路径--Floyd-Warshall算法 点赞收藏关注 你的支持是对我最大的鼓励我们一起努力吧! 1. 图的基本概念
图是由顶点集合及顶点间的关系组成的一种数据结构G (V E)其中
顶点集合V {x|x属于某个数据对象集}是有穷非空集合
E {(x,y)|x,y属于V}或者E {x, y|x,y属于V Path(x, y)}是顶点间关系的有穷集合也叫做边的集合。
(x, y)表示x到y的一条双向通路即(x, y)是无方向的Path(x, y)表示从x到y的一条单向通路即Path(x, y)是有方向的。
顶点和边图中结点称为顶点第i个顶点记作vi。两个顶点vi和vj相关联称作顶点vi和顶点vj之间有一条边图中的第k条边记作ekek (vivj)或vivj。
有向图和无向图在有向图中顶点对x, y是有序的顶点对xy称为顶点x到顶点y的一条边(弧)x, y和y, x是两条不同的边比如下图G3和G4为有向图。在无向图中顶点对(x, y)是无序的顶点对(x,y)称为顶点x和顶点y相关联的一条边这条边没有特定方向(x, y)和(yx)是同一条边比如下图G1和G2为无向图。注意无向边(x, y)等于有向边x, y和y, x。
下面是一些常见的图G2看着是一颗二叉树为什么也说是图呢 可以这样理解树是一种特殊(无环连通)的图图不一定是树。树关注的节点(顶点)中存的值以及连通关系图关注的是顶点及边的权值。边由三部分组成两个顶点、权值
树是一种存储式数据结构节点内存值然后构成二叉搜索树AVL树红黑树。 图是一种表示型数据结构表示某种场景。
比如说下面的图顶点可能表示城市边表示城市之间一个关系高铁距离、高铁价格、高铁时间。。。
有了这个东西提出DFSBFS遍历最小生成树最小代价把图连图最短路径(一个顶点到其他顶点 或者 多个顶点之间 最短路径)的问题。 图还可以用来表示社交关系
顶点人 边表示两个人是好友 边权值亲密度等
微信qq等关系-无向图(强社交关系) 微博抖音等关系-有向图(弱社交关系、媒体社交) 完全图(任意两个顶点都有边)在有n个顶点的无向图中若有n * (n-1)/2条边(n个顶点 1-n-12-n-2 … n-0 等差数列)即任意两个顶点之间有且仅有一条边则称此图为无向完全图比如上图G1在n个顶点的有向图中若有n * (n-1)条边即任意两个顶点之间有且仅有方向相反的边则称此图为有向完全图比如上图G4。
邻接顶点在无向图中G中若(u, v)是E(G)中的一条边则称u和v互为邻接顶点并称边(u,v)依附于顶点u和v在有向图G中若u, v是E(G)中的一条边则称顶点u邻接到v顶点v邻接自顶点u并称边u, v与顶点u和顶点v相关联。
顶点的度顶点v的度是指与它相关联的边的条数记作deg(v)。在有向图中顶点的度等于该顶点的入度与出度之和其中顶点v的入度是以v为终点的有向边的条数记作indev(v)顶点v的出度是以v为起始点的有向边的条数记作outdev(v)。因此dev(v) indev(v) outdev(v)。注意对于无向图顶点的度等于该顶点的入度和出度即dev(v) indev(v) outdev(v)。
路径在图G (V E)中若从顶点vi出发有一组边使其可到达顶点vj则称顶点vi到顶点vj的顶点序列为从顶点vi到顶点vj的路径。
路径长度对于不带权的图一条路径的路径长度是指该路径上的边的条数对于带权的图一条路径的路径长度是指该路径上各个边权值的总和。 简单路径与回路若路径上各顶点v1v2v3…vm均不重复则称这样的路径为简单路径。若路径上第一个顶点v1和最后一个顶点vm重合则称这样的路径为回路或环。 子图设图G {V, E}和图G1 {V1E1}若V1属于V且E1属于E则称G1是G的子图。 连通图(连通图是针对无向图来说的)在无向图中若从顶点v1到顶点v2有路径则称顶点v1与顶点v2是连通的。如果图中任意一对顶点都是连通的则称此图为连通图。
强连通图(强连通图是针对有向图来说的)在有向图中若在每一对顶点vi和vj之间都存在一条从vi到vj的路径也存在一条从vj到vi的路径则称此图是强连通图。
生成树一个连通图的最小连通子图称作该图的生成树。有n个顶点的连通图的生成树有n个顶点和n-1条边。
2. 图的存储结构
因为图中既有节点又有边(节点与节点之间的关系)因此在图的存储中只需要保存节点和边关系即可。节点保存比较简单只需要一段连续空间即可那边关系该怎么保存呢
顶点我们可以像并查集哪里一样用vector和map保存那边如何保存呢
//V 顶点类型, W 权值类型, Direction 表示有向/无向
templateclass V,class W,bool Direction
class Graph
{private:vectorV _vertexs;//顶点集合mapV, int _IndexMap;//顶点与下标映射
};2.1 邻接矩阵
因为节点与节点之间的关系就是连通与否即为0或者1因此邻接矩阵(二维数组)即是先用一个数组将顶点保存(将顶点转化成对应的下标比如说顶点是abcd编号就是0123)然后采用矩阵来表示节点与节点之间的关系。 注意
无向图的邻接矩阵是对称的第i行(列)元素之和就是顶点i的度。有向图的邻接矩阵则不一定是对称的第i行(列)元素之后就是顶点i 的出(入)度。如果边带有权值并且两个节点之间是连通的上图中的边的关系就用权值代替如果两个顶点不通则使用无穷大代替 3. 用邻接矩阵存储图的有点是能够快速知道两个顶点是否连通缺陷是如果顶点比较多边比较少时矩阵中存储了大量的0成为系数矩阵比较浪费空间并且要求两个节点之间的路径不是很好求。
优点
邻接矩阵存储方式非常适合稠密图 邻接矩阵O(1)判断两个顶点的连接关系并取到权值
缺点
相对而言不适合查找一个顶点连接所有边 — O(N)
假设有n个顶点是不是要所有顶点遍历一遍才知道某个顶点到底和那些顶点相连。 时间复杂度是O(N)N是顶点个数。
假设有100个顶点我这个顶点只和三个顶点相连只有三条边但也要遍历100次能不能有个方法快速把与之相连的三条边都找到呢
2.2 邻接表
邻接表使用数组表示顶点的集合使用链表表示边的关系。
邻接表和哈希桶类似。使用一个指针数组把自己和连接的顶点边都挂在下面。
无向图邻接表存储 注意无向图中同一条边在邻接表中出现了两次。如果想知道顶点vi的度只需要知道顶点vi边链表集合中结点的数目即可。
优点
适合存储稀疏图 适合查找一个顶点连接出去的边
缺点
不适合确定两个顶点是否相连及权值
有向图邻接表存储 注意有向图中每条边在邻接表中只出现一次与顶点vi对应的邻接表所含结点的个数就是该顶点的出度也称出度表要得到vi顶点的入度必须检测其他所有顶点对应的边链表看有多少边顶点的dst取值是i。
一般情况下有向图存储一个出边表即可。
总结一下邻接矩阵和邻接表其实属于相辅相成各有优缺点的互补结构。具体还是看场景选择用邻接矩阵和邻接表
2.3 邻接矩阵的实现
//类型模板参数: V 顶点类型(int,char...), W 权值类型(int,double...), Direction 表示有向/无向(默认无向)
//非类型模板参数: MAX_W 默认权值
templateclass V, class W, W MAX_W INT_MAX, bool Direction false
class Graph
{
public:private:vectorV _vertexs; //顶点集合mapV, int _IndexMap; //顶点与下标映射vectorvectorW _matrix; //邻接矩阵(边的集合)
};图的创建有下面几种方式
IO输入 ------ 自己写不方便测试oj中更适合图的结构关系写到文件读取文件手动添加边 我们采用的方式
Graph(const V* a, size_t n)
{_vertexs.reserve(n);for (size_t i 0; i n; i){_vertexs.push_back(a[i]);_IndexMap[a[i]] i;}_matrix.resize(n);for (size_t i 0; i n; i){_matrix[i].resize(n, MAX_W);}
}添加边
首先我们要找到边对应两个顶点的下标然后才在矩阵添加边的信息注意区分有向图还是无向图。
size_t GetVertexindex(const V v)
{//不能直接用[]去查,万一不在就成插入了auto it _IndexMap.find(v);if (it ! _IndexMap.end()){return it-second;}else{throw invalid_argument(不存在的顶点);return -1;}
}void _AddEdge(const size_t srci, const size_t dsti, const W w)
{_matrix[srci][dsti] w;if (Direction false) // 无向图{_matrix[dsti][srci] w;}
}void AddEdge(const V src, const V dst, const W w)
{size_t srci GetVertexindex(src);size_t dsti GetVertexindex(dst);_AddEdge(srci, dsti, w);
}打印
void Print()
{// 顶点for (size_t i 0; i _vertexs.size(); i){cout [ i ] - _vertexs[i] endl;}cout endl;// 矩阵// 横下标cout ;for (size_t i 0; i _vertexs.size(); i){//cout i ;printf(%4d, i);}cout endl;for (size_t i 0; i _matrix.size(); i){cout i ; // 竖下标for (size_t j 0; j _matrix[i].size(); j){//cout _matrix[i][j] ;if (_matrix[i][j] MAX_W){//cout * ;printf(%4c, *);}else{//cout _matrix[i][j] ;printf(%4d, _matrix[i][j]);}}cout endl;}cout endl;
}下面我们测试一下
void TestGraph()
{Graphchar, int, INT_MAX, true g(0123, 4);g.AddEdge(0, 1, 1);g.AddEdge(0, 3, 4);g.AddEdge(1, 3, 2);g.AddEdge(1, 2, 9);g.AddEdge(2, 3, 8);g.AddEdge(2, 1, 5);g.AddEdge(2, 0, 3);g.AddEdge(3, 2, 6);g.Print();
}完整代码
//类型模板参数: V 顶点类型(int,char...), W 权值类型(int,double...), Direction 表示有向/无向(默认无向)
//非类型模板参数: MAX_W 默认权值
templateclass V, class W, W MAX_W INT_MAX, bool Direction false
class Graph
{
public:Graph(const V* a, size_t n){_vertexs.reserve(n);for (size_t i 0; i n; i){_vertexs.push_back(a[i]);_IndexMap[a[i]] i;}_matrix.resize(n);for (size_t i 0; i n; i){_matrix[i].resize(n, MAX_W);} }size_t GetVertexindex(const V v){//不能直接用[]去查,万一不在就成插入了auto it _IndexMap.find(v);if (it ! _IndexMap.end()){return it-second;}else{throw invalid_argument(不存在的顶点);return -1;}}void _AddEdge(const size_t srci, const size_t dsti, const W w){_matrix[srci][dsti] w;if (Direction false) // 无向图{_matrix[dsti][srci] w;}}void AddEdge(const V src, const V dst, const W w){size_t srci GetVertexindex(src);size_t dsti GetVertexindex(dst);_AddEdge(srci, dsti, w);}void Print(){// 顶点for (size_t i 0; i _vertexs.size(); i){cout [ i ] - _vertexs[i] endl;}cout endl;// 矩阵// 横下标cout ;for (size_t i 0; i _vertexs.size(); i){//cout i ;printf(%4d, i);}cout endl;for (size_t i 0; i _matrix.size(); i){cout i ; // 竖下标for (size_t j 0; j _matrix[i].size(); j){//cout _matrix[i][j] ;if (_matrix[i][j] MAX_W){//cout * ;printf(%4c, *);}else{//cout _matrix[i][j] ;printf(%4d, _matrix[i][j]);}}cout endl;}cout endl;}private:vectorV _vertexs; //顶点集合mapV, int _IndexMap; //顶点与下标映射vectorvectorW _matrix; //邻接矩阵(边的集合)
};2.4 邻接表的实现
邻接表实际也是一个哈希桶这里实现很简单
//存储边的信息
templateclass W
struct Edge
{size_t _srci;//起始点size_t _dsti;//目标点的下标W _w;//权值EdgeW* _next;Edge(const size_t srci,const size_t dsti,const W w):_srci(srci),_dsti(dsti),_w(w),_next(nullptr){}
};templateclass V,class W,bool Direction false
class Graph
{typedef EdgeW Edge;
public:Graph(const V* a, size_t n){_vertexs.reserve(n);for (size_t i 0; i n; i){_vertexs.push_back(a[i]);_IndexMap[a[i]] i;}_tables.resize(n, nullptr);}size_t GetVertexindex(const V v){auto it _IndexMap.find(v);if (it ! _IndexMap.end()){return it-second;}else{throw invalid_argument(不存在的顶点);return -1;}}void _AddEdge(const size_t srci, const size_t dsti,const W w){//头插Edge* edge new Edge(srci, dsti, w);edge-_next _tables[srci];_tables[srci] edge;if (Direction false) // 无向图{Edge* new_edge new Edge(dsti, srci, w);new_edge-_next _tables[dsti];_tables[dsti] new_edge;}}void AddEdge(const V src, const V dst, const W w){size_t srci GetVertexindex(src);size_t dsti GetVertexindex(dst);_AddEdge(srci, dsti, w);}void Print(){// 顶点for (size_t i 0; i _vertexs.size(); i){cout [ i ] - _vertexs[i] endl;}cout endl;for (size_t i 0; i _tables.size(); i){cout _vertexs[i] [ i ]-;Edge* cur _tables[i];while (cur){cout [ _vertexs[cur-_dsti] : cur-_dsti : cur-_w ]-;cur cur-_next;}cout nullptr endl;}}private:vectorV _vertexs; //顶点集合mapV, int _IndexMap; //顶点与下标映射vectorEdge* _tables; //邻接表(哈希桶)
};接下来图的遍历最小生成树最短路径我们都以邻接矩阵构的图去实现。
3. 图的遍历
给定一个图G和其中任意一个顶点v0从v0出发沿着图中各边访问图中的所有顶点且每个顶点仅被遍历一次。遍历即对顶点进行某种操作的意思。
3.1 图的广度优先遍历
有树的基础就知道广度优先遍历必然要借助队列来实现。广度优先遍历就是以某个点为起点当这个顶点出队列就把和这个顶点的邻接顶点都入队列然后一层一层往外走。但是要注意的是已经入过队列的顶点下一次不能在入队列否则就会死循环因此还要来一个标记bool类型数组。当一个顶点入队列后就标记一下。 void BFS(const V src)
{size_t srci GetVertexindex(src);size_t n _vertexs.size();//队列和标记数组queueint q;vectorbool vis(n, false);q.push(srci);vis[srci] true;while (!q.empty()){size_t front q.front();q.pop();cout front : _vertexs[front] endl;//把和front顶点的临界顶点入队列for (size_t i 0; i n; i){if (_matrix[front][i] ! MAX_W !vis[i]){q.push(i);vis[i] true;}}}
}void TestBDFS()
{string a[] { 张三, 李四, 王五, 赵六, 周七 };Graphstring, int g1(a, sizeof(a) / sizeof(string));g1.AddEdge(张三, 李四, 100);g1.AddEdge(张三, 王五, 200);g1.AddEdge(王五, 赵六, 30);g1.AddEdge(王五, 周七, 30);g1.Print();g1.BFS(张三);//g1.DFS(张三);
}接下来看一道题图的BFS应用题 举一个例子告诉我们一度好友、二度好友。。。是什么样的让我们找到小点的六度好友。这就是一个典型的图BFS应用。回想一下刚才我们的BFS顶点出队列是怎么出的是一个一个出的。对于这道题我们出队列的就要求一层一层出。那怎么一层一层出呢很简单出队列之前计算一下当前队列内元素的个数。每次出队列内元素个数次。
void BFS(const V src)
{size_t srci GetVertexindex(src);size_t n _vertexs.size();queueint q;vectorbool vis(n, false);q.push(srci);vis[srci] true;while (!q.empty()){//出队列之前计算队列内元素个数一层一层出size_t k q.size();while (k--){size_t front q.front();q.pop();cout front : _vertexs[front] endl;for (size_t i 0; i n; i){if (_matrix[front][i] ! MAX_W !vis[i]){q.push(i);vis[i] true;}}}}
}3.2 图的深度优先遍历
图的深度优先遍历和树的前序遍历一样。先往深走当走到不能走的就回溯换条路走最终直到所有顶点遍历完然后返回。因此我们用递归来实现这里我们还是需要一个标记bool类型数组已经访问过的不能在访问否则就会死递归。 void _DFS(size_t srci, const size_t n, vectorbool vis)
{cout srci : _vertexs[srci] endl;vis[srci] true;//找一个srci相邻的且没有被访问过的顶点,去往深度遍历for (size_t i 0; i n; i){if (_matrix[srci][i] ! MAX_W !vis[i]){_DFS(i, n, vis);}}
}void DFS(const V src)
{size_t srci GetVertexindex(src);size_t n _vertexs.size();vectorbool vis(n, false);_DFS(srci, n, vis);
}其实这里还有一个遗漏的问题如果无向图是一个连通图或者有向图是一个强连通图一次BFS和DFS就可以把所有顶点遍历一遍。但是如果图不是连通的。那以某个点为起点就没有办法一次BFS或者DSF把所有顶点遍历一遍那如何把图中所有顶点都访问到呢 其实很简单不是有标记数组吗。把标记数组在遍历一遍如果还有顶点没有被遍历到那就以这个顶点在做一次BFS或DFS。
4. 最小生成树
首先生成树对应的一定是连通图。连通图中找生成树。
连通图(连通图是针对无向图来说的)在无向图中若从顶点v1到顶点v2有路径则称顶点v1与顶点v2是连通的。如果图中任意一对顶点都是连通的则称此图为连通图。
生成树一个连通图的最小连通子图称作该图的生成树。有n个顶点的连通图的生成树有n个顶点和n-1条边。(最少的边连通起来)
最小生成树构成生成树的边的权值加起来是最小的。最小的成本让n个顶点连通
连通图中的每一棵生成树都是原图的一个极大无环子图即从其中删去任何一条边生成树就不在连通反之在其中引入任何一条新边都会形成一条回路。
若连通图由n个顶点组成则其生成树必含n个顶点和n-1条边。因此构造最小生成树的准则有三条
只能使用图中的权值最小的边来构造最小生成树只能使用恰好n-1条边来连接图中的n个顶点选用的n-1条边不能构成回路
构造最小生成树的方法Kruskal算法和Prim算法。这两个算法都采用了逐步求解的贪心策略。
贪心算法是指在问题求解时总是做出当前看起来最好的选择。也就是说贪心算法做出的不是整体
最优的的选择而是某种意义上的局部最优解。贪心算法不是对所有的问题都能得到整体最优解。
最小生成树不唯一但是权值是唯一的。
4.1 Kruskal算法
任给一个有n个顶点的连通网络N{V,E}
首先构造一个由这n个顶点组成、不含任何边的图G{V,NULL}其中每个顶点自成一个连通分量
其次不断从E中取出权值最小的一条边(若有多条任取其一)若该边的两个顶点来自不同的连通分量则将此边加入到G中。如此重复直到所有顶点在同一个连通分量上为止。
核心每次迭代时选出一条具有最小权值且两端点不在同一连通分量上的边加入生成树。
其实上面说了这么多Kruskal算法核心思想就是每次都从边中选权值最小的边(全局选最小)。
那怎么去选最小的边呢可以把所有的边拿出来排序。但是这不是好方法。更好的方法就是用优先级队列。建一个小堆。每次拿堆顶元素然后pop堆顶元素再拿次小的边。
但是这里还有一个问题可能选的边会造成回路
比如选择 i - g 权值为6的这条边构成了回路
如何判断选择的边构成了回路呢 使用并查集 - 判环
刚开始每一个顶点都是一个独立的集合选边的时候判断一下构成这个边的两个顶点是否是一个集合如果不是一个集合就可以选这个边。然后把对应的两个顶点合并成一个集合。 struct Edge
{size_t _srci;size_t _dsti;W _w;Edge(size_t srci, size_t dsti, W w):_srci(srci),_dsti(dsti),_w(w){}bool operator(const Edge e) const{return _w e._w;}
};//把最小生成树权值和返回去
W Kruskal(Self minTree)
{size_t n _vertexs.size();//最小生成树是连通图的一个子图,信息是一样的先初始化minTree._vertexs _vertexs;minTree._IndexMap _IndexMap;minTree._matrix.resize(n);for (size_t i 0; i n; i){minTree._matrix[i].resize(n, MAX_W);}//建小堆,因为Edge是自定义类型,库中的greater不支持自定义类型比较,所以写一个对应的仿函数priority_queueEdge, vectorEdge, greaterEdge heap;//并查集UnionFindSet ufs(n);//将所有边入堆for (size_t i 0; i n; i){for (size_t j 0; j n; j){//无向图的邻接矩阵是一个对称矩阵//因此只用存矩阵上半部分或者下半部分就行了if (i j _matrix[i][j] ! MAX_W){heap.push(Edge(i, j, _matrix[i][j]));}}}//选出n-1条边size_t sz 0;W total W();while (!heap.empty()){Edge minedge heap.top();heap.pop();//构成边的两个顶点不在一个集合,说明不构成环,可以选if (!ufs.IsSet(minedge._srci, minedge._dsti)){//可以打印一下看选了那条边cout _vertexs[minedge._srci] - _vertexs[minedge._dsti] : minedge._w endl;minTree._AddEdge(minedge._srci, minedge._dsti, minedge._w);ufs.Union(minedge._srci, minedge._dsti);sz;total minedge._w;}else{cout 构成环;cout _vertexs[minedge._srci] - _vertexs[minedge._dsti] : minedge._w endl;}}if (sz n - 1){return total;}else{return -1;}
}void TestGraphMinTree()
{const char* str abcdefghi;Graphchar, int g(str, strlen(str));g.AddEdge(a, b, 4);g.AddEdge(a, h, 8);//g.AddEdge(a, h, 9);g.AddEdge(b, c, 8);g.AddEdge(b, h, 11);g.AddEdge(c, i, 2);g.AddEdge(c, f, 4);g.AddEdge(c, d, 7);g.AddEdge(d, f, 14);g.AddEdge(d, e, 9);g.AddEdge(e, f, 10);g.AddEdge(f, g, 2);g.AddEdge(g, h, 1);g.AddEdge(g, i, 6);g.AddEdge(h, i, 7);Graphchar, int kminTree;cout Kruskal: g.Kruskal(kminTree) endl;kminTree.Print();//Graphchar, int pminTree;//cout Prim: g.Prim(pminTree, a) endl;//pminTree.Print();//cout endl;//for (size_t i 0; i strlen(str); i)//{// cout Prim: g.Prim(pminTree, str[i]) endl;//}
}4.2 Prim算法
Prim算法也是用的贪心但是它跟Kruskal算法不一样Kruskal的核心思想是每次都在全局选最小Prim是给一个起点然后从这个起点开始去找最小边局部选最小。它选边是先把所有顶点归成两个集合一个集合是已经被选择的顶点已经加入到最小生成树的顶点剩下顶点是一个集合。它是在两个集合之间去选最小边。每次都从两个集合各选一个顶点构成的最小边。 为什么会这样选边的呢也就说这个地方贪心不是一个全局的贪心是一个局部的贪心。以某个点为起点去找周围最小的边。而之前是全局贪心。那局部贪心的优势是什么
它的优势就是选边不会构成环。
它是在两个集合之间去选最小边。每次都从两个集合各选一个顶点构成的最小边。天然避环。
那怎么去区分已经加入到最小生成树的顶点集合和剩余顶点的集合呢 我们可以搞两个vector一个X集合一个Y集合。 X表示已经加入最小生成树顶点的结合 Y表示剩余顶点的集合
刚开始所以顶点都没加入到最小生成树也就是都在Y集合因此Y集合的所有顶点都标记成true如果某个顶点加入到最小生成树就把对应顶点从Y中变成false而在X中变为true。
那如何从X-Y集合连接的边里面选出最小的边 搞一个优先级队列小堆把已经加入最小生成树顶点相连的边加入到队列中这样去选最小边可不可以其实不行 加入h到X集合的时候 a - h 就已经在一个集合了这条边就不该在这个队列里面了但是你又不能控制把它删除。
所以直接用优先级队列也不太好。
第二种方式就是每次去遍历因为我们这里是矩阵很方便每次去遍历去找X集合的顶点与Y集合的顶点构成最小的边。但是时间复杂度挺高的。
其实我们还是用优先级队列不过选边的时候要判一下环如果选出来最小的边的两个顶点在一个集合是构成环的不能选
W Prim(Self minTree, const V src)
{size_t n _vertexs.size();minTree._vertexs _vertexs;minTree._IndexMap _IndexMap;minTree._matrix.resize(n);for (size_t i 0; i n; i)minTree._matrix[i].resize(n, MAX_W);//从X-Y集合中连接的边里面选出最小的边vectorbool X(n,false);vectorbool Y(n, true);priority_queueEdge, vectorEdge, greaterEdge heap;size_t srci GetVertexindex(src);//先把srci连接的边添加到队列中for (size_t i 0; i n; i){if(_matrix[srci][i] ! MAX_W)heap.push(Edge(srci, i, _matrix[srci][i]));}X[srci] true;Y[srci] false;size_t sz 0;W total W();while (!heap.empty()){Edge minedge heap.top();heap.pop();if (!X[minedge._dsti])//每次从两个集合中各选一个顶点构成的最小边,防止成环{cout _vertexs[minedge._srci] - _vertexs[minedge._dsti] : minedge._w endl;minTree._AddEdge(minedge._srci, minedge._dsti, minedge._w);sz;total minedge._w;X[minedge._dsti] true;Y[minedge._dsti] false;for (size_t i 0; i n; i){//已经选过的最小边,不要重复添加if (_matrix[minedge._dsti][i] ! MAX_W Y[i])heap.push(Edge(minedge._dsti, i, _matrix[minedge._dsti][i]));}}else{cout 构成环;cout _vertexs[minedge._srci] - _vertexs[minedge._dsti] : minedge._w endl;}}if (sz n - 1){return total;}else{return -1;}}5. 最短路径
最短路径问题从在带权有向图G中的某一顶点出发找出一条通往另一顶点的最短路径最短也就是沿路径各边的权值总和达到最小。
一般而言 最小生成树 - 无向图 最短路径 - 有向图
5.1 单源最短路径–Dijkstra算法
单源最短路径一个起点到其他所有点最短路径。
单源最短路径问题给定一个图G ( V E ) G(VE)G(VE)求源结点s ∈ V s∈Vs∈V到图中每个结点v ∈ V v∈Vv∈V的最短路径。Dijkstra算法就适用于解决带权重的有向图上的单源最短路径问题同时算法要求图中所有边的权重非负。一般在求解最短路径的时候都是已知一个起点和一个终点所以使用Dijkstra算法求解过后也就得到了所需起点到终点的最短路径。
针对一个带权有向图G将所有结点分为两组S和QS是已经确定最短路径的结点集合在初始时为空初始时就可以将源节点s放入毕竟源节点到自己的代价是0Q 为其余未确定最短路径的结点集合每次从Q 中找出一个起点到该结点代价最小的结点u 将u 从Q 中移出并放入S 中对u 的每一个相邻结点v 进行松弛操作。松弛即对每一个相邻结点v 判断源节点s到结点u 的代价与u 到v 的代价之和是否比原来s 到v 的代价更小若代价比原来小则要将s 到v 的代价更新为s 到u 与u 到v 的代价之和否则维持原样。如此一直循环直至集合Q 为空即所有节点都已经查找过一遍并确定了最短路径至于一些起点到达不了的结点在算法循环后其代价仍为初始设定的值不发生变化。Dijkstra算法每次都是选择V-S中最小的路径节点来进行更新并加入S中所以该算法使用的是贪心策略。
Dijkstra算法存在的问题是不支持图中带负权路径如果带有负权路径则可能会找不到一些路径的最短路径
比如这里是以s为源点去找和其他点的最短路径。 刚开始S集合里面只有起点ss到其他起点初始都是∞指的是还没有最短路径。s是自己到自己可以初始为0初始选择a这个起点以这个点去做松弛操作去遍历与s相连的顶点去更新s到其他顶点的最短路径然后从未被加入到S里面的点里面去选一个从源点到这些顶点的最短路径。以这个顶点开始在去做松弛操作。
Dijkstra算法贪心策略每次去选从起点-还没加入到最短路径的顶点中去选最短路径那个顶点去更新其连接的路径(做松弛操作)
用最小的边在去更新其他边也是相对很小。
如何存储起点到其他顶点最短路径的权值和存储最短路径呢
它这里用的是抽象表示用了两个数组本来是二维的。但是压缩成了一维。 每个顶点都确定过一个下标。根据下标搞了一个数组把起点到其他顶点的最短路径的权值存储到这个dist数组里。在根据下标搞一个Ppath记录起点到其他顶点的路径数组里面存的是路径前一个顶点下标。 //顶点个数是 N, 时间复杂度 O(N^2) 空间复杂度 O(N)
void Dijkstra(const V src, vectorW dist, vectorint Ppath)
{size_t n _vertexs.size();size_t srci GetVertexindex(src);//dist,记录srci-其他顶点最短路径权值数组dist.resize(n, MAX_W);//Ppath 记录srci-其他顶点最短路径父顶点数组Ppath.resize(n, -1);//初始化dist[srci] 0;Ppath[srci] srci;//已经确定最短路径的顶点集合vectorbool S(n, false);// n个顶点更新N次for (size_t i 0; i n; i){//每次去选从起点-还未加入到最短路径的顶点中去选最短路径的那个顶点,去更新其连接的路径(松弛操作)W min MAX_W;size_t u -1;for (size_t j 0; j n; j){if (!S[j] dist[j] min){u j;min dist[j];}}S[u] true;//选到的顶点加入到最短路径for (size_t v 0; v n; v){//松弛操作,已经加入到最短路径的顶点路径已经是最小不用更新,其他顶点如果 s - u u - v s - v 更新if (!S[v] _matrix[u][v] ! MAX_W dist[u] _matrix[u][v] dist[v]){dist[v] dist[u] _matrix[u][v];Ppath[v] u;}}}
}打印最短路径各个顶点的最短路径是倒着存的存的是前一个顶点的下标。我们把路径算出来之后还要逆置一下才能把路径找到。 void PrintShortPath(const V src,const vectorW dist,const vectorint Ppath)
{size_t srci GetVertexindex(src);size_t n _vertexs.size();for (size_t i 0; i n; i){if (i ! srci)//自己到自己不算{//找出i顶点的路径和并查集类似vectorint path;int parent i;while (parent ! srci){path.push_back(parent);parent Ppath[parent];//前一个顶点的下标}path.push_back(srci);reverse(path.begin(), path.end());for (auto e : path){cout _vertexs[e] -;}cout 权值和 dist[i] endl;}}
}Dijkstra算法存在的问题是不支持图中带负权路径如果带有负权路径则可能会找不到一些路径的最短路径
可以看到 s - y 并不是最短路径。Dijkstra算法本身用了一个贪心如果对已加入到最小路径的顶点更新这个贪心就失效了。如果边的权值都是正的以其他边去更新已经加入最小路径的顶点就比之前更大没有必要更新但是有负数就不一样了贪心就失效了。 5.2 单源最短路径–Bellman-Ford算法
Dijkstra算法只能用来解决正权图的单源最短路径问题但有些题目会出现负权图。这时这个算法就不能帮助我们解决问题了而bellman—ford算法可以解决负权图的单源最短路径问题。它的优点是可以解决有负权边的单源最短路径问题而且可以用来判断是否有负权回路。它也有明显的缺点它的时间复杂度 O(N*E) (N是点数E是边数)普遍是要高于Dijkstra算法O(N²)的。像这里如果我们使用邻接矩阵实现那么遍历所有边的数量的时间复杂度就是O(N^3)这里也可以看出来Bellman-Ford就是一种暴力求解更新。 s - { j } 其他顶点的集合要么是直接相连要么是找中间边边去更新Dijkstra是去找s-某个顶点特别短那就优先拿这条边去作为起始边去更新它是我到这个顶点边是最短的那我从这个顶点到其他顶点也是最短的。Bellman-Ford是去找终止边暴力去更新。
Dijkstra 最小起始边贪心 Bellman-Ford 终止边暴力
终止边就是以 i - j 去进行更新i - j 就是图中所有边
s - { j } 其他顶点要么直接相连要么 s - i i - j这个时候仅需要探测s - i 是通的 i - j 也是通的 它们加起来比 s - j 更小就松弛更新一下。i - j 代表图中所有边拿图中所有边去暴力更新一遍。
Bellman-Ford算法借助终止边i - j 图中所有边暴力更新起点 - { j } 所有顶点。要么直接相连要么借助终止边。
但是拿所有边走一遍并不是说就一定能更新出来
void BellmanFord(const V src, vectorW dist, vectorint Ppath)
{size_t srci GetVertexindex(src);size_t n _vertexs.size();// vectorW dist, 记录srci - 其他顶点最短路径权值数组dist.resize(n, MAX_W);// vectorint pPath 记录srci - 其他顶点最短路径父顶点数组Ppath.resize(n, -1);// 先更新srci-srci为缺省值dist[srci] W();Ppath[srci] srci;// i - j 更新一轮// 借助终止边i-j(图中所有顶点之间的边),更新srci到所有顶点的最小路径(做松弛操作)for (size_t i 0; i n; i){for (size_t j 0; j n; j){//srci - i i - j srci - j if (_matrix[i][j] ! MAX_W dist[i] _matrix[i][j] dist[j]){dist[j] dist[i] _matrix[i][j];Ppath[j] i;}}}}最短路径似乎更新出来了 但是为什么s-z的权值不对呢 接下来画图分析一下
第一次更新是 s-s s-y因为更新规则是 dist[i] _matrix[i][j] dist[j]我们初始的时候是把 dist[srci] W()给了初始值。先先更新与s直连的边。 s-x x-t这一句的更新就导致了问题。4 -2 6 s-t 最短路径更新成2t的前一个顶点变成x。也就是从s到t的路径变成了 s - y - x - t s - t 最短路径更新成2。
但是注意到 s - t 的最短路径更新到2 而从 s - z 要经过ts - z 路径因为我们更新了 s - t 的路径而变成了 s - y - x - t - z但是s - z 最短路径可没有更新依旧是上次 s -(直连) t - z的最短路径2。所以 s - t 有了路径更新但是 s - t 最短路径没有更新。权值和路径对不上。 只要你更新出了一条更短路径可能就会影响其他路径。 如何解决
s - z 在更新一次就变成了 s - y - x - t - z 的权值 -2了。
在更新一次就修正了但是新更新路径又可能会影响其他路径所以还要继续更新最多更新n轮极端情况下最多用n条边去更新某一个顶点。
这里还有一个优化可能某一轮就不会在更新了也不会影响其他路径。因此可以增加一个标记位某一轮没有更新就结束更新。
//时间复杂度 O(N^3), 空间复杂度 O(N)
void BellmanFord(const V src, vectorW dist, vectorint Ppath)
{size_t srci GetVertexindex(src);size_t n _vertexs.size();// vectorW dist, 记录srci - 其他顶点最短路径权值数组dist.resize(n, MAX_W);// vectorint pPath 记录srci - 其他顶点最短路径父顶点数组Ppath.resize(n, -1);// 先更新srci-srci为缺省值dist[srci] W();Ppath[srci] srci;// 总体最多更新n轮for (size_t k 0; k n; k){//优化bool update false;// i - j 更新一轮// 借助终止边i-j(图中所有顶点之间的边),更新srci到所有顶点的最小路径(做松弛操作)for (size_t i 0; i n; i){for (size_t j 0; j n; j){//srci - i i - j srci - j if (_matrix[i][j] ! MAX_W dist[i] _matrix[i][j] dist[j]){//只要更新出一条更短路径,可能会影响其他路径,在更新一次就修正了//但是新更新的路径又可能会影响其他路径,所以还要继续更新,最多更新n轮dist[j] dist[i] _matrix[i][j];Ppath[j] i;update true;}}}// 如果这个轮次中没有更新出更短路径那么后续轮次就不需要再走了if (update false)break;}
}还有一个优化思路第一个轮次所有边都会参与更新但是第二个轮次并一定所有边都参与更新只有那些第一个轮次更新的最短路径的会影响其他路径的然后第二轮去更新就好了。具体可以搞一个队列优化。
第一轮更新所有边入队列 后面的轮次更新出最短路径的边入队列 Bellman-Ford算法它的优点是可以解决有负权边的单源最短路径问题但是解决不了带负权回路的的单源最短路径问题。因此可以用来判断是否有负权回路。
s-s 每次都会更新。 bool BellmanFord(const V src, vectorW dist, vectorint Ppath)
{size_t srci GetVertexindex(src);size_t n _vertexs.size();// vectorW dist, 记录srci - 其他顶点最短路径权值数组dist.resize(n, MAX_W);// vectorint pPath 记录srci - 其他顶点最短路径父顶点数组Ppath.resize(n, -1);// 先更新srci-srci为缺省值dist[srci] W();Ppath[srci] srci;// 总体最多更新n轮for (size_t k 0; k n; k){//优化bool update false;// i - j 更新一轮// 借助终止边i-j(图中所有顶点之间的边),更新srci到所有顶点的最小路径(做松弛操作)for (size_t i 0; i n; i){for (size_t j 0; j n; j){//srci - i i - j srci - j if (_matrix[i][j] ! MAX_W dist[i] _matrix[i][j] dist[j]){//只要更新出一条更短路径,可能会影响其他路径,在更新一次就修正了//但是新更新的路径又可能会影响其他路径,所以还要继续更新,最多更新n轮dist[j] dist[i] _matrix[i][j];Ppath[j] i;update true;}}}// 如果这个轮次中没有更新出更短路径那么后续轮次就不需要再走了if (update false)break;}//更新n轮后还能更新就是带负权回路for (size_t i 0; i n; i){for (size_t j 0; j n; j){//srci - i i - j srci - j if (_matrix[i][j] ! MAX_W dist[i] _matrix[i][j] dist[j]){return false;}}}return true;
}5.3 多源最短路径–Floyd-Warshall算法
Floyd-Warshall算法是解决图中任意两点间的最短路径的一种算法也可以解决带负权路径。
Dijkstra算法和BellmanFord算法也可以以所有点为起点也可以求出任意两点之间的最短距离。但是Dijkstra算法不能带负权BellmanFord算法效率低一点。
Floyd-Warshall算法真正优势在于同时更新多源既然要记录多源的权值和数组那就意味着一维已经不行了那这个时候就要搞成一个二维的。二维就能记录任意两个点。它和一维的区别就是以前算 srci - i i - j 要去矩阵里面取现在就去dist这个矩阵里面去取。 Floyd算法考虑的是一条最短路径的中间节点即简单路径p{v1,v2,…,vn}上除v1和vn的任意节点。
任意两点之间要么直接相连要么最多经过其它点n - 2个顶点。
Dijkstra算法是用最小起始边来算 BellmanFord算法是用终止边来算 Floyd-Warshall算法使用中间点来算
设k是p的一个中间节点那么从i到j的最短路径p就被分成i到k和k到j的两段最短路径p1p2。p1是从i到k且中间节点属于{12…k-1}取得的一条最短路径。p2是从k到j且中间节点属于{12…k-1}取得的一条最短路径。 Floyd-Warshall算法本质还是用了动态规划。距离都在dsti里面去取i - j 要么直接相连要么经过 1…k)集合中的顶点(n-2个顶点) i - kk - j。取两种情况中的最小值为最短路径。
具体做法如下
先将直接相连的 i - j 的 dist Ppath初始化最短路径更新i - 中间点 - jk作为中间点尝试更新 i - j 的路径 如果 i - kk - j i - j 更新 dist[i][j]和Ppath[i][j]注意如果是i - kk - j i - jPpath[i][j] 更新要注意Ppath要的是跟 j 相连的上一个邻接顶点如果 k 与 j 直接相连 Ppath[k][j]存的就是 k 如果 k - j 没有直接相连k - … - x - jPpath[k][j] 存的就是 x。所以Ppath[i][j] Ppath[k][j] 而不是直接等于 k。
void FloydWarshall(vectorvectorW vvDist, vectorvectorint vvPpath)
{size_t n _vertexs.size();//初始化权值和路径矩阵vvDist.resize(n, vectorW(n, MAX_W));vvPpath.resize(n, vectorint(n, -1));//先将之间相连的 i-j 更新一下for (size_t i 0; i n; i){for (size_t j 0; j n; j){if (_matrix[i][j] ! MAX_W){vvDist[i][j] _matrix[i][j];vvPpath[i][j] i;}if (i j){vvDist[i][j] W();}}}// 最短路径的更新i- {其他顶点} -j// K严格来说最多是n-2个,但是不能循环n-2次,要循环n次,因为 i - j 一直在变,要把所有点作为中间点// abcdef a-f k这次是a或者f 对于a-f也没有影响, a-a a-f, a-f f-f,for (size_t k 0; k n; k){for (size_t i 0; i n; i){for (size_t j 0; j n; j){// k 作为的中间点尝试去更新 i-j 的路径if (vvDist[i][k] ! MAX_W vvDist[k][j] ! MAX_W vvDist[i][k] vvDist[k][j] vvDist[i][j]){vvDist[i][j] vvDist[i][k] vvDist[k][j];// 找跟j相连的上一个邻接顶点// 如果k-j 直接相连上一个点就kvvpPath[k][j]存就是k// 如果k-j 没有直接相连k-...-x-jvvpPath[k][j]存就是xvvPpath[i][j] vvPpath[k][j];}}// 打印权值和路径矩阵观察数据for (size_t i 0; i n; i){for (size_t j 0; j n; j){if (vvDist[i][j] MAX_W){printf(%3c, *);}else{printf(%3d, vvDist[i][j]);}}cout endl;}cout endl;for (size_t i 0; i n; i){for (size_t j 0; j n; j){printf(%3d, vvPpath[i][j]);}cout endl;}cout endl;}}
}void TestFloydWarShall()
{const char* str 12345;Graphchar, int, INT_MAX, true g(str, strlen(str));g.AddEdge(1, 2, 3);g.AddEdge(1, 3, 8);g.AddEdge(1, 5, -4);g.AddEdge(2, 4, 1);g.AddEdge(2, 5, 7);g.AddEdge(3, 2, 4);g.AddEdge(4, 1, 2);g.AddEdge(4, 3, -5);g.AddEdge(5, 4, 6);vectorvectorint vvDist;vectorvectorint vvParentPath;g.FloydWarshall(vvDist, vvParentPath);//打印任意两点之间的最短路径for (size_t i 0; i strlen(str); i){g.PrintShortPath(str[i], vvDist[i], vvParentPath[i]);cout endl;}
}
