机械网站建设营销,网站404页面作用,wordpress 默认搜索引擎,手机数据线东莞网站建设图 1.图的基本概念2. 图的存储结构2.1邻接矩阵2.2邻接表2.3两种实现的比较 3.图的遍历3.1 图的广度优先遍历3.2 图的深度优先遍历 4.最小生成树4.1 Kruskal算法4.2 Prim算法4.3 两个算法比较 5.最短路径5.1两个抽象存储5.2单源最短路径--Dijkstra算法5.3单源最短路径--Bellman-… 图 1.图的基本概念2. 图的存储结构2.1邻接矩阵2.2邻接表2.3两种实现的比较 3.图的遍历3.1 图的广度优先遍历3.2 图的深度优先遍历 4.最小生成树4.1 Kruskal算法4.2 Prim算法4.3 两个算法比较 5.最短路径5.1两个抽象存储5.2单源最短路径--Dijkstra算法5.3单源最短路径--Bellman-Ford算法5.4 多源最短路径--Floyd-Warshall算法5.5 几个算法的比较 1.图的基本概念
概念多但是不难理解难的算法部分基本都是图解。
图是由顶点集合及顶点间的关系组成的一种数据结构G (V E)其中V为顶点集合E为边集合。
顶点和边图中结点称为顶点第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为无向图。 有向完全图在有n个顶点的无向图中若有n * (n-1)/2条边即任意两个顶点之间有且仅有一条边则称此图为无向完全图比如上图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. 图的存储结构
因为图中既有节点又有边(节点与节点之间的关系)因此在图的存储中只需要保存节点和边关系即可。节点保存比较简单只需要一段连续空间即可那边关系该怎么保存呢
2.1邻接矩阵
因为节点与节点之间的关系就是连通与否即为0或者1因此邻接矩阵(二维数组)即是先用一个数组将定点保存然后采用矩阵来表示节点与节点之间的关系。 注意
无向图的邻接矩阵是对称的第i行(列)元素之和就是顶点i的度。有向图的邻接矩阵则不一定是对称的第i行(列)元素之后就是顶点i 的出(入)度。如果边带有权值并且两个节点之间是连通的上图中的边的关系就用权值代替如果两个顶点不通则使用无穷大自己设定值表示无穷代替。
代码实现
namespace maritx
{//V为顶点类型无论什么类型都可以转换位对于的下标访问时使用哈希表转换出下标//W为边类型一般为数值类型MAX_W代表边不存在//Direction表示方向默认无向templateclass V, class W, W MAX_W INT_MAX, bool Direction false //默认无向class Graph{private:vectorV _vertexs; //顶点mapV, size_t _VIndexMap; //顶点 下标vectorvectorW _matrix; //邻接矩阵public:typedef GraphV, W, MAX_W, Direction self;Graph() default;Graph(const V* vertexs, size_t n){_vertexs.resize(n);for (size_t i 0; i n; i){_vertexs[i] vertexs[i];_VIndexMap[vertexs[i]] i;}//初始化邻接矩阵_matrix.resize(n);for (int i 0; i n; i){_matrix[i].resize(n, MAX_W);}}size_t GetVIndex(const V v){if (_VIndexMap.count(v)){return _VIndexMap[v];}else //如果没有这个顶点{throw invalid_argument(不存在的顶点);//assert(false);return -1;}}void AddEdge(const V src, const V dst, const W w){size_t srci GetVIndex(src);size_t dsti GetVIndex(dst);_AddEdge(srci, dsti, w);}void _AddEdge(int srci, int dsti, const W w){_matrix[srci][dsti] w; //有向图只需添加一边if (Direction false){_matrix[dsti][srci] w;}}};
}2.2邻接表
邻接表使用数组表示顶点的集合使用链表表示边的关系。 无向图邻接表存储 有向图邻接表存储
代码实现
namespace link_table
{templateclass Wstruct Edge{W _w; //权值int _dsti;EdgeW* _next;Edge(int dsti,const W w):_dsti(dsti),_w(w),_next(nullptr){}};templateclass V, class W, bool Direction false //默认无向class Graph{public:typedef EdgeW Edge;Graph(const V* vertexs, size_t n){_vertexs.resize(n);for (size_t i 0; i n; i){_vertexs[i] vertexs[i];_VIndexMap[vertexs[i]] i;}//初始化邻接矩阵_tables.resize(n, nullptr);}size_t GetVIndex(const V v){if (_VIndexMap.count(v)){return _VIndexMap[v];}else //如果没有这个顶点{throw invalid_argument(不存在的顶点);//assert(false);return -1;}}void AddEdge(const V src, const V dst, const W w){size_t srci GetVIndex(src);size_t dsti GetVIndex(dst);Edge* newnode new Edge(dsti, w);newnode-_next _tables[srci];_tables[srci] newnode; //有向图只需添加一边if (Direction false){Edge* newnode new Edge(srci, w);newnode-_next _tables[dsti];_tables[dsti] newnode;}}void Print(){// 打印顶点和下标映射关系for (size_t i 0; i _vertexs.size(); i){cout _vertexs[i] - i ;}cout endl endl;for (int i 0; i _tables.size(); i){Edge* cur _tables[i];if(cur) cout i;while (cur){cout - cur-_dsti ;cur cur-_next;}cout endl;}}private:vectorV _vertexs; //顶点mapV, int _VIndexMap; //顶点下标vectorEdge* _tables; //邻接表};
}2.3两种实现的比较
对于邻接矩阵优点是确定AB两点间关系时方便。缺点是对于边数量少的情况想遍历与某点的出(入)边需要遍历矩阵的一行N空间也会很浪费。对于邻接表优点是边少时遍历点的出(入)边有几条边就走几次。缺点是想确定AB两点间关系时需要遍历一次邻接表。推荐关系复杂边多时使用邻接矩阵。 关系简单边少时使用邻接表。两种存储实现图相关算法差别不大后面的算法都是基于邻接矩阵的。 3.图的遍历
给定一个图G和其中任意一个顶点v0从v0出发沿着图中各边访问图中的所有顶点且每个顶点仅被遍历一次。遍历即对结点进行某种操作的意思。 树的遍历是自顶点向下图的遍历是选定一个顶点作为起点。
3.1 图的广度优先遍历 //遍历
void BFS(const V v)
{size_t n _vertexs.size();size_t srci GetVIndex(v);vectorbool visited(n);queuesize_t q;q.push(srci);visited[srci] true;while (!q.empty()){size_t sz q.size();for (size_t i 0; i sz; i){size_t top q.front(); q.pop();cout _vertexs[top] ;for (size_t j 0; j n; j){if (_matrix[top][j] ! MAX_W visited[j] ! true) //存在并且没有访问过{q.push(j);visited[j] true;}}}}//有可能存在从v点出发到不了某些点的情况这时可遍历vis数组for (int i 0; i n; i){if (visited[i] false){cout _vertexs[i] ;}}cout endl;
}3.2 图的深度优先遍历 void DFS(const V v)
{size_t srci GetVIndex(v);vectorbool visited(_vertexs.size());dfs(srci, visited);//有可能存在从v点出发到不了某些点的情况这时可遍历vis数组for (int i 0; i n; i){if (visited[i] false){cout _vertexs[i] ;}}
}void dfs(size_t srci, vectorbool visited)
{cout _vertexs[srci] ;visited[srci] true;for (int i 0; i _vertexs.size(); i){if (_matrix[srci][i] ! MAX_W visited[i] ! true){dfs(i, visited);}}
}4.最小生成树
连通图中的每一棵生成树都是原图的一个极大无环子图即从其中删去任何一条边生成树就不在连通反之在其中引入任何一条新边都会形成一条回路。
若连通图由n个顶点组成则其生成树必含n个顶点和n-1条边。因此构造最小生成树的准则有三条
只能使用图中的边来构造最小生成树只能使用恰好n-1条边来连接图中的n个顶点选用的n-1条边不能构成回路
构造最小生成树的方法Kruskal算法和Prim算法。这两个算法都采用了逐步求解的贪心策略。
贪心算法是指在问题求解时总是做出当前看起来最好的选择。也就是说贪心算法做出的不是整体最优的的选择而是某种意义上的局部最优解。贪心算法不是对所有的问题都能得到整体最优解Kruskal算法和Prim算法都可保证最优两种策略相当容易记忆证明难度较大本文不做证明。 4.1 Kruskal算法
每次都选用图中权值最小的边来构造可以使用堆实现。只能选n - 1条边。选用的边不可构成回路可以使用并查集来判断环是否存在。 不了解并查集的可以看这篇文章很简单的并查集 不了解堆的可以看这篇文章堆 struct Edge //存储边信息
{int _srci;int _dsti;W _w;Edge(int srci, int dsti, W w):_srci(srci),_dsti(dsti),_w(w){}bool operator(const Edge edge) const{return _w edge._w;}
};//Kruskal(克鲁斯卡尔),生成的了返回权值生成不了返回W默认值
W Kruskal(self minTree)
{//初始化一下最小生成树size_t n _vertexs.size();minTree._vertexs _vertexs;minTree._VIndexMap _VIndexMap;minTree._matrix.resize(n);for (auto e : minTree._matrix){e.resize(_vertexs.size(), MAX_W);}UnionFindSet ufs(n); //并查集priority_queueEdge, vectorEdge, greaterEdge pq; //堆//入边for (int i 0; i n; i){for (int j i; j n; j) //无向图只需要一半即可{if(_matrix[i][j] ! MAX_W)pq.push(Edge(i, j, _matrix[i][j]));}}//依次选最小边选n - 1size_t esum 0;W ret 0;//不断选最小边即可while (!pq.empty()){Edge e pq.top(); pq.pop();if (!ufs.InSet(e._srci, e._dsti)) //不在一个集合(不构成回路)当前边可选{minTree.AddEdge(e._srci, e._dsti, e._w);esum;ret e._w;ufs.Union(e._srci, e._dsti);}}//判断可否形成最小生成树if (esum n - 1){return ret;}else{return W();}
}4.2 Prim算法
Kruskal算法侧重边Prim算法侧重点。设有XY两个点集合X表示已在最小生成树中的点Y表示还未在最小生成树中的点。故选边时选的是X-Y所有边中的最小权值。只能选n - 1条边。选用的边不可构成回路只需选的边起点在X终点在Y即可。
//prim(普利姆算法)
W Prim(self minTree, const V src)
{//初始化一下最小生成树size_t n _vertexs.size();minTree._vertexs _vertexs;minTree._VIndexMap _VIndexMap;minTree._matrix.resize(n);for (auto e : minTree._matrix){e.resize(_vertexs.size(), MAX_W);}size_t srci GetVIndex(src); //起点//存储边的堆priority_queueEdge, vectorEdge, greaterEdge pq;//X和Y集合不在X就在Yvectorbool X(n, false);X[srci] true;//把X初始点的边入进去for (size_t i 0; i n; i){if (_matrix[srci][i] ! MAX_W){pq.push(Edge(srci, i, _matrix[srci][i]));}}//选出边的条数size_t esum 0;W ret 0;while (!pq.empty()){Edge e pq.top(); pq.pop();if (X[e._dsti] ! true) //终点在Y选了不成环{minTree.AddEdge(e._srci, e._dsti, e._w); esum;ret e._w;X[e._dsti] true; for (int i 0; i n; i){//入边为X-YX-X的边没必要入if (_matrix[e._dsti][i] ! MAX_W X[i] ! true) {pq.push(Edge(e._dsti, i, _matrix[e._dsti][i]));}}}}//判断可否形成最小生成树if (esum n - 1){return ret;}else{return W();}
}4.3 两个算法比较
Kruskal算法适用于稀疏图即边少的图因为该算法需要用堆维护所有的边。Prim算法适用于稠密图即边多的图因为该算法的要点在点并不需要维护所有的边(X-X的边无需维护)。 5.最短路径
5.1两个抽象存储 基于这两个抽象数据结构还原最短路径
//打印最短路径的算法
void PrinrtShotPath(const V src, const vectorW dist, const vectorint pPath)
{size_t n _vertexs.size();size_t srci GetVIndex(src);for (size_t i 0; i n; i){if (i ! srci) //源到源不打印{size_t par i;vectorsize_t path; //先从结尾开始添加while (par ! srci){path.push_back(par);par pPath[par];}path.push_back(srci); reverse(path.begin(), path.end()); //翻转过来for (auto pos : path){cout _vertexs[pos] -;}cout dist[i] endl; //打印长度}}
}5.2单源最短路径–Dijkstra算法
贪心分为两个集合Q和S其中Q表示已经确定最短路径的顶点集合S表示未确定最短路径的顶点集合。在已有最短路径的基础上更新到其他顶点的路径如果更短就更新这个操作称为松弛顶点。建议配合图解看Dijkstra算法不适用于带负权的最短路径问题后面解释。
图解 正确性证明
图边权没有负数 1如果现在遍历 起点-S(未确定最短路径点集合)的边找到一条s-x(记和为len)的最短那就可以确定这条是s-x的最短。 2因为如果存在s-……(和一定小于len)-x的一条更短路径那遍历时就会先选中s-……中的顶点进行松弛而不是选中x进行松弛。图边权有负数 1遍历 起点-S(未确定最短路径点集合)的边找到一条s-x(记和为len)的最短不能确定这条是s-x的最短。 2因为可能存在s-……大于len-负权-x(小于len)这时候就会更新不到这条真正的最短
//单源最短路径dijkstra算法不带负权
//每次都可以确定一个点的最短路径然后围绕这个点松弛
//准确性如果当前选的不是最短那就不会选中当前而是其他的点在松弛操作中更新出最短
//两个输出型参数,dist为路径长pPath记录路径
void Dijkstra(const V src, vectorW dist, vectorint pPath)
{size_t n _vertexs.size();size_t srci GetVIndex(src);//初始化dist.resize(n, MAX_W);pPath.resize(n, -1);dist[srci] W();//Q中为true说明已经确认最短路径vectorbool Q(n, false);//要确定N个顶点的最短循环N次其实只要N-1次即可但为了逻辑就多循环一次for (size_t i 0; i n; i){size_t u srci;W min MAX_W;//找到最短的路径该路径已经可确认为最短for (size_t j 0; j n; j){if (Q[j] false dist[j] min){u j;min dist[j];}}Q[u] true;//松弛顶点 srci-u u-v - srci-vfor (size_t v 0; v n; v){if (_matrix[u][v] ! MAX_W dist[u] _matrix[u][v] dist[v]){dist[v] dist[u] _matrix[u][v];pPath[v] u;}} }
}5.3单源最短路径–Bellman-Ford算法
Bellman-Ford算法本质是暴力算法。Bellman-Ford算法可以解决带负权的问题。Bellman-Ford算法的核心在于松弛顶点。
图解 负权回路
//单源最短路径BellmanFord算法带负权注意负权成环
bool BellmanFord(const V src, vectorW dist, vectorint pPath)
{size_t n _vertexs.size();size_t srci GetVIndex(src);//初始化dist.resize(n, MAX_W);pPath.resize(n, -1);dist[srci] W();//最多更新n - 1for (size_t k 0; k n - 1; k){//优化的标志位如果没有松弛更短说明所有顶点最短路径都找到了bool flag true;//所有顶点做一次松弛for (size_t i 0; i n; i){for (size_t j 0; j n; j){//src - i - jif (_matrix[i][j] ! MAX_W dist[i] _matrix[i][j] dist[j]) //更新出更短{dist[j] dist[i] _matrix[i][j];pPath[j] i;flag false;}}}if (flag){break;}}for (size_t i 0; i n; i){for (size_t j 0; j n; j){//还能更新说明存在负权回路问题if (_matrix[i][j] ! MAX_W dist[i] _matrix[i][j] dist[j]) //更新出更短{return false;}}}return true;
}5.4 多源最短路径–Floyd-Warshall算法
多源最短即求任意两点的最短路径。适用于带负权的图。Floyd-Warshall算法的核心是动态规划。
图解 //多源最短路径FloydWarshall
//vvDist和vvPPath是二维的vvDist[x]和vvPPath[x]表示以x为起点到各点的最短路径情况
void FloydWarShall(vectorvectorW vvDist, vectorvectorint vvPPath)
{size_t n _vertexs.size();vvDist.resize(n);vvPPath.resize(n);// 初始化权值和路径矩阵for (size_t i 0; i n; i){vvDist[i].resize(n, MAX_W);vvPPath[i].resize(n, -1);}//把直接相连的边入进来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;}//i j,即自己到自己if (i j){vvDist[i][j] W();}}}//中间经过了(0, k)这些顶点for (size_t k 0; k n; k){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]){vvDist[i][j] vvDist[i][k] vvDist[k][j];vvPPath[i][j] vvPPath[k][j];}}}}
}5.5 几个算法的比较
假设图是稠密图我们使用矩阵存储。 对这些算法的时间复杂度分析 Dijkstra算法ON ^ 2。 Bellman-Ford算法ON ^ 3。 Floyd-Warshall算法ON ^ 3。Dijkstra算法适用于不带负权的图如果想对不带负权的图找多源最短路径也可以循环N次Dijkstra算法效率和Floyd-Warshall差不多。Bellman-Ford算法和Floyd-Warshall算法都可以解决带负权的问题。Bellman-Ford算法大多数情况是快于Floyd-Warshall算法的只是要单源最短且带负权用Bellman-Ford即可。而且针对Bellman-Ford算法可以用SPFA队列优化。SPFA优化本文不讲SPFA优化后时间复杂度不变最坏的情况和朴素Bellman-Ford算法一致Floyd-Warshall算法用于解决多源最短路径是效果较好而且可解决带负权问题。
