图

图由节点和图构成； 有向图：连线有方向；不对称性； 无向图：连线无方向；是有向图的一种特殊请情况； 有权图：连线有权值； 无权图：连线无权值；

简单图

邻接矩阵：对于一个四个节点二维矩阵，可以用4*4表示相连情况；可以有向可以无向；适合稠密图 邻接表：每个节点的内容是与其相连的节点，类似链表；可以有向可以无向；适合稀疏图 main.cpp

#include <iostream> using namespace std; int main() { return 0; }

稠密图——邻接矩阵 DenseGraph.h

#ifndef INC_02_GRAPH_REPRESENTATION_DENSEGRAPH_H #define INC_02_GRAPH_REPRESENTATION_DENSEGRAPH_H #include <iostream> #include <vector> #include <cassert> using namespace std; // 稠密图 - 邻接矩阵 class DenseGraph{ private: int n, m;//图的节点数和边数 bool directed; //代表有向图和无向图 vector<vector<bool>> g; //二维矩阵，布尔型，T代表有边，F代表无边 public: DenseGraph( int n , bool directed ){ this->n = n; this->m = 0; //初始边为0 this->directed = directed; for( int i = 0 ; i < n ; i ++ ) g.push_back( vector<bool>(n, false) ); //布尔型向量，元素都是F，创建了n*n的全F邻接矩阵 } //析构，不需要释放 ~DenseGraph(){ } //返回顶点和边 int V(){ return n;} int E(){ return m;} //在v和w之间增加边 void addEdge( int v , int w ){ assert( v >= 0 && v < n ); assert( w >= 0 && w < n ); if( hasEdge( v , w ) )//如果已经是T则直接返回 return; //更改g矩阵 g[v][w] = true; if( !directed ) //如果无向，另一个也要是T g[w][v] = true; m ++; } //用此函数检验是否存在这个边 bool hasEdge( int v , int w ){ assert( v >= 0 && v < n ); assert( w >= 0 && w < n ); return g[v][w]; } }; #endif //INC_02_GRAPH_REPRESENTATION_DENSEGRAPH_H

稀疏图——邻接表 SparseGraph.h

// // Created by liuyubobobo on 9/21/16. // #ifndef INC_02_GRAPH_REPRESENTATION_SPARSEGRAPH_H #define INC_02_GRAPH_REPRESENTATION_SPARSEGRAPH_H #include <iostream> #include <vector> #include <cassert> using namespace std; // 稀疏图 - 邻接表 class SparseGraph{ private: int n, m; bool directed; vector<vector<int>> g;//储存的是int型节点编号 public: SparseGraph( int n , bool directed ){ this->n = n; this->m = 0; this->directed = directed; 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); //在v加入w if( v != w && !directed ) //是否有向，且v不等于w g[w].push_back(v); m ++; } //确定平行边 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; } }; #endif //INC_02_GRAPH_REPRESENTATION_SPARSEGRAPH_H

临边遍历——图算法中最常见的操作 在邻接矩阵中需要将此节点之外的都遍历一遍，为T的说明邻接； 使用邻接表可以直接获得这个信息 main.cpp

#include <iostream> #include "SparseGraph.h" #include "DenseGraph.h" using namespace std; int main() { int N = 20; int M = 100; srand( time(NULL) ); // Sparse Graph SparseGraph g1(N , false); for( int i = 0 ; i < M ; i ++ ){ int a = rand()%N; //随机节点 int b = rand()%N; g1.addEdge( a , b ); //添加 } // O(E) for( int v = 0 ; v < N ; v ++ ){ cout<<v<<" : "; SparseGraph::adjIterator adj( g1 , v ); //声明临边迭代器 for( int w = adj.begin() ; !adj.end() ; w = adj.next() ) cout<<w<<" "; cout<<endl; } cout<<endl; // Dense Graph DenseGraph g2(N , false); for( int i = 0 ; i < M ; i ++ ){ int a = rand()%N; int b = rand()%N; g2.addEdge( a , b ); } // O(V^2) for( int v = 0 ; v < N ; v ++ ){ cout<<v<<" : "; DenseGraph::adjIterator adj( g2 , v ); for( int w = adj.begin() ; !adj.end() ; w = adj.next() ) cout<<w<<" "; cout<<endl; } return 0; }

稠密图——邻接矩阵 DenseGraph.h

