大家好，欢迎来到IT知识分享网。
文章目录
1.图的一种分类：无权图、有权图
2.无权图的表示
邻接矩阵实现： // 稠密图 class DenseGraph{
private: int n, m; // 节点数和边数 bool directed; // 是否为有向图 vector<vector<bool>> g; // 图的具体数据 public: DenseGraph( int n , bool directed ){
assert( n >= 0 ); this->n = n; this->m = 0; // 初始化没有任何边 this->directed = directed; // g初始化为n*n的布尔矩阵, 每一个g[i][j]均为false, 表示没有任和边 //实现方式1： g = vector<vector<bool>>(n, vector<bool>(n, false)); /*实现方式2： for(int i=0; i<n; i++) g.push_back(vector<bool>(n,false)); } */ ~DenseGraph(){
} int V(){
return n;} // 返回节点个数 int E(){
return m;} // 返回边的个数 // 向图中添加一个边 void addEdge( int v , int w ){
assert( v >= 0 && v < n ); assert( w >= 0 && w < n ); if( hasEdge( v , w ) ) return; g[v][w] = true; if( !directed ) g[w][v] = true; m ++; } // 验证图中是否有从v到w的边 bool hasEdge( int v , int w ){
assert( v >= 0 && v < n ); assert( w >= 0 && w < n ); return g[v][w]; } }; 邻接表实现: class SparseGraph{
private: int n, m; // 节点数和边数 bool directed; // 是否为有向图 vector<vector<int>> g; // 图的具体数据 public: SparseGraph( int n , bool directed ){
assert( n >= 0 ); this->n = n; this->m = 0; // 初始化没有任何边 this->directed = directed; // g初始化为n个空的vector, 表示每一个g[i]都为空, 即没有任和边 //实现方式1: g = vector<vector<int>>(n, vector<int>()); /*实现方式2： for(int i=0; i<n; i++) g.push_back(vector<int>( )); */ } ~SparseGraph(){
} int V(){
return n;} // 返回节点个数 int E(){
return m;} // 返回边的个数 // 向图中添加一个边 void addEdge( int v, int w ){
assert( v >= 0 && v < n ); assert( w >= 0 && w < n ); g[v].push_back(w); if( v != w && !directed ) g[w].push_back(v); m ++; } // 验证图中是否有从v到w的边 bool hasEdge( int v , int w ){
assert( v >= 0 && v < n ); assert( w >= 0 && w < n ); for( int i = 0 ; i < g[v].size() ; i ++ ) if( g[v][i] == w ) return true; return false; } }; 3.无权图的联通分量、最短路径
3.1 深度优先遍历求连通分量
// 求无权图的联通分量 template <typename Graph> class Component{
private: Graph &G; // 图的引用 bool *visited; // 记录dfs的过程中节点是否被访问 int ccount; // 记录联通分量个数 int *id; // 每个节点所对应的联通分量标记 // 图的深度优先遍历 void dfs( int v ){
visited[v] = true; id[v] = ccount; typename Graph::adjIterator adj(G, v); //相邻结点迭代器 for( int i = adj.begin() ; !adj.end() ; i = adj.next() ){
if( !visited[i] ) dfs(i); } } public: Component(Graph &graph): G(graph){
visited = new bool[G.V()]; id = new int[G.V()]; ccount = 0; for( int i = 0 ; i < G.V() ; i ++ ){
visited[i] = false; id[i] = -1; } // 求图的联通分量 for( int i = 0 ; i < G.V() ; i ++ ) if( !visited[i] ){
dfs(i); ccount ++; } } ~Component(){
delete[] visited; delete[] id; } // 返回图的联通分量个数 int count(){
return ccount; } // 查询点v和点w是否联通 bool isConnected( int v , int w ){
assert( v >= 0 && v < G.V() ); assert( w >= 0 && w < G.V() ); return id[v] == id[w]; } }; 3.2 广度优先遍历求最短路径
// 寻找无权图的最短路径 template <typename Graph> class ShortestPath{
private: Graph &G; // 图的引用 int s; // 起始点 bool *visited; // 记录dfs的过程中节点是否被访问 int *from; // 记录路径, from[i]表示查找的路径上i的上一个节点 int *ord; // 记录路径中节点的次序。ord[i]表示i节点在路径中的次序。 public: // 寻找无权图graph从s点到其他点的最短路径 ShortestPath(Graph &graph, int s):G(graph){
// 算法初始化 assert( s >= 0 && s < graph.V() ); visited = new bool[graph.V()]; from = new int[graph.V()]; ord = new int[graph.V()]; for( int i = 0 ; i < graph.V() ; i ++ ){
visited[i] = false; from[i] = -1; ord[i] = -1; } this->s = s; // 无向图最短路径算法, 从s开始广度优先遍历整张图 queue<int> q; q.push( s ); visited[s] = true; ord[s] = 0; while( !q.empty() ){
int v = q.front(); q.pop(); typename Graph::adjIterator adj(G, v); for( int i = adj.begin() ; !adj.end() ; i = adj.next() ) if( !visited[i] ){
q.push(i); visited[i] = true; from[i] = v; ord[i] = ord[v] + 1; } } } ~ShortestPath(){
delete [] visited; delete [] from; delete [] ord; } // 查询从s点到w点是否有路径 bool hasPath(int w){
assert( w >= 0 && w < G.V() ); return visited[w]; } // 查询从s点到w点的路径, 存放在vec中 void path(int w, vector<int> &vec){
assert( w >= 0 && w < G.V() ); stack<int> s; // 通过from数组逆向查找到从s到w的路径, 存放到栈中 int p = w; while( p != -1 ){
s.push(p); p = from[p]; } // 从栈中依次取出元素, 获得顺序的从s到w的路径 vec.clear(); while( !s.empty() ){
vec.push_back( s.top() ); s.pop(); } } // 打印出从s点到w点的路径 void showPath(int w){
assert( w >= 0 && w < G.V() ); vector<int> vec; path(w, vec); for( int i = 0 ; i < vec.size() ; i ++ ){
cout<<vec[i]; if( i == vec.size()-1 ) cout<<endl; else cout<<" -> "; } } // 查看从s点到w点的最短路径长度 int length(int w){
assert( w >= 0 && w < G.V() ); return ord[w]; } }; 4.有权图表示
自定义一个Edge类来表示边上权重信息和所连接的节点 template<typename Weight> class Edge{
private: int a,b; // 边的两个端点 Weight weight; // 边的权值 public: Edge(int a, int b, Weight weight){
this->a = a; this->b = b; this->weight = weight; } // 空的构造函数, 所有的成员变量都取默认值 Edge(){
} ~Edge(){
} int v(){
return a;} // 返回第一个顶点 int w(){
return b;} // 返回第二个顶点 Weight wt(){
return weight;} // 返回权值 // 给定一个顶点, 返回另一个顶点 int other(int x){
assert( x == a || x == b ); return x == a ? b : a; } // 输出边的信息 friend ostream& operator<<(ostream &os, const Edge &e){
os<<e.a<<"-"<<e.b<<": "<<e.weight; return os; } // 边的大小比较, 是对边的权值的大小比较 bool operator<(Edge<Weight>& e){
return weight < e.wt(); } bool operator<=(Edge<Weight>& e){
return weight <= e.wt(); } bool operator>(Edge<Weight>& e){
return weight > e.wt(); } bool operator>=(Edge<Weight>& e){
return weight >= e.wt(); } bool operator==(Edge<Weight>& e){
return weight == e.wt(); } }; //邻接矩阵实现 // 稠密图 - 邻接矩阵 template <typename Weight> class DenseGraph{
private: int n, m; // 节点数和边数 bool directed; // 是否为有向图 vector<vector<Edge<Weight> *>> g; // 图的具体数据 public: DenseGraph( int n , bool directed){
assert( n >= 0 ); this->n = n; this->m = 0; this->directed = directed; // g初始化为n*n的矩阵, 每一个g[i][j]指向一个边的信息, 初始化为NULL //实现1： g = vector<vector<Edge<Weight> *>>(n, vector<Edge<Weight> *>(n, NULL)); /*实现方式2： for(int i=0; i<n; i++) g.push_back(vector<Edge<Weight> *>(n,NULL)); } */ } ~DenseGraph(){
for( int i = 0 ; i < n ; i ++ ) for( int j = 0 ; j < n ; j ++ ) if( g[i][j] != NULL ) delete g[i][j]; } int V(){
return n;} // 返回节点个数 int E(){
return m;} // 返回边的个数 // 向图中添加一个边, 权值为weight void addEdge( int v, int w , Weight weight ){
assert( v >= 0 && v < n ); assert( w >= 0 && w < n ); // 如果从v到w已经有边, 删除这条边 if( hasEdge( v , w ) ){
delete g[v][w]; if( v != w && !directed ) delete g[w][v]; m --; } g[v][w] = new Edge<Weight>(v, w, weight); if( v != w && !directed ) g[w][v] = new Edge<Weight>(w, v, weight); m ++; } // 验证图中是否有从v到w的边 bool hasEdge( int v , int w ){
assert( v >= 0 && v < n ); assert( w >= 0 && w < n ); return g[v][w] != NULL; } // 显示图的信息 void show(){
for( int i = 0 ; i < n ; i ++ ){
for( int j = 0 ; j < n ; j ++ ) if( g[i][j] ) cout<<g[i][j]->wt()<<"\t"; else cout<<"NULL\t"; cout<<endl; } } }; //邻接列表实现 // 稀疏图 - 邻接表 template<typename Weight> class SparseGraph{
private: int n, m; // 节点数和边数 bool directed; // 是否为有向图 vector<vector<Edge<Weight> *> > g; // 图的具体数据 public: SparseGraph( int n , bool directed){
assert(n >= 0); this->n = n; this->m = 0; // 初始化没有任何边 this->directed = directed; // g初始化为n个空的vector, 表示每一个g[i]都为空, 即没有任和边 //实现1： g = vector<vector<Edge<Weight> *> >(n, vector<Edge<Weight> *>()); //实现2： /* for(int i=0; i<n; i++) g.push_back(vector<Edge<Weight> *>()); */ } // 析构函数 ~SparseGraph(){
for( int i = 0 ; i < n ; i ++ ) for( int j = 0 ; j < g[i].size() ; j ++ ) delete g[i][j]; } int V(){
return n;} // 返回节点个数 int E(){
return m;} // 返回边的个数 // 向图中添加一个边, 权值为weight void addEdge( int v, int w , Weight weight){
assert( v >= 0 && v < n ); assert( w >= 0 && w < n ); // 注意, 由于在邻接表的情况, 查找是否有重边需要遍历整个链表 // 我们的程序允许重边的出现 g[v].push_back(new Edge<Weight>(v, w, weight)); if( v != w && !directed ) g[w].push_back(new Edge<Weight>(w, v, weight)); m ++; } // 验证图中是否有从v到w的边 bool hasEdge( int v , int w ){
assert( v >= 0 && v < n ); assert( w >= 0 && w < n ); for( int i = 0 ; i < g[v].size() ; i ++ ) if( g[v][i]->other(v) == w ) return true; return false; } // 显示图的信息 void show(){
for( int i = 0 ; i < n ; i ++ ){
cout<<"vertex "<<i<<":\t"; for( int j = 0 ; j < g[i].size() ; j ++ ) cout<<"( to:"<<g[i][j]->w()<<",wt:"<<g[i][j]->wt()<<")\t"; cout<<endl; } } }; 5.最小生成树
找出图中一棵树，连接所有节点，并且权值之和最小 5.1 切分定理
5.2 Prim算法（利用切分定理，从一个点开始，一点点扩散，直至求出最小生成树）
//实现： // 使用Prim算法求图的最小生成树 template<typename Graph, typename Weight> class LazyPrimMST{
private: Graph &G; // 图的引用 MinHeap<Edge<Weight>> pq; // 最小堆, 算法辅助数据结构 bool *marked; // 标记数组, 在算法运行过程中标记节点i是否被访问 vector<Edge<Weight>> mst; // 最小生成树所包含的所有边 Weight mstWeight; // 最小生成树的权值 // 访问节点v void visit(int v){
assert( !marked[v] ); marked[v] = true; // 将和节点v相连接的所有未访问的边放入最小堆中 typename Graph::adjIterator adj(G,v); for( Edge<Weight>* e = adj.begin() ; !adj.end() ; e = adj.next() ) if( !marked[e->other(v)] ) pq.insert(*e); } public: LazyPrimMST(Graph &graph):G(graph), pq(MinHeap<Edge<Weight>>(graph.E())){
// 算法初始化 marked = new bool[G.V()]; for( int i = 0 ; i < G.V() ; i ++ ) marked[i] = false; mst.clear(); // Lazy Prim visit(0); while( !pq.isEmpty() ){
// 使用最小堆找出已经访问的边中权值最小的边 Edge<Weight> e = pq.extractMin(); // 如果这条边的两端都已经访问过了, 则扔掉这条边 if( marked[e.v()] == marked[e.w()] ) continue; // 否则, 这条边则应该存在在最小生成树中 mst.push_back( e ); // 访问和这条边连接的还没有被访问过的节点 if( !marked[e.v()] ) visit( e.v() ); else visit( e.w() ); } // 计算最小生成树的权值 mstWeight = mst[0].wt(); for( int i = 1 ; i < mst.size() ; i ++ ) mstWeight += mst[i].wt(); } ~LazyPrimMST(){
delete[] marked; } // 返回最小生成树的所有边 vector<Edge<Weight>> mstEdges(){
return mst; }; // 返回最小生成树的权值 Weight result(){
return mstWeight; }; }; 5.2.1 优化
IndexMinHeap:每个heap节点保存的是与该节点 横切边权值最小值 
//实现 // 使用优化的Prim算法求图的最小生成树 template<typename Graph, typename Weight> class PrimMST{
private: Graph &G; // 图的引用 IndexMinHeap<Weight> ipq; // 最小索引堆, 算法辅助数据结构 vector<Edge<Weight>*> edgeTo; // 访问的点所对应的边, 算法辅助数据结构 bool* marked; // 标记数组, 在算法运行过程中标记节点i是否被访问 vector<Edge<Weight>> mst; // 最小生成树所包含的所有边 Weight mstWeight; // 最小生成树的权值 // 访问节点v void visit(int v){
assert( !marked[v] ); marked[v] = true; // 将和节点v相连接的未访问的另一端点, 和与之相连接的边, 放入最小堆中 typename Graph::adjIterator adj(G,v); for( Edge<Weight>* e = adj.begin() ; !adj.end() ; e = adj.next() ){
int w = e->other(v); // 如果边的另一端点未被访问 if( !marked[w] ){
// 如果从没有考虑过这个端点, 直接将这个端点和与之相连接的边加入索引堆 if( !edgeTo[w] ){
edgeTo[w] = e; ipq.insert(w, e->wt()); } // 如果曾经考虑这个端点, 但现在的边比之前考虑的边更短, 则进行替换 else if( e->wt() < edgeTo[w]->wt() ){
edgeTo[w] = e; ipq.change(w, e->wt()); } } } } public: // 构造函数, 使用Prim算法求图的最小生成树 PrimMST(Graph &graph):G(graph), ipq(IndexMinHeap<double>(graph.V())){
assert( graph.E() >= 1 ); // 算法初始化 marked = new bool[G.V()]; for( int i = 0 ; i < G.V() ; i ++ ){
marked[i] = false; edgeTo.push_back(NULL); } mst.clear(); // Prim visit(0); while( !ipq.isEmpty() ){
// 使用最小索引堆找出已经访问的边中权值最小的边 // 最小索引堆中存储的是点的索引, 通过点的索引找到相对应的边 int v = ipq.extractMinIndex(); assert( edgeTo[v] ); mst.push_back( *edgeTo[v] ); visit( v ); } mstWeight = mst[0].wt(); for( int i = 1 ; i < mst.size() ; i ++ ) mstWeight += mst[i].wt(); } ~PrimMST(){
delete[] marked; } vector<Edge<Weight>> mstEdges(){
return mst; }; Weight result(){
return mstWeight; }; }; 5.3 Kruskal算法
实现： // Kruskal算法 template <typename Graph, typename Weight> class KruskalMST{
private: vector<Edge<Weight>> mst; // 最小生成树所包含的所有边 Weight mstWeight; // 最小生成树的权值 public: // 构造函数, 使用Kruskal算法计算graph的最小生成树 KruskalMST(Graph &graph){
// 将图中的所有边存放到一个最小堆中 MinHeap<Edge<Weight>> pq( graph.E() ); for( int i = 0 ; i < graph.V() ; i ++ ){
typename Graph::adjIterator adj(graph,i); for( Edge<Weight> *e = adj.begin() ; !adj.end() ; e = adj.next() ) if( e->v() < e->w() ) pq.insert(*e); } // 创建一个并查集, 来查看已经访问的节点的联通情况 UnionFind uf = UnionFind(graph.V()); while( !pq.isEmpty() && mst.size() < graph.V() - 1 ){
// 从最小堆中依次从小到大取出所有的边 Edge<Weight> e = pq.extractMin(); // 如果该边的两个端点是联通的, 说明加入这条边将产生环, 扔掉这条边 if( uf.isConnected( e.v() , e.w() ) ) continue; // 否则, 将这条边添加进最小生成树, 同时标记边的两个端点联通 mst.push_back( e ); uf.unionElements( e.v() , e.w() ); } mstWeight = mst[0].wt(); for( int i = 1 ; i < mst.size() ; i ++ ) mstWeight += mst[i].wt(); } ~KruskalMST(){
} // 返回最小生成树的所有边 vector<Edge<Weight>> mstEdges(){
return mst; }; // 返回最小生成树的权值 Weight result(){
return mstWeight; }; }; 5.4 时间复杂度
6.最短路径
最短路径问题：从一个节点到另一个节点的最短距离 （本节为单源最短路径） 6.1 dijkstra算法
前提：图中不能有负权边 一轮操作; 
二轮操作: 
三轮操作： 
四轮操作： 
实现： // Dijkstra算法求最短路径 template<typename Graph, typename Weight> class Dijkstra{
private: Graph &G; // 图的引用 int s; // 起始点 Weight *distTo; // distTo[i]存储从起始点s到i的最短路径长度 bool *marked; // 标记数组, 标记是否求得到节点i最短距离 vector<Edge<Weight>*> from; // from[i]记录最短路径中, 到达i点的边是哪一条 // 可以用来恢复整个最短路径 public: // 构造函数, 使用Dijkstra算法求最短路径 Dijkstra(Graph &graph, int s):G(graph){
// 算法初始化 assert( s >= 0 && s < G.V() ); this->s = s; distTo = new Weight[G.V()]; marked = new bool[G.V()]; for( int i = 0 ; i < G.V() ; i ++ ){
distTo[i] = Weight(); marked[i] = false; from.push_back(NULL); } // 使用索引堆记录当前找到的到达每个顶点的最短距离 IndexMinHeap<Weight> ipq(G.V()); // 对于起始点s进行初始化 distTo[s] = Weight(); from[s] = new Edge<Weight>(s, s, Weight()); ipq.insert(s, distTo[s] ); marked[s] = true; while( !ipq.isEmpty() ){
int v = ipq.extractMinIndex(); // distTo[v]就是s到v的最短距离 marked[v] = true; // 对v的所有相邻节点进行更新 typename Graph::adjIterator adj(G, v); for( Edge<Weight>* e = adj.begin() ; !adj.end() ; e = adj.next() ){
int w = e->other(v); // 如果从s点到w点的最短路径还没有找到 if( !marked[w] ){
// 如果w点以前没有访问过, // 或者访问过, 但是通过当前的v点到w点距离更短, 则进行更新 if( from[w] == NULL || distTo[v] + e->wt() < distTo[w] ){
distTo[w] = distTo[v] + e->wt(); from[w] = e; if( ipq.contain(w) ) ipq.change(w, distTo[w] ); else ipq.insert(w, distTo[w] ); } } } } } // 析构函数 ~Dijkstra(){
delete[] distTo; delete[] marked; delete from[0]; } // 返回从s点到w点的最短路径长度 Weight shortestPathTo( int w ){
assert( w >= 0 && w < G.V() ); assert( hasPathTo(w) ); return distTo[w]; } // 判断从s点到w点是否联通 bool hasPathTo( int w ){
assert( w >= 0 && w < G.V() ); return marked[w]; } // 寻找从s到w的最短路径, 将整个路径经过的边存放在vec中 void shortestPath( int w, vector<Edge<Weight>> &vec ){
assert( w >= 0 && w < G.V() ); assert( hasPathTo(w) ); // 通过from数组逆向查找到从s到w的路径, 存放到栈中 stack<Edge<Weight>*> s; Edge<Weight> *e = from[w]; while( e->v() != this->s ){
s.push(e); e = from[e->v()]; } s.push(e); // 从栈中依次取出元素, 获得顺序的从s到w的路径 while( !s.empty() ){
e = s.top(); vec.push_back( *e ); s.pop(); } } // 打印出从s点到w点的路径 void showPath(int w){
assert( w >= 0 && w < G.V() ); assert( hasPathTo(w) ); vector<Edge<Weight>> vec; shortestPath(w, vec); for( int i = 0 ; i < vec.size() ; i ++ ){
cout<<vec[i].v()<<" -> "; if( i == vec.size()-1 ) cout<<vec[i].w()<<endl; } } }; 6.1.1 优化：Bellman-Ford算法
前提：图中不能有负权环 负权环： 
// 使用BellmanFord算法求最短路径 template <typename Graph, typename Weight> class BellmanFord{
private: Graph &G; // 图的引用 int s; // 起始点 Weight* distTo; // distTo[i]存储从起始点s到i的最短路径长度 vector<Edge<Weight>*> from; // from[i]记录最短路径中, 到达i点的边是哪一条 // 可以用来恢复整个最短路径 bool hasNegativeCycle; // 标记图中是否有负权环 // 判断图中是否有负权环 bool detectNegativeCycle(){
for( int i = 0 ; i < G.V() ; i ++ ){
typename Graph::adjIterator adj(G,i); for( Edge<Weight>* e = adj.begin() ; !adj.end() ; e = adj.next() ) if( from[e->v()] && distTo[e->v()] + e->wt() < distTo[e->w()] ) return true; } return false; } public: // 构造函数, 使用BellmanFord算法求最短路径 BellmanFord(Graph &graph, int s):G(graph){
this->s = s; distTo = new Weight[G.V()]; // 初始化所有的节点s都不可达, 由from数组来表示 for( int i = 0 ; i < G.V() ; i ++ ) from.push_back(NULL); // 设置distTo[s] = 0, 并且让from[s]不为NULL, 表示初始s节点可达且距离为0 distTo[s] = Weight(); from[s] = new Edge<Weight>(s, s, Weight()); // 这里我们from[s]的内容是new出来的, 注意要在析构函数里delete掉 // Bellman-Ford的过程 // 进行V-1次循环, 每一次循环求出从起点到其余所有点, 最多使用pass步可到达的最短距离 for( int pass = 1 ; pass < G.V() ; pass ++ ){
// 每次循环中对所有的边进行一遍松弛操作 // 遍历所有边的方式是先遍历所有的顶点, 然后遍历和所有顶点相邻的所有边 for( int i = 0 ; i < G.V() ; i ++ ){
// 使用我们实现的邻边迭代器遍历和所有顶点相邻的所有边 typename Graph::adjIterator adj(G,i); for( Edge<Weight>* e = adj.begin() ; !adj.end() ; e = adj.next() ) // 对于每一个边首先判断e->v()可达 // 之后看如果e->w()以前没有到达过， 显然我们可以更新distTo[e->w()] // 或者e->w()以前虽然到达过, 但是通过这个e我们可以获得一个更短的距离, 即可以进行一次松弛操作, 我们也可以更新distTo[e->w()] if( from[e->v()] && (!from[e->w()] || distTo[e->v()] + e->wt() < distTo[e->w()]) ){
distTo[e->w()] = distTo[e->v()] + e->wt(); from[e->w()] = e; } } } hasNegativeCycle = detectNegativeCycle(); } // 析构函数 ~BellmanFord(){
delete[] distTo; delete from[s]; } // 返回图中是否有负权环 bool negativeCycle(){
return hasNegativeCycle; } // 返回从s点到w点的最短路径长度 Weight shortestPathTo( int w ){
assert( w >= 0 && w < G.V() ); assert( !hasNegativeCycle ); assert( hasPathTo(w) ); return distTo[w]; } // 判断从s点到w点是否联通 bool hasPathTo( int w ){
assert( w >= 0 && w < G.V() ); return from[w] != NULL; } // 寻找从s到w的最短路径, 将整个路径经过的边存放在vec中 void shortestPath( int w, vector<Edge<Weight>> &vec ){
assert( w >= 0 && w < G.V() ); assert( !hasNegativeCycle ); assert( hasPathTo(w) ); // 通过from数组逆向查找到从s到w的路径, 存放到栈中 stack<Edge<Weight>*> s; Edge<Weight> *e = from[w]; while( e->v() != this->s ){
s.push(e); e = from[e->v()]; } s.push(e); // 从栈中依次取出元素, 获得顺序的从s到w的路径 while( !s.empty() ){
e = s.top(); vec.push_back( *e ); s.pop(); } } // 打印出从s点到w点的路径 void showPath(int w){
assert( w >= 0 && w < G.V() ); assert( !hasNegativeCycle ); assert( hasPathTo(w) ); vector<Edge<Weight>> vec; shortestPath(w, vec); for( int i = 0 ; i < vec.size() ; i ++ ){
cout<<vec[i].v()<<" -> "; if( i == vec.size()-1 ) cout<<vec[i].w()<<endl; } } }; 6.2 时间复杂度
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/119802.html
