海诚网站建设,网页浏览器入口,怎样做带音乐的表白网站,中国营销策划网目录 一. 图的基本概念
二. 图的存储结构
2.1 邻接矩阵
2.2 邻接表
三. 图的遍历
3.1 广度优先遍历
3.2 深度优先遍历
四. 最小生成树
4.1 最小生成树获取策略
4.2 Kruskal算法
4.3 Prim算法
五. 最短路径问题
5.1 Dijkstra算法
5.2 Bellman-Ford算法
5.3 Floyd-…目录 一. 图的基本概念
二. 图的存储结构
2.1 邻接矩阵
2.2 邻接表
三. 图的遍历
3.1 广度优先遍历
3.2 深度优先遍历
四. 最小生成树
4.1 最小生成树获取策略
4.2 Kruskal算法
4.3 Prim算法
五. 最短路径问题
5.1 Dijkstra算法
5.2 Bellman-Ford算法
5.3 Floyd-Warshall算法
六. 总结 一. 图的基本概念
图是一种由顶点集合以及顶点与顶点之间关系组成的数据结构记为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表示x连接到y有方向。
如图1.1所示A、B、C、D称之为顶点连接顶点之间的“线”称其为边边的箭头表示连接方向图1.1左边的A-B连接线表示A连接到B有方向记为A,B右边图结构中A-B表示A和B相连接没有方向记为(A,B)。 图1.1 有向图个无向图 有向图与无向图有向图中的顶点和顶点之间的连接具有方向性如图1.1中左侧图结构所示可以说顶点B连接到顶点D但不可以说顶点D连接到顶点B这是有向图结构。图1.1右侧的图结构是无向图A和B之间有边相连那我们可以认为A能够连接到BB也能够连接到A。
完全图在无向图中假设顶点数量为N那么有N*(N-1)/2,条边即任意两个顶点之间都有边相连那么就称其为无向完全图。在有向图中任意两个顶点之间都有两条指向相反的连接线即有N个顶点的有向图有N*(N-1)条边称这样的图结构为有向完全图。 图1.2 有向完全图和无向完全图 邻接顶点在无向图中如果(A,B)是一条边那么我们称顶点A和顶点B邻接在有向图中如果A,B是一条边则表示A连接到B称顶点A邻接到顶点B顶点B邻接自顶点A。
顶点的度顶点的度指的是与顶点相连的边的条数记为deg(V)表示顶点V的度。对于有向图顶点V的度等于入度和出度之和顶点V的出度指的是以V为起点的边的条数记为outdev(V)顶点V的入度指以V为终点的边的条数记为indev(V)那么deg(V) outdev(V) indev(V)。对于无向图顶点的度与其出度和入度都相等即deg(V) outdev(V) indev(V)。
路径对于图G { V, E }假设从顶点vi出发经过一定的路径可以到顶点vj那么从顶点vi到顶点vj所经过的顶点就称为顶点vi到顶点vj的路径。
路径长度对于不带权的图路径长度就是从源顶点到目标顶点所经过的边的条数对于带权值的图从源顶点到目标顶点的路径长度就是每条边的权值之和。如图1.3所示所谓权值就是边的附属信息。 图1.3 带权值的边 简单路径与回路假设顶点v1和vm相连路径v1, v2, ... , vm没有重复的顶点那么称v1, v2, ... , vm为简单路径如果v1,v2, ..., v1路径从起始点开始又回到了起始点那么就是回路。 图1.4 简单路径与回路 子图对于图G { V, E}有图G1 { V1, E1 }且有V1为V的子集E1为E的子集那么称G1为G的子图。 图1.5 子图 连通图在无向图中如果顶点vi与顶点vj之间能够通过一些边连接起来那么称顶点vi与顶点vj是连通的如果无向图中任意一对顶点都是连通的那么称这种图结构为连通图。
强连通图在有向图中如果对于任意一对顶点vi和vj既有从vi到vj的路径也有从vj到vi的路径那么这种图结构称为强连接图。
最小生成树对于连通图能够将每个顶点连接在一起的最小连通子图称为最小生成树对于有N个顶点的连通图其最小生成树应该有N-1条边。 图1.6 连通图和强联通图 二. 图的存储结构
图的存储结构有两种邻接矩阵和邻接表。
2.1 邻接矩阵
所谓邻接矩阵就是一个二维数组。假设使用一维数组存储图中的每一个顶点每一个顶点都有一个与之对应的在数组中的下标将这个一维数组拓展到二维数组就可以表示顶点和顶点之间的连接关系。假设邻接矩阵为M那么M[i][j]就表示下标i对应的顶点和下标j对应的顶点的连接关系。
对于不带权值的图如果矩阵中两个顶点相连接即vi与vj相连那么邻接矩阵中的M[i][j]1对于带权值的图邻接矩阵中的值表示每条边的权重如果两条边不相连那么对应的邻接矩阵中的值就记为无穷大。对于无向图的邻接矩阵是关于主对角线对称的矩阵。
邻接矩阵的优缺点邻接矩阵能够快速查找两个顶点是否直接相连但是如果边较少的时候邻接矩阵中会有大量的浪费空间且使用邻接矩阵不容易求得两个顶点之间的路径。 图2.1 邻接矩阵存储图结构 代码2.1为使用邻接矩阵进行存储的图结构的模板类代码实现。该类为模板类模板参数有四个分别为V表示图的顶点数据类型、W表示权值数据类型、MAX_W表示两顶点不相连时默认的权重Direction表示该图是有向图还是无向图。
成员变量有三个_vertex为记录顶点数据的一维数组_valIndexMap为顶点数据与下标的映射哈希表_edges为邻接矩阵。
先实现构造函数和顶点边添加函数在构造函数中应当将数组中给出的全部数据插入到_vertex中去并且构造数据值和_vertex数组下标的映射关系。在边添加函数_AddEdges中要传三个参数分别为源顶点、目标顶点和权值获取源顶点和目标顶点的下标在临界矩阵中建立源顶点到目标顶点的连接如果是无向图还要添加目标顶点到源顶点的连接。
为了方便观察引入Print函数用于向屏幕打印邻接矩阵以检查结果的正确性。
代码2.1邻接矩阵存储图
#include iostream
#include vector
#include unordered_map
#include cassertnamespace Matrix
{templateclass V, class W, W MAX_W INT_MAX, bool Direction falseclass Graph{public:// 构造函数传递一维数组和数据个数Graph(const V* arr, size_t size){for (size_t i 0; i size; i){_vertex.push_back(arr[i]);_valIndexMap[arr[i]] i;}// 为邻接矩阵申请空间并初始化_edges.resize(size, std::vectorW(size, MAX_W));}// 顶点下标获取函数size_t GetIndex(const V val){auto pos _valIndexMap.find(val);if (pos ! _valIndexMap.end()){return pos-second;}else{assert(false);return -1;}}// 边添加函数void AddEdge(const V src, const V dst, const W w){// 获取源顶点和目标顶点对应的一维数组下标size_t srci GetIndex(src);size_t dsti GetIndex(dst);// 建立srci-dsti的连接关系_edges[srci][dsti] w;// 如果是无向图还需要建立dst-src的连接关系if (Direction false){_edges[dsti][srci] w;}}// 邻接矩阵打印函数void Print(){size_t n _vertex.size();for (size_t i 0; i n; i){for (size_t j 0; j n; j){if (_edges[i][j] MAX_W) std::cout * ;else std::cout _edges[i][j] ;}std::cout std::endl;}}private:std::vectorV _vertex; // 存储顶点值的一维数组std::unordered_mapV, size_t _valIndexMap; // 顶点值与其在数组下标中的映射关系std::vectorstd::vectorW _edges; // 邻接矩阵};
}
2.2 邻接表
邻接表就是对图中每一个顶点都分配一个链表链表中的每个顶点都表示一个与该顶点直接相连的顶点如图2.2就是邻接表存储存储图的示意。对于无向图只需要一张邻接表就能够清楚表示图结构。对于有向图可以使用一张出边表和一张入边表出边表记录以每个顶点为起始点的边连接到的顶点入边表记录以每个顶点为终点的边的起始顶点在实际应用中使用一张出边表也能清晰表达有向图的结构因此入边表一般省略。
使用邻接表的优缺点邻接表适用于存储稀疏图适用于查找一个顶点连接出去的边但是无法像邻接矩阵那样以O(1)的时间复杂度判断两个顶点是否直接相连。 图2.1 邻接表存储图 代码2.2对邻接表存储的图结构进行了初步的实现定义struct Edge结构体来存储边struct Edge包含三个成员目标顶点下标_dsti、权值_w、下一个顶点_next。模板类class Graph的成员变量与邻接矩阵版的基本相同区别就在于使用邻接表表示顶点间的连接关系添加边函数AddEdge将新的连接边new出来的struct Edge对象头插到对应单链表处即可。
代码2.2采用邻接表存储图
#include iostream
#include vector
#include unordered_map
#include cassertnamespace LinkTable
{templateclass Wstruct Edge{size_t _dsti; // 目标顶点在数组中的下标W _w; // 权重struct Edge* _next; // 单链表下一个顶点// 构造函数Edge(size_t dsti, const W w): _dsti(dsti), _w(w), _next(nullptr){ }};templateclass V, class W, W MAX_W INT_MAX, bool Direction falseclass Graph{typedef EdgeW Edge;public:// 构造函数Graph(const V* arr, size_t size){// 将顶点插入一维数组并建立顶点与下标的映射for (size_t i 0; i size; i){_vertex.emplace_back(arr[i]);_valIndexMap[arr[i]] i;}// 初始化邻接表_edges.resize(size, nullptr);}// 顶点下标获取函数size_t GetIndex(const V val){auto pos _valIndexMap.find(val);if (pos ! _valIndexMap.end()){return pos-second;}else{assert(false);return -1;}}// 添加边函数void AddEdge(const V src, const V dst, const W w){// 获取源节点和目标节点的下标size_t srci GetIndex(src);size_t dsti GetIndex(dst);// 构建srci-dsti的连接关系Edge* edge1 new Edge(dsti, w);edge1-_next _edges[srci];_edges[srci] edge1;// 如果是无向图构建dsti-srci的连接关系if (Direction false){Edge* edge2 new Edge(srci, w);edge2-_next _edges[dsti];_edges[dsti] edge2;}}// 打印邻接表函数void Print(){size_t n _edges.size();for (size_t i 0; i n; i){std::cout _vertex[i] :;Edge* cur _edges[i];while (cur){std::cout [ _vertex[cur-_dsti] : cur-_w ] -;cur cur-_next;}std::cout nullptr std::endl;}}private:std::vectorV _vertex; // 存储顶点的一维数组std::unordered_mapV, size_t _valIndexMap; // 数据和下标的映射关系哈希表std::vectorEdge* _edges; // 邻接表表示的连接边};
}
三. 图的遍历
3.1 广度优先遍历
广度优先遍历我们可以理解为分层遍历依次遍历每一层的顶点数目。在具体实现中使用队列进行辅助先将起始顶点入队列从队头开始遍历将与队头直接相连且还未被遍历的顶点插入队尾每次插入一个顶点都要对这个顶点进行记录以避免重复遍历。图3.1为广度优先遍历的分层情况第0层遍历完成后遍历第1层之后是第2层、第3层以此类推。代码3.1在使用邻接矩阵存储的图结构中实现对图的广度优先遍历。 图3.1 图的广度优先遍历 代码3.1图的广度优先遍历
// 图的广度优先遍历src为遍历起点
void BFS(const V src)
{size_t srci GetIndex(src); // 起点下标size_t n _vertex.size(); // 顶点个数std::vectorbool visited(n, false); // 记录每个点是否被遍历是否已经加入到队列中std::queuesize_t q; // 队列记录顶点下标q.push(srci); // 源顶点先入队列visited[srci] true; // 记录源顶点已被加入队列size_t levelSize 1; // 每层节点个数size_t level 0;// 使用辅助队列开始逐层执行广度优先遍历算法while (!q.empty()){printf(第%u层, level);for (size_t i 0; i levelSize; i){size_t u q.front();q.pop();std::cout _vertex[u] ;// 检查u-v的连接情况// 如果u-v相连且v尚未被遍历那么v入队列for (size_t v 0; v n; v){if (_edges[u][v] ! MAX_W visited[v] false){visited[v] true;q.push(v);}}}std::cout std::endl;levelSize q.size();}
}
3.2 深度优先遍历
深度优先就是选定一个原点后就一直向下递归遍历直到无法递归的时候就回溯直到完成对于所有点的遍历通过vector数组记录每个点是否被遍历。 图3.2 图的深度优先遍历 代码3.2图的深度优先遍历算法
// 深度优先遍历算法子函数
// curi为当前遍历节点的下标visited为记录节点是否被遍历过的数组
void _DFS(size_t curi, std::vectorbool visited)
{visited[curi] true;std::cout _vertex[curi] std::endl;// 检查是否有curi-u的连接// 如果u还未被遍历那么就递归遍历执行深度优先算法for (size_t u 0; u _edges.size(); u){if (_edges[curi][u] ! MAX_W visited[u] false){_DFS(u, visited);}}
}// 深度优先遍历函数src为起始点
void DFS(const V src)
{size_t srci GetIndex(src); // 遍历源顶点下标size_t n _vertex.size(); // 顶点个数std::vectorbool visited(n, 0); // 记录每个节点是否被遍历过的数组_DFS(srci, visited);
}
四. 最小生成树
4.1 最小生成树获取策略
所谓最小生成树是对于无向连通图的概念即路径权值和最小的、连通的子图。这就要求最小生成树满以下条件
如果原图有N个顶点那么其最小生成树有N-1条边。最小生成树中的边不能构成回路。必须是满足前两个条件边权值和最小的生成树。
获取最小生成树的算法有Kruskal算法(克鲁斯卡尔算法)和Prim算法(普里姆算法)这两种算法都是采用“贪心”策略即寻找局部最优解即当前图中满足一定条件的权值最小的边。但是要注意Kruskal算法和Prim算法都是局部贪心算法能够取得局部最优解但是不一定获取的是全局最优解它们获取的结果只能说是非常接近于最小生成树而不一定就是最小生成树。
4.2 Kruskal算法
Kruskal算法的思想就是在整个图的所有边中筛选出权值最小的边同时在选边的过程中避免构成环等到筛选出N-1条边后就可以获取最小生成树。图4.1为Kruskal算法的选边过程其中红色加粗的线为被选择的边。
Kruskal算法核心每次都筛选权值最小的、且不构成回路的边加入生成树。 图4.1 Kruskal算法的选边过程 通过Kruskal算法获取最小生成树需要使用 小根堆 并查集 来辅助进行其中小根堆负责每次在所有尚未选取的边中筛选权值最小的边并查集用于避免生成回路环。需要定义struct Edge类来记录边的属性信息struct Edge的成员包括起始顶点下标srci、目标顶点下标dsti以及权重w重载 运算符用于比较权重大小。在Kruskal算法的代码中首先要将所有的边插入小根堆每次从堆顶拿出一条边使用并查集检查两个顶点是否会构成环属于同一个集合如果不会构成环那么就将这条边添加到生成树中去。之后将此时的srci和dsti归并到并查集的同一集合中去以避免成环然后选边计数器1进行权重累加。假设总共有N个顶点如果选出生成树有N-1条边说明成功获得了最小生成树返回每个边的权重之和否则就是获取最小生成树失败返回MAX_W。
代码4.1为Kruskal算法及其配套被调函数及自定义类型的实现其中Graph的其余不相关函数省略代码4.2为并查集的实现代码。
代码4.1Kruskal算法及其配套被调函数及自定义类型的实现
#include UnionFindSet.hpp
#include iostream
#include vector
#include queue
#include unordered_map
#include algorithm
#include cassertnamespace Matrix
{// 自定义类型 -- 顶点与顶点之间的边templateclass Wstruct Edge{size_t _srci; // 源顶点下标size_t _dsti; // 目标顶点下标W _w; // 权重// 构造函数Edge(size_t srci, size_t dsti, const W w): _srci(srci), _dsti(dsti), _w(w){ }// 大于比较运算符重载函数用于构建小根堆bool operator(const EdgeW w) const{return _w w._w;}};templateclass V, class W, W MAX_W INT_MAX, bool Direction falseclass Graph{typedef EdgeW Edge;typedef GraphV, W, MAX_W, Direction Self;public:// 强制生成默认构造函数Graph() default;// ....// 与Kruskal算法不相关的成员函数全部省略// 根据下标添加边的函数void _AddEdge(size_t srci, size_t dsti, const W w){_edges[srci][dsti] w;if (Direction false){_edges[dsti][srci] w;}}// Kruskal算法获取最小生成树// 返回值为最小生成树的权值和minTree为输出型参数用于获取最小生成树// 如果无法获取最小生成树那么就返回MAX_WW Kruskal(Self minTree){// 初始化minTree中的每个成员size_t n _vertex.size();minTree._vertex _vertex;minTree._valIndexMap _valIndexMap;minTree._edges.resize(n, std::vectorW(n, MAX_W));// 将所有边的信息源顶点、目标顶点、权值插入到小根堆中去std::priority_queueEdge, std::vectorEdge, std::greaterEdge minHeap;for (size_t i 0; i n; i){for (size_t j i 1; j n; j){if (_edges[i][j] ! MAX_W){Edge edge(i, j, _edges[i][j]);minHeap.emplace(edge);}}}UnionFindSet ufs(n); // 用于避免构成回路的并查集size_t count 0; // 计数器用于统计选取了多少条边W totalW W(); // 总权值计数器std::cout Kruskal开始选边 std::endl;while (!minHeap.empty()){// 小根堆堆顶为当前尚未被筛选且权值最小的边size_t srci minHeap.top()._srci;size_t dsti minHeap.top()._dsti;size_t w minHeap.top()._w;minHeap.pop();// 检查当前两个节点是否位于同一并查集的几何中if (!ufs.InSet(srci, dsti)){std::cout [ _vertex[srci] - _vertex[dsti] ]: w std::endl;// 向最小生成树中添加srci-dsti的边minTree._AddEdge(srci, dsti, w);// 将srci和dsti归为同一集合ufs.Union(srci, dsti);// 选边计数器1权值累加count;totalW w;}else{std::cout 构成环 [ _vertex[srci] - _vertex[dsti] ]: w std::endl;}}// 如果选择了n-1条边那么说明获取了最小生成树否则获取最小生成树失败if (count n - 1) {return totalW;}else {return MAX_W;}}private:std::vectorV _vertex; // 存储顶点值的一维数组std::unordered_mapV, size_t _valIndexMap; // 顶点值与其在数组下标中的映射关系std::vectorstd::vectorW _edges; // 邻接矩阵};
}
代码4.2并查集UnionFindSet.hpp头文件
#pragma once#include vector
#include algorithmclass UnionFindSet
{
public:UnionFindSet(size_t n):_ufs(n, -1){}void Union(int x1, int x2){int root1 FindRoot(x1);int root2 FindRoot(x2);// 如果本身就在一个集合就没必要合并了if (root1 root2)return;// 控制数据量小的往大的集合合并if (abs(_ufs[root1]) abs(_ufs[root2]))std::swap(root1, root2);_ufs[root1] _ufs[root2];_ufs[root2] root1;}int FindRoot(int x){int root x;while (_ufs[root] 0){root _ufs[root];}// 路径压缩while (_ufs[x] 0){int parent _ufs[x];_ufs[x] root;x parent;}return root;}// 检查两个节点是否属于同一集合bool InSet(int x1, int x2){return FindRoot(x1) FindRoot(x2);}// 获取并查集中集合的数量size_t SetSize(){size_t size 0;for (size_t i 0; i _ufs.size(); i){if (_ufs[i] 0){size;}}return size;}private:std::vectorint _ufs;
};
4.3 Prim算法
Prim算法普里姆算法的思路与Kruskal算法基本一致采用的都是贪心策略与Kruskal算法不同的是Prim算法会选定一个起始点src并将已经连通的顶点和尚未被连通的顶点划分到两个集合中去分别记为S和U每一次筛选都会选出从si-ui的边中权值最小的那个由于对已经连通和尚未连通的顶点进行了划分因此选边建立连接的过程中不需要并查集来辅助就能够避免成环。图4.3为Prim算法的选边过程红色加粗的实线为被选择的边。 图4.2 Prim算法的选边过程 代码4.3Prim算法的实现
// Prim算法获取最小生成树
W Prim(const V src, Self minTree)
{// 初始化minTree中的每个成员size_t n _vertex.size();minTree._vertex _vertex;minTree._valIndexMap _valIndexMap;minTree._edges.resize(n, std::vectorW(n, MAX_W));// 起始节点对应下标size_t srci GetIndex(src);// visited记录每个顶点是否已经被连通了起来std::vectorbool visited(n, false);visited[srci] true; // 源顶点自身连通// 用于选取最短边的小根堆std::priority_queueEdge, std::vectorEdge, std::greaterEdge minHeap;// 将以srci为起点的边添加到小根堆中去for (size_t i 0; i n; i){if (_edges[srci][i] ! MAX_W){// Edge edge(srci, i, _edges[srci][i]);// minHeap.push(edge);minHeap.emplace(srci, i, _edges[srci][i]);}}size_t count 0; // 选边计数器W totalW W(); // 权值之和std::cout Prim开始选边 std::endl;// 开始依次选边while (!minHeap.empty()){// 取当前边的起点为u终点为v权重为wsize_t u minHeap.top()._srci;size_t v minHeap.top()._dsti;W w minHeap.top()._w;minHeap.pop();// 检查建立u-v的连接后是否会构成环if (visited[v] false) // 不会构成环{std::cout [ _vertex[u] - _vertex[v] ]: w std::endl;// 在minTree中建立u-v的连接minTree._AddEdge(u, v, w);// 记顶点v被选取选边计数器1权值累加visited[v] true;count;totalW w;// 将以v为起点的边添加到小根堆minHeap中去for (size_t k 0; k n; k){if (visited[k] false _edges[v][k] ! MAX_W){// Edge edge(v, k, _edges[v][k]);// minHeap.push(edge);minHeap.emplace(v, k, _edges[v][k]);}}}else{std::cout 构成环 [ _vertex[u] - _vertex[v] ]: w std::endl;}}if (count 1 n) {return totalW;}else {return MAX_W;}
}
五. 最短路径问题
最短路径就是计算从任意顶点vi到vj所经过的路径权值和最小的那条路径。
5.1 Dijkstra算法
Dijkstra算法迪杰斯特拉算法用于求单源最短路径即给定一个起点计算以这个顶点为起点图中其余任意顶点为终点的路径中权值之和最小的那一条路径。注意Dijkstra算法要求不能带有负权值。
Dijkstra算法的核心思想是贪心算法其大致的流程为将一个有向图G中的顶点分为S和Q两组其中S为已经确定了最短路径的顶点Q为尚未确定最短路径的顶点最初先将处源顶点srci以外所有顶点都加入Q源顶点srci加入S。每次从Q中找出一个源顶点到该顶点最小的顶点u将其从Q中移出放入到S中对与u相邻的顶点v进行松弛操作。所谓松弛操作就是比较srci-u s-v的和是否比原来srci-v的路径和小如果是那么就更新srci-v的最短路径反复进行松弛操作直到Q集合中没有顶点。图5.1为Dijkstra算法松弛迭代的过程黑色填充的顶点为已经确定最短路径的顶点灰色填充为本轮遍历的源顶点。 图5.1 Dijkstra算法的松弛迭代过程 代码5.1为Dijkstra算法的具体实现该函数接收三个参数分别为起始点、最小路径dist(输出型参数)、每个顶点的父亲顶点pPath(输出型参数)这里使用pPath的目的是为了避免存储全部的路径达到节省空间降低算法编码难度的目的。为了观察结果实现了PrintPath函数用于打印顶点src到任意顶点的最短路径。
代码5.1Dijkstra算法的实现
// Dijkstra求最小生成树
// dist为路径和pPath为每个顶点前导顶点的下标
void Dijkstra(const V src, std::vectorW dist, std::vectorsize_t pPath)
{// 初始化dist和pPath数组size_t n _vertex.size();dist.resize(n, MAX_W);pPath.resize(n, -1);size_t srci GetIndex(src); // 起始顶点的下标dist[srci] 0;pPath[srci] srci;// visited数组记录每个顶点是否已经可以确定最短路径std::vectorbool visited(n, false);// visited[srci] true;// 开始选边迭代for (size_t k 0; k n; k){// 挑选出尚未确定最短路径的顶点中离srci最近的顶点记下标为usize_t u -1;W minDist MAX_W;for (size_t i 0; i n; i){if (visited[i] false dist[i] minDist){u i;minDist dist[i];}}// 将u添加到已经确定最小路径和的集合中去visited[u] true;// 检查u-v dist[u]是否比原来的dist[v]小// 如果小那么更新dist[v]的值for (size_t v 0; v n; v){if (visited[v] false _edges[u][v] ! MAX_W dist[u] _edges[u][v] dist[v]){dist[v] dist[u] _edges[u][v];pPath[v] u;}}}
}// 路径打印函数
void PrintPath(const V src, const std::vectorW dist, const std::vectorsize_t pPath)
{size_t srci GetIndex(src);size_t n pPath.size();for (size_t i 0; i n; i){std::vectorint path;size_t parent i;while (pPath[parent] ! parent){path.push_back(parent);parent pPath[parent];}path.push_back(srci);std::reverse(path.begin(), path.end());for (const auto x : path){std::cout _vertex[x] -;}std::cout 权重: dist[i] std::endl;}
}
5.2 Bellman-Ford算法
Dijkstra算法不能解决带有负权的图的问题为此Bellman-Ford算法贝尔曼-福特算法被提了出来这种算法可以解决带有负权的图的最小路径问题这种算法也是用于解决单源最短路径问题的即给定一个起始点src获取从src到每一个顶点的最短路径。
Bellman-Ford算法实际上是一种暴力求解的算法对于有N个顶点的图要暴力搜索顶点vi和顶点vj迭代更新最短路径。Bellman-Ford算法的时间复杂度为O(N^3)而Dijkstra算法的时间复杂度为O(N^2)因此对于不带有负权的图应当使用Dijkstra求最短路径而非使用Bellman-Ford算法。 图5.2 Bellman-Ford算法的松弛迭代过程 但是Bellman-Ford算法无法解决负权回路所谓负权回路就是图结构中的某个环其所有边的权值累加起来小于0就是负权回路。如图5.3所示的图a-b-d-a就是一个负权回路a-b-d-a的权值加起来为-2这样就存在一种诡异的现象即每一次从a出发再回到a路径权值之和都会变小这样理论上a-a的路径可以无限小对于存在负权回路的图没有任何办法可以解决其最小路径问题 图5.3 负权回路 代码5.2Bellman-Ford算法的实现
// BellmanFord 算法获取单源最短路径
bool BellmanFord(const V src, std::vectorW dist, std::vectorsize_t pPath)
{// 初始化输出型参数size_t n _vertex.size();dist.resize(n, MAX_W);pPath.resize(n, -1);size_t srci GetIndex(src); // 源顶点对应的下标dist[srci] 0; // srci-srci距离为0pPath[srci] srci; // 原顶点的前导节点记为其自身for (size_t k 0; k n; k){// 遍历节点i和节点j更新迭代for (size_t i 0; i n; i){for (size_t j 0; j n; j){if (dist[i] ! MAX_W _edges[i][j] ! MAX_W dist[i] _edges[i][j] dist[j]){dist[j] dist[i] _edges[i][j];pPath[j] i;}}}}// 检查是否有负权回路如果有返回false否则返回truefor (size_t i 0; i n; i){for (size_t j 0; j n; j){if (_edges[i][j] ! MAX_W dist[i] _edges[i][j] dist[j]){return false;}}}return true;
}
5.3 Floyd-Warshall算法
Floyd-Warshall算法弗洛伊德算法是用于计算多源最短路径的算法其基本原理为三维动态规划算法
设为从顶点i到定点j仅以 {1,2,...,k}顶点为中间顶点的情况下的最短路径和。
若i-j的最短路径经过k那么如i-j的最短路径不经过k那么
状态转移方程为
Floyd-Warshall算法的本质是三维动态规划算法D[i][j][k]表示的是从顶点i到顶点j在只经过0~k个中间顶点的情况下的最短路径。通过优化将最后一维k优化掉这是只需要二维数组D[i][j]就可以计算出多源最短路径Floyd-Warshall算法的时间复杂度为O(N^3)空间复杂度为O(N^2)且Floyd-Warshall算法可以解决带有负权的图的问题。
代码5.3Floyd-Warshall算法的实现
// FloydWarshall算法计算多源最短路径
void FloydWarshall(std::vectorstd::vectorW vvDist, std::vectorstd::vectorsize_t vvPath)
{// 初始化记录路径和的数组和记录前导节点的数组size_t n _vertex.size();vvDist.resize(n, std::vectorW(n, MAX_W));vvPath.resize(n, std::vectorsize_t(n, -1));// 将图中直接相连的边添加到vvDist和vvPath中去for (size_t i 0; i n; i){for (size_t j 0; j n; j){if (_edges[i][j] ! MAX_W){vvDist[i][j] _edges[i][j];vvPath[i][j] i;}if (i j){vvDist[i][j] 0;vvPath[i][j] i;}}}// 三维数组动态规划查找多源最短路径for (size_t k 0; k n; k){bool change false;for (size_t i 0; i n; i){for (size_t j 0; j n; j){if (vvDist[i][k] ! MAX_W vvDist[k][j] ! MAX_W vvDist[i][k] vvDist[k][j] vvDist[i][j]){change true;vvDist[i][j] vvDist[i][k] vvDist[k][j];vvPath[i][j] vvPath[k][j];}}}if (change false){break;}}
}
六. 总结
图是一种存储顶点和边的数据结构记为G{V,E}图还可以细分为带权图和无权图、有向图和无向图。图的存储结构有邻接表和邻接矩阵两种格式这两种方式各有优劣但对于稠密图一般使用邻接矩阵。最小生成树是在无向连通图中能够将每个顶点连接起来的、边权值和最小的子树通过Kruskal算法和Prim算法可以获取最小生成树这两种算法的策略都是局部贪心。Dijkstra算法和Bellman-Ford算法可以计算单源最短路径问题Dijkstra算法无法计算带负权的图的最小路径Bellman-Ford算法可以解决负权问题但是Dijkstra算法的时间复杂度为O(N^2)Bellman-Ford算法的时间复杂度为O(N^3)。Floyd-Warshall算法用于计算多源最短路径问题这种算法的思想是动态规划可以解决负权问题时间复杂度为O(N^3)。