// // Created by liuyubobobo on 9/21/16. // #ifndef INC_03_VERTEX_ADJACENT_ITERATOR_DENSEGRAPH_H #define INC_03_VERTEX_ADJACENT_ITERATOR_DENSEGRAPH_H #include <iostream> #include <vector> #include <cassert> using namespace std; // 稠密图 - 邻接矩阵 class DenseGraph{ private: int n, m; bool directed; vector<vector<bool>> g; public: DenseGraph( int n , bool directed ){ this->n = n; this->m = 0; this->directed = directed; 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 ++; } bool hasEdge( int v , int w ){ assert( v >= 0 && v < n ); assert( w >= 0 && w < n ); return g[v][w]; } class adjIterator{ //迭代器 private: DenseGraph &G; int v; int index; public: adjIterator(DenseGraph &graph, int v): G(graph){ this->v = v; this->index = -1; } int begin(){ index = -1; return next(); } int next(){ for( index += 1 ; index < G.V() ; index ++ ) if( G.g[v][index] ) //进行遍历，去找为T 的元素 return index; return -1; } bool end(){ //大于节点的个数则迭代完成 return index >= G.V(); } }; }; #endif //INC_03_VERTEX_ADJACENT_ITERATOR_DENSEGRAPH_H

SpraseGraph.h

// // Created by liuyubobobo on 9/21/16. // #ifndef INC_03_VERTEX_ADJACENT_ITERATOR_SPARSEGRAPH_H #define INC_03_VERTEX_ADJACENT_ITERATOR_SPARSEGRAPH_H #include <iostream> #include <vector> #include <cassert> using namespace std; // 稀疏图 - 邻接表 class SparseGraph{ private: int n, m; bool directed; vector<vector<int>> g; public: SparseGraph( int n , bool directed ){ this->n = n; this->m = 0; this->directed = directed; 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 ++; } 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; } class adjIterator{ //相临边迭代器 private: SparseGraph &G; //存储引用 int v; int index; public: adjIterator(SparseGraph &graph, int v): G(graph){ this->v = v; this->index = 0; //迭代到哪里 } int begin(){ //迭代的第一个元素 index = 0; //初始化 if( G.g[v].size() ) //是否存在 return G.g[v][index]; return -1; } int next(){ //迭代的下一个元素 index ++; if( index < G.g[v].size() ) //是否还有 return G.g[v][index]; return -1; } bool end(){ return index >= G.g[v].size(); } }; }; #endif //INC_03_VERTEX_ADJACENT_ITERATOR_SPARSEGRAPH_H

用文件测试图算法，文件中每行表示节点相连 main.cpp

#include <iostream> #include "SparseGraph.h" #include "DenseGraph.h" #include "ReadGraph.h" using namespace std; int main() { string filename = "testG1.txt"; SparseGraph g1( 13 , false ); //初始化 ReadGraph<SparseGraph> readGraph1( g1 , filename ); //读入文件到稀疏图中 g1.show(); //显示图 cout<<endl; DenseGraph g2( 13 , false ); ReadGraph<DenseGraph> readGraph2( g2 , filename ); //稠密图 g2.show(); return 0; }

ReadGraph.h

// // Created by liuyubobobo on 9/22/16. // #ifndef INC_04_READ_GRAPH_READGRAPH_H #define INC_04_READ_GRAPH_READGRAPH_H #include <iostream> #include <string> #include <fstream> #include <sstream> #include <cassert> using namespace std; template <typename Graph> //模板类 class ReadGraph{ public: ReadGraph(Graph &graph, const string &filename){ //读图，不指定类型 ifstream file(filename); //用名字读文件 string line; //一行一行读取 int V, E; assert( file.is_open() ); //确保成功打开 assert( getline(file, line) ); //得到第一行 stringstream ss(line); ss>>V>>E; //从ss中解析处V和E assert( V == graph.V() ); //确保文件点数和图点属性相同 for( int i = 0 ; i < E ; i ++ ){ assert( getline(file, line) ); //一行一行读 stringstream ss(line); int a,b; ss>>a>>b; //放入ab中 assert( a >= 0 && a < V ); //检查越界 assert( b >= 0 && b < V ); graph.addEdge( a , b ); //将ab边加入图中 } } }; #endif //INC_04_READ_GRAPH_READGRAPH_H

深度优先遍历 可以得到联通分量

Components.h

// // Created by liuyubobobo on 9/22/16. // #ifndef INC_05_DFS_AND_COMPONENTS_COMPONENTS_H #define INC_05_DFS_AND_COMPONENTS_COMPONENTS_H #include <iostream> #include <cassert> using namespace std; template <typename Graph> //模板类 class Component{ private: Graph &G; bool *visited; //记录是否被访问过 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; } bool isConnected( int v , int w ){ assert( v >= 0 && v < G.V() ); assert( w >= 0 && w < G.V() ); return id[v] == id[w]; } }; #endif //INC_05_DFS_AND_COMPONENTS_COMPONENTS_H

在深度遍历的过程中同时也创造了路径，将其存储下来 main.cpp

#include <iostream> #include "SparseGraph.h" #include "DenseGraph.h" #include "ReadGraph.h" #include "Path.h" using namespace std; int main() { string filename = "testG2.txt"; SparseGraph g = SparseGraph(7, false); ReadGraph<SparseGraph> readGraph(g, filename); g.show(); cout<<endl; Path<SparseGraph> dfs(g,0); cout<<"DFS : "; dfs.showPath(6); return 0; }

