图论基础

柔情只为你懂 2023-08-17 17:48 194阅读 0赞

# 图 #

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

## 简单图 ##

邻接矩阵：对于一个四个节点二维矩阵，可以用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