path.h

// // Created by liuyubobobo on 9/22/16. // #ifndef INC_06_FINDING_A_PATH_PATH_H #define INC_06_FINDING_A_PATH_PATH_H #include <vector> #include <stack> #include <iostream> #include <cassert> using namespace std; template <typename Graph> class Path{ //类 private: Graph &G; int s; bool* visited; int * from; //存储最初的节点 void dfs( int v ){ visited[v] = true; typename Graph::adjIterator adj(G, v); for( int i = adj.begin() ; !adj.end() ; i = adj.next() ){ if( !visited[i] ){ from[i] = v; //如果相邻的节点未方位，将将from维护到v dfs(i); } } } public: Path(Graph &graph, int s):G(graph){ //s到其他店的路径 // 算法初始化 assert( s >= 0 && s < G.V() ); //G初始化 visited = new bool[G.V()]; from = new int[G.V()]; for( int i = 0 ; i < G.V() ; i ++ ){ visited[i] = false; //初始化 from[i] = -1; } this->s = s; // 寻路算法 dfs(s); } ~Path(){ delete [] visited; delete [] from; } bool hasPath(int w){ assert( w >= 0 && w < G.V() ); //检查越界 return visited[w]; } void path(int w, vector<int> &vec){ stack<int> s; //倒退时使用栈，临时存放 int p = w; while( p != -1 ){ s.push(p); //推入p p = from[p]; } vec.clear(); //清空 while( !s.empty() ){ //推到了元节点 vec.push_back( s.top() ); //栈顶 s.pop(); } } void showPath(int w){ //打印s到w 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<<" -> "; } } }; #endif //INC_06_FINDING_A_PATH_PATH_H

广度优先遍历和最短路径； 广度优先便利求出了无权图的最短路径； main.cpp

#include <iostream> #include "SparseGraph.h" #include "DenseGraph.h" #include "ReadGraph.h" #include "Path.h" #include "ShortestPath.h" using namespace std; int main() { string filename = "testG2.txt"; SparseGraph g = SparseGraph(7, false); ReadGraph<SparseGraph> readGraph(g, filename); g.show(); cout<<endl; Path<SparseGraph> dfs(g,0); cout<<"DFS : "; dfs.showPath(6); ShortestPath<SparseGraph> bfs(g,0); cout<<"BFS : "; bfs.showPath(6); return 0; }

ShorteatPath.h

// // Created by liuyubobobo on 9/22/16. // #ifndef INC_07_BFS_AND_SHORTEST_PATH_SHORTESTPATH_H #define INC_07_BFS_AND_SHORTEST_PATH_SHORTESTPATH_H #include <vector> #include <queue> #include <stack> #include <iostream> #include <cassert> using namespace std; template <typename Graph> class ShortestPath{ private: Graph &G; int s; bool *visited; int *from; int *ord; //会记录最短距离 public: 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; queue<int> q; // 无向图最短路径算法 q.push( s ); //向队列中推入远点 visited[s] = true; //不需要再入队 ord[s] = 0; //到自己的距离为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; //最短距加1 } } } ~ShortestPath(){ delete [] visited; delete [] from; delete [] ord; } bool hasPath(int w){ assert( w >= 0 && w < G.V() ); return visited[w]; } void path(int w, vector<int> &vec){ assert( w >= 0 && w < G.V() ); stack<int> s; int p = w; while( p != -1 ){ s.push(p); p = from[p]; } vec.clear(); while( !s.empty() ){ vec.push_back( s.top() ); s.pop(); } } 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<<" -> "; } } int length(int w){ //查询最短路径的长度 assert( w >= 0 && w < G.V() ); return ord[w]; } }; #endif //INC_07_BFS_AND_SHORTEST_PATH_SHORTESTPATH_H

带权图 之间的邻接矩阵的元素为布尔值，现在可以是数字型，代表权值； 邻接表变成字典型，包括节点以及权值 Edge.h

// // Created by liuyubobobo on 9/23/16. // #ifndef INC_01_WEIGHTED_GRAPH_EDGE_H #define INC_01_WEIGHTED_GRAPH_EDGE_H #include <iostream> #include <cassert> using namespace std; template<typename Weight> class Edge{ private: int a,b; //默认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(); } }; #endif //INC_01_WEIGHTED_GRAPH_EDGE_H

DenseGraph.h

// // Created by liuyubobobo on 9/23/16. // #ifndef INC_01_WEIGHTED_GRAPH_DENSEGRAPH_H #define INC_01_WEIGHTED_GRAPH_DENSEGRAPH_H #include <iostream> #include <vector> #include <cassert> #include "Edge.h" using namespace std; // 稠密图 - 邻接矩阵 template <typename Weight>//模板类 class DenseGraph{ private: int n, m; bool directed; vector<vector<Edge<Weight> *>> g; public: DenseGraph( int n , bool directed){ this->n = n; this->m = 0; this->directed = directed; 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;} void addEdge( int v, int w , Weight weight ){ assert( v >= 0 && v < n ); assert( w >= 0 && w < n ); if( hasEdge( v , w ) ){ delete g[v][w]; if( !directed ) delete g[w][v]; m --; //维护 } g[v][w] = new Edge<Weight>(v, w, weight); //加入权值参数 if( !directed ) g[w][v] = new Edge<Weight>(w, v, weight); //无向 m ++; //维护 } 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; } } class adjIterator{ private: DenseGraph &G; int v; int index; public: adjIterator(DenseGraph &graph, int v): G(graph){ this->v = v; this->index = -1; } Edge<Weight>* begin(){ index = -1; return next(); } Edge<Weight>* next(){ for( index += 1 ; index < G.V() ; index ++ ) if( G.g[v][index] ) return G.g[v][index]; return NULL; } bool end(){ return index >= G.V(); } }; }; #endif //INC_01_WEIGHTED_GRAPH_DENSEGRAPH_H

SparesGraph.h

// // Created by liuyubobobo on 9/23/16. // #ifndef INC_01_WEIGHTED_GRAPH_SPARSEGRAPH_H #define INC_01_WEIGHTED_GRAPH_SPARSEGRAPH_H #include <iostream> #include <vector> #include <cassert> #include "Edge.h" using namespace std; // 稀疏图 - 邻接表 template<typename Weight> //模板类 class SparseGraph{ private: int n, m; bool directed; vector<vector<Edge<Weight> *>> g; public: SparseGraph( int n , bool directed){ this->n = n; this->m = 0; this->directed = directed; 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;} 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 ++; } 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 ) //另外一个点是否是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; } } class adjIterator{ private: SparseGraph &G; int v; int index; public: adjIterator(SparseGraph &graph, int v): G(graph){ this->v = v; this->index = 0; } Edge<Weight>* begin(){ index = 0; if( G.g[v].size() ) return G.g[v][index]; return NULL; } Edge<Weight>* next(){ index += 1; if( index < G.g[v].size() ) return G.g[v][index]; return NULL; } bool end(){ return index >= G.g[v].size(); } }; }; #endif //INC_01_WEIGHTED_GRAPH_SPARSEGRAPH_H

最小生成树问题 带权图中各个节点均连通，同时总权值最小； 找V-1条边，连接V个节点； 切分定理：给定任意切分，横切边中权值最小的边必然属于最小生成树！ 如果一个边的两个端点，属于切分不同的两边，这个边成为横切边； LazyPrim实现方法：选定一个节点后，使用圆切，相邻的边都放入最小堆中，取出最小的权值作为最小生成树的边；找到新的节点，重复操作，依然把新的相临边加入最小堆中；取出来的最小边的两个端点已经遍历过了，则直接扔掉；知道最后一条边取出完成整个过程。 mian.cpp

#include <iostream> #include <iomanip> #include "DenseGraph.h" #include "SparseGraph.h" #include "ReadGraph.h" #include "LazyPrimMST.h" using namespace std; int main() { string filename = "testG1.txt"; int V = 8; SparseGraph<double> g = SparseGraph<double>(V, false); ReadGraph<SparseGraph<double>, double> readGraph(g, filename); // Test Lazy Prim MST cout<<"Test Lazy Prim MST:"<<endl; LazyPrimMST<SparseGraph<double>, double> lazyPrimMST(g); vector<Edge<double>> mst = lazyPrimMST.mstEdges(); for( int i = 0 ; i < mst.size() ; i ++ ) cout<<mst[i]<<endl; cout<<"The MST weight is: "<<lazyPrimMST.result()<<endl; cout<<endl; return 0; }

LazyPrimMST.h

// // Created by liuyubobobo on 9/24/16. // #ifndef INC_03_LAZY_PRIM_LAZYPRIMMST_H #define INC_03_LAZY_PRIM_LAZYPRIMMST_H #include <iostream> #include <vector> #include <cassert> #include "Edge.h" #include "MinHeap.h" using namespace std; template<typename Graph, typename Weight> //模板类 class LazyPrimMST{ private: Graph &G; //传入图 MinHeap<Edge<Weight>> pq; //在最小堆中给边开空间 bool *marked; //节点是否被标记过 vector<Edge<Weight>> mst; //给mark开空间 Weight mstWeight; //都是edge类型 void visit(int v){ assert( !marked[v] ); //未标记 marked[v] = true; //转成true 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); //访问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(); //计算最小的权值，加和为matWeigh 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; //返回最小生成树的边 }; }; #endif //INC_03_LAZY_PRIM_LAZYPRIMMST_H

借助最小堆

MinHeap.h

// // Created by liuyubobobo on 9/24/16. // #ifndef INC_03_LAZY_PRIM_MINHEAP_H #define INC_03_LAZY_PRIM_MINHEAP_H #include <algorithm> #include <cassert> using namespace std; template<typename Item> class MinHeap{ private: Item *data; int count; int capacity; void shiftUp(int k){ while( k > 1 && data[k/2] > data[k] ){ swap( data[k/2], data[k] ); k /= 2; } } void shiftDown(int k){ while( 2*k <= count ){ int j = 2*k; if( j+1 <= count && data[j+1] < data[j] ) j ++; if( data[k] <= data[j] ) break; swap( data[k] , data[j] ); k = j; } } public: MinHeap(int capacity){ data = new Item[capacity+1]; count = 0; this->capacity = capacity; } MinHeap(Item arr[], int n){ data = new Item[n+1]; capacity = n; for( int i = 0 ; i < n ; i ++ ) data[i+1] = arr[i]; count = n; for( int i = count/2 ; i >= 1 ; i -- ) shiftDown(i); } ~MinHeap(){ delete[] data; } int size(){ return count; } bool isEmpty(){ return count == 0; } void insert(Item item){ assert( count + 1 <= capacity ); data[count+1] = item; shiftUp(count+1); count ++; } Item extractMin(){ assert( count > 0 ); Item ret = data[1]; swap( data[1] , data[count] ); count --; shiftDown(1); return ret; } Item getMin(){ assert( count > 0 ); return data[1]; } void show(){ cout<<"| "; for( int i = 1 ; i <= count ; i ++ ) cout<<data[i]->wt()/*<<","<<data[i]*/<<" | "; cout<<endl; } }; #endif //INC_03_LAZY_PRIM_MINHEAP_H

prim的优化，从初始节点开始，将所有横切边的权值加入最小索引堆（长度等于节点数）中，最小的当做最小生成树；再看下一个节点的所有横切边的权值，如果比之前数组中的权值小，则更新权值；知道所有节点都被访问后，留下的的权值就是最小生成树的权值。时间复杂度下降。 main_performance.cpp

#include <iostream> #include <iomanip> #include <vector> #include <ctime> #include <string> #include "DenseGraph.h" #include "SparseGraph.h" #include "ReadGraph.h" #include "LazyPrimMST.h" #include "PrimMST.h" using namespace std; int main() { string filename1 = "testG1.txt"; //节点数量逐渐增加 int V1 = 8; string filename2 = "testG2.txt"; int V2 = 250; string filename3 = "testG3.txt"; int V3 = 1000; string filename4 = "testG4.txt"; int V4 = 10000; // string filename5 = "testG5.txt"; // int V5 = 1000000; SparseGraph<double> g1 = SparseGraph<double>(V1, false); ReadGraph<SparseGraph<double>,double> readGraph1(g1, filename1); cout<<filename1<<" load successfully."<<endl; SparseGraph<double> g2 = SparseGraph<double>(V2, false); ReadGraph<SparseGraph<double>,double> readGraph2(g2, filename2); cout<<filename2<<" load successfully."<<endl; SparseGraph<double> g3 = SparseGraph<double>(V3, false); ReadGraph<SparseGraph<double>,double> readGraph3(g3, filename3); cout<<filename3<<" load successfully."<<endl; SparseGraph<double> g4 = SparseGraph<double>(V4, false); ReadGraph<SparseGraph<double>,double> readGraph4(g4, filename4); cout<<filename4<<" load successfully."<<endl; // SparseGraph<double> g5 = SparseGraph<double>(V5, false); // ReadGraph<SparseGraph<double>,double> readGraph5(g5, filename5); // cout<<filename5<<" load successfully."<<endl; cout<<endl; clock_t startTime, endTime; // Test Lazy Prim MST cout<<"Test Lazy Prim MST:"<<endl; startTime = clock(); LazyPrimMST<SparseGraph<double>, double> lazyPrimMST1(g1); endTime = clock(); cout<<"Test for G1: "<<(double)(endTime-startTime)/CLOCKS_PER_SEC<<" s."<<endl; startTime = clock(); LazyPrimMST<SparseGraph<double>, double> lazyPrimMST2(g2); endTime = clock(); cout<<"Test for G2: "<<(double)(endTime-startTime)/CLOCKS_PER_SEC<<" s."<<endl; startTime = clock(); LazyPrimMST<SparseGraph<double>, double> lazyPrimMST3(g3); endTime = clock(); cout<<"Test for G3: "<<(double)(endTime-startTime)/CLOCKS_PER_SEC<<" s."<<endl; startTime = clock(); LazyPrimMST<SparseGraph<double>, double> lazyPrimMST4(g4); endTime = clock(); cout<<"Test for G4: "<<(double)(endTime-startTime)/CLOCKS_PER_SEC<<" s."<<endl; // startTime = clock(); // LazyPrimMST<SparseGraph<double>, double> lazyPrimMST5(g5); // endTime = clock(); // cout<<"Test for G5: "<<(double)(endTime-startTime)/CLOCKS_PER_SEC<<" s."<<endl; cout<<endl; // Test Prim MST cout<<"Test Prim MST:"<<endl; startTime = clock(); PrimMST<SparseGraph<double>, double> PrimMST1(g1); endTime = clock(); cout<<"Test for G1: "<<(double)(endTime-startTime)/CLOCKS_PER_SEC<<" s."<<endl; startTime = clock(); PrimMST<SparseGraph<double>, double> PrimMST2(g2); endTime = clock(); cout<<"Test for G2: "<<(double)(endTime-startTime)/CLOCKS_PER_SEC<<" s."<<endl; startTime = clock(); PrimMST<SparseGraph<double>, double> PrimMST3(g3); endTime = clock(); cout<<"Test for G3: "<<(double)(endTime-startTime)/CLOCKS_PER_SEC<<" s."<<endl; startTime = clock(); PrimMST<SparseGraph<double>, double> PrimMST4(g4); endTime = clock(); cout<<"Test for G4: "<<(double)(endTime-startTime)/CLOCKS_PER_SEC<<" s."<<endl; // startTime = clock(); // PrimMST<SparseGraph<double>, double> PrimMST5(g5); // endTime = clock(); // cout<<"Test for G5: "<<(double)(endTime-startTime)/CLOCKS_PER_SEC<<" s."<<endl; cout<<endl; return 0; }

primMST.h

// // Created by liuyubobobo on 9/26/16. // #ifndef INC_05_IMPLEMENTATION_OF_OPTIMIZED_PRIM_ALGORITHM_PRIMMST_H #define INC_05_IMPLEMENTATION_OF_OPTIMIZED_PRIM_ALGORITHM_PRIMMST_H #include <iostream> #include <vector> #include <cassert> #include "Edge.h" #include "IndexMinHeap.h" using namespace std; template<typename Graph, typename Weight> class PrimMST{ private: Graph &G;//图的引用 vector<Edge<Weight>> mst; bool* marked; //是否标记 IndexMinHeap<Weight> ipq; //最小索引堆 vector<Edge<Weight>*> edgeTo; //最短的横切边 Weight mstWeight; void visit(int v){ assert( !marked[v] ); //之前没有访问 marked[v] = true; //标记 typename Graph::adjIterator adj(G,v); //临边迭代器 for( Edge<Weight>* e = adj.begin() ; !adj.end() ; e = adj.next() ){ int w = e->other(v); //相邻的是w 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: // assume graph is connected 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(); visit(0); //从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; }; }; #endif //INC_05_IMPLEMENTATION_OF_OPTIMIZED_PRIM_ALGORITHM_PRIMMST_H

使用最小索引堆代替最小堆 IndexMinHeap.h

// // Created by liuyubobobo on 9/26/16. // #ifndef INC_05_IMPLEMENTATION_OF_OPTIMIZED_PRIM_ALGORITHM_INDEXMINHEAP_H #define INC_05_IMPLEMENTATION_OF_OPTIMIZED_PRIM_ALGORITHM_INDEXMINHEAP_H #include <iostream> #include <algorithm> #include <cassert> using namespace std; template<typename Item> class IndexMinHeap{ private: Item *data; int *indexes; int *reverse; int count; int capacity; void shiftUp( int k ){ while( k > 1 && data[indexes[k/2]] > data[indexes[k]] ){ swap( indexes[k/2] , indexes[k] ); reverse[indexes[k/2]] = k/2; reverse[indexes[k]] = k; k /= 2; } } void shiftDown( int k ){ while( 2*k <= count ){ int j = 2*k; if( j + 1 <= count && data[indexes[j]] > data[indexes[j+1]] ) j += 1; if( data[indexes[k]] <= data[indexes[j]] ) break; swap( indexes[k] , indexes[j] ); reverse[indexes[k]] = k; reverse[indexes[j]] = j; k = j; } } public: IndexMinHeap(int capacity){ data = new Item[capacity+1]; indexes = new int[capacity+1]; reverse = new int[capacity+1]; for( int i = 0 ; i <= capacity ; i ++ ) reverse[i] = 0; count = 0; this->capacity = capacity; } ~IndexMinHeap(){ delete[] data; delete[] indexes; delete[] reverse; } int size(){ return count; } bool isEmpty(){ return count == 0; } void insert(int index, Item item){ assert( count + 1 <= capacity ); assert( index + 1 >= 1 && index + 1 <= capacity ); index += 1; data[index] = item; indexes[count+1] = index; reverse[index] = count+1; count++; shiftUp(count); } Item extractMin(){ assert( count > 0 ); Item ret = data[indexes[1]]; swap( indexes[1] , indexes[count] ); reverse[indexes[count]] = 0; reverse[indexes[1]] = 1; count--; shiftDown(1); return ret; } int extractMinIndex(){ assert( count > 0 ); int ret = indexes[1] - 1; swap( indexes[1] , indexes[count] ); reverse[indexes[count]] = 0; reverse[indexes[1]] = 1; count--; shiftDown(1); return ret; } Item getMin(){ assert( count > 0 ); return data[indexes[1]]; } int getMinIndex(){ assert( count > 0 ); return indexes[1]-1; } bool contain( int index ){ return reverse[index+1] != 0; } Item getItem( int index ){ assert( contain(index) ); return data[index+1]; } void change( int index , Item newItem ){ assert( contain(index) ); index += 1; data[index] = newItem; shiftUp( reverse[index] ); shiftDown( reverse[index] ); } }; #endif //INC_05_IMPLEMENTATION_OF_OPTIMIZED_PRIM_ALGORITHM_INDEXMINHEAP_H

Kruska算法：直接去取最短的边，一定是最小生成树的，只要不变成环就可以；判断是否成环使用并查集就行，使用UnionFind快速判断环。 UF.h

// // Created by liuyubobobo on 9/26/16. // #ifndef INC_06_KRUSKAL_ALGORITHM_UF_H #define INC_06_KRUSKAL_ALGORITHM_UF_H #include <iostream> #include <cassert> using namespace std; // Quick Union + rank + path compression class UnionFind{ private: int* parent; int* rank; int count; public: UnionFind(int count){ parent = new int[count]; rank = new int[count]; this->count = count; for( int i = 0 ; i < count ; i ++ ){ parent[i] = i; rank[i] = 1; } } ~UnionFind(){ delete[] parent; delete[] rank; } int size(){ return count; } bool isConnected( int p , int q ){ return find(p) == find(q); } int find(int p){ assert( p >= 0 && p < count ); // path compression 1 while( p != parent[p] ){ parent[p] = parent[parent[p]]; p = parent[p]; } return p; } void unionElements(int p, int q){ int pRoot = find(p); int qRoot = find(q); if( pRoot == qRoot ) return; if( rank[pRoot] < rank[qRoot] ) parent[pRoot] = qRoot; else if( rank[qRoot] < rank[pRoot]) parent[qRoot] = pRoot; else{ // rank[pRoot] == rank[qRoot] parent[pRoot] = qRoot; rank[qRoot] ++; } } void show(){ for( int i = 0 ; i < count ; i ++ ) cout<<i<<" : "<<parent[i]<<endl; } }; #endif //INC_06_KRUSKAL_ALGORITHM_UF_H

KruskaIMST.h

// // Created by liuyubobobo on 9/26/16. // #ifndef INC_06_KRUSKAL_ALGORITHM_KRUSKALMST_H #define INC_06_KRUSKAL_ALGORITHM_KRUSKALMST_H #include <iostream> #include <vector> #include "MinHeap.h" #include "UF.h" #include "Edge.h" using namespace std; template <typename Graph, typename Weight> class KruskalMST{ private: vector<Edge<Weight>> mst; //最小生成树 Weight mstWeight; //权值 public: 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); //放入pq中 } 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; }; }; #endif //INC_06_KRUSKAL_ALGORITHM_KRUSKALMST_H

如果横切边有相等的边，可能会出现多个最小生成树存在； Vyssotsky’s Algorithm:将边逐渐添加到生成树中，一旦形成环，删除环中权值最大的边;

最短路径问题 一个节点到其他所有节点的路径最小——最小路径树； 上一章求得是所有节点之间的路径之和最小； 松弛操作：找到一条看似更松更复杂的路径然而权值却是最小的； 松弛算法是最小路径最核心的问题 Dijkstra算法 前提：不能有负权边； 标识起点，访问所有临边，可以找到最短边，找到其抵达的节点，这条边就是原点和这个节点之间的最短路径；再看新节点的临边，临边到达的节点和原点的距离可以进行比较和更新；再用最短临边所到达的节点开始进行新的松弛操作，看看以这个节点作为中转点所到达的节点能够有更短的路径； 依旧使用最小索引堆的结构，不断更新最小索引堆的权值

Dijkstra.h

// // Created by liuyubobobo on 9/28/16. // #ifndef INC_03_IMPLEMENTATION_OF_DIJKSTRA_DIJKSTRA_H #define INC_03_IMPLEMENTATION_OF_DIJKSTRA_DIJKSTRA_H #include <iostream> #include <vector> #include <stack> #include "Edge.h" #include "IndexMinHeap.h" using namespace std; template<typename Graph, typename Weight> class Dijkstra{ private: Graph &G; //引用 int s; //元节点 Weight *distTo; //原点到每个节点的距离 bool *marked; //标识 vector<Edge<Weight>*> from; //记录哪里来的 public: Dijkstra(Graph &graph, int s):G(graph){ 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()); // start dijkstra distTo[s] = Weight(); //原点s初始化，调用模板默认函数 ipq.insert(s, distTo[s] ); //放入最短路径 marked[s] = true;//标记s while( !ipq.isEmpty() ){ int v = ipq.extractMinIndex(); //最近的节点 // distTo[v]就是s到v的最短距离 marked[v] = true; //标识 //cout<<v<<endl; typename Graph::adjIterator adj(G, v); //对v进行松弛操作 for( Edge<Weight>* e = adj.begin() ; !adj.end() ; e = adj.next() ){ int w = e->other(v); if( !marked[w] ){ if( from[w] == NULL || distTo[v] + e->wt() < distTo[w] ){ //w没访问过，或者v的路径更小，则要进行松弛操作 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; } Weight shortestPathTo( int w ){ assert( w >= 0 && w < G.V() ); return distTo[w]; } bool hasPathTo( int w ){ assert( w >= 0 && w < G.V() ); return marked[w]; } //最短路径的边 void shortestPath( int w, vector<Edge<Weight>> &vec ){ assert( w >= 0 && w < G.V() ); stack<Edge<Weight>*> s; //先入栈再出栈 Edge<Weight> *e = from[w]; while( e->v() != this->s ){ s.push(e); e = from[e->v()]; } s.push(e); while( !s.empty() ){ e = s.top(); vec.push_back( *e ); s.pop(); } } void showPath(int w){ assert( w >= 0 && w < G.V() ); 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; } } }; #endif //INC_03_IMPLEMENTATION_OF_DIJKSTRA_DIJKSTRA_H

处理负权边 BellmanFor单源最短路径算法 前提：图中不能有负权环 从一点到另外一点的最短路径，最多经过所有的V个顶点线，有V-1条边； 对一个点的一次松弛操作，就是找到经过这个点的另外一条路径，多一条边； BellmanFor.h

// // Created by liuyubobobo on 9/28/16. // #ifndef INC_05_IMPLEMENTATION_OF_BELLMAN_FORD_BELLMANFORD_H #define INC_05_IMPLEMENTATION_OF_BELLMAN_FORD_BELLMANFORD_H #include <stack> #include <vector> #include "Edge.h" using namespace std; template <typename Graph, typename Weight> class BellmanFord{ private: Graph &G; int s; Weight* distTo; vector<Edge<Weight>*> from; 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->w()] || distTo[e->v()] + e->wt() < distTo[e->w()] ) return true; } return false; } public: BellmanFord(Graph &graph, int s):G(graph){ this->s = s; distTo = new Weight[G.V()]; for( int i = 0 ; i < G.V() ; i ++ ){ from.push_back(NULL); } // Bellman-Ford distTo[s] = Weight(); //默认构造函数 for( int pass = 1 ; pass < G.V() ; pass ++ ){ // Relaxation for( int i = 0 ; i < G.V() ; i ++ ){ //遍历所有点对每个点的临边进行遍历 typename Graph::adjIterator adj(G,i); //迭代器，e表示临边 for( Edge<Weight>* e = adj.begin() ; !adj.end() ; e = adj.next() ) if( !from[e->w()] || distTo[e->v()] + e->wt() < distTo[e->w()] ){ //e到达w或者比较权值 distTo[e->w()] = distTo[e->v()] + e->wt(); //更新 from[e->w()] = e; //更新 } } } //辅助函数，在做一轮松弛操作 hasNegativeCycle = detectNegativeCycle(); } ~BellmanFord(){ delete[] distTo; } //负权环 bool negativeCycle(){ return hasNegativeCycle; } Weight shortestPathTo( int w ){ assert( w >= 0 && w < G.V() ); assert( !hasNegativeCycle ); return distTo[w]; } //s到w上的边 bool hasPathTo( int w ){ assert( w >= 0 && w < G.V() ); return from[w] != NULL; } void shortestPath( int w, vector<Edge<Weight>> &vec ){ assert( w >= 0 && w < G.V() ); assert( !hasNegativeCycle ); stack<Edge<Weight>*> s; Edge<Weight> *e = from[w]; while( e->v() != this->s ){ s.push(e); e = from[e->v()]; } s.push(e); while( !s.empty() ){ e = s.top(); vec.push_back( *e ); s.pop(); } } void showPath(int w){ assert( w >= 0 && w < G.V() ); assert( !hasNegativeCycle ); 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; } } }; #endif //INC_05_IMPLEMENTATION_OF_BELLMAN_FORD_BELLMANFORD_H