图论 Graph Theory

图论并不是研究图画。而是研究由节点和边所构成的数学模型

万事开头难，虽然看上去很复杂，但是慢慢学习深入之后会体会到他的魅力

很多信息之间的联系都可以使用图来表示。数据可视化

• 交通运输
• 社交网络
• 互联网
• 工作安排
• 脑区活动
• 程序状态执行

每个节点是城市，边是道路。点是航站楼，边是航线.

社交网络 - 人 & 好友关系 电影 & 电影相似程度

互联网 域名 域名跳转

工作安排 ：先后程度

自动机

图的分类：

• 无向图（Undirected Graph）
• 有向图（Directed Graph）

人和人认识就是边。

自动机转移有方向

以无向图为主。无向图是一种特殊的有向图

• 无权图
• 有权图

边:认识不认识。 好友度

边带值：相似程度 & 路长

图的连通性：

可以看做是三张图。也可以视为一个。

图不是完全连通的。

简单图（simple Graph）：

考虑最小生成树。连通性。这两种边意义不大

简单图：不包含。

图的表示

对于边的表示采用什么样的数据结构：

n个节点 就是一个n行n列的矩阵，无向图对角线对称：1表示连通。0表示没通

有向图的矩阵表示：

邻接表：

对于每个顶点只表达与这个顶点相连接的信息

每一行都是一个链表，存放了对这一行而言相连的节点。

优点：存储空间小

邻接表适合表示稀疏图 (Sparse Graph)

邻接矩阵适合表示稠密图 (Dense Graph)

邻接表适合表示稀疏图，邻接矩阵适合表示稠密图。

多少：边多。

边的个数 与 能拥有的最大边的个数对比。

如下图就是一个稀疏图：

所有的点之间都有边。

每个电影和其他所有电影之间的相似度。不管相似大小都是连接的边。

编码：

// 稠密图 - 邻接矩阵class DenseGraph{private:    int n, m;       // 节点数和边数    bool directed;  // 是否为有向图    vector
     
      
       > 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, 表示没有任和边        //g = vector
       
        
         >(n, vector
         
          (n, false));          for (int i = 0; i < n; ++i) {            g.push_back(vector
          
           (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]; }};
          
         
        
       
      
     

addedge的时候已经去除了平行边的概念。因为如果有边之间return

O(1)来判断是否有边

稀疏图编码

// 稀疏图 - 邻接表class SparseGraph{private:    int n, m;       // 节点数和边数    bool directed;  // 是否为有向图    vector
     
      
       > g;  // 图的具体数据public:    // 构造函数    SparseGraph( int n , bool directed ){        assert( n >= 0 );        this->n = n;        this->m = 0;    // 初始化没有任何边        this->directed = directed;        // g初始化为n个空的vector, 表示每一个g[i]都为空, 即没有任和边        //g = vector
       
        
         >(n, vector
         
          ());        for (int i = 0; i < n; ++i) {            g.push_back(vector
          
           ()); } } ~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; }};
          
         
        
       
      
     

邻接表取消平行边复杂度度过大。

邻接表的优势

遍历邻边 - 图算法中最常见的操作

// 邻边迭代器, 传入一个图和一个顶点,    // 迭代在这个图中和这个顶点向连的所有顶点    class adjIterator{    private:        SparseGraph &G; // 图G的引用        int v;        int index;    public:        // 构造函数        adjIterator(SparseGraph &graph, int v): G(graph){            this->v = v;            this->index = 0;        }        ~adjIterator(){}        // 返回图G中与顶点v相连接的第一个顶点        int begin(){            index = 0;            if( G.g[v].size() )                return G.g[v][index];            // 若没有顶点和v相连接, 则返回-1            return -1;        }        // 返回图G中与顶点v相连接的下一个顶点        int next(){            index ++;            if( index < G.g[v].size() )                return G.g[v][index];            // 若没有顶点和v相连接, 则返回-1            return -1;        }        // 查看是否已经迭代完了图G中与顶点v相连接的所有顶点        bool end(){            return index >= G.g[v].size();        }    };     // 邻边迭代器, 传入一个图和一个顶点,    // 迭代在这个图中和这个顶点向连的所有顶点    class adjIterator{    private:        DenseGraph &G;  // 图G的引用        int v;        int index;    public:        // 构造函数        adjIterator(DenseGraph &graph, int v): G(graph){            assert( v >= 0 && v < G.n );            this->v = v;            this->index = -1;   // 索引从-1开始, 因为每次遍历都需要调用一次next()        }        ~adjIterator(){}        // 返回图G中与顶点v相连接的第一个顶点        int begin(){            // 索引从-1开始, 因为每次遍历都需要调用一次next()            index = -1;            return next();        }        // 返回图G中与顶点v相连接的下一个顶点        int next(){            // 从当前index开始向后搜索, 直到找到一个g[v][index]为true            for( index += 1 ; index < G.V() ; index ++ )                if( G.g[v][index] )                    return index;            // 若没有顶点和v相连接, 则返回-1            return -1;        }        // 查看是否已经迭代完了图G中与顶点v相连接的所有顶点        bool end(){            return index >= G.V();        }    };

算法封装成类

用文件来表示

第一行有多少节点，多少边。然后节点对：表示这两个节点间有边。

template 
     
      class ReadGraph{public:    // 从文件filename中读取图的信息, 存储进图graph中    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;        assert( V == graph.V() );        // 读取每一条边的信息        for( int i = 0 ; i < E ; i ++ ){            assert( getline(file, line) );            stringstream ss(line);            int a,b;            ss>>a>>b;            assert( a >= 0 && a < V );            assert( b >= 0 && b < V );            graph.addEdge( a , b );        }    }};
     

运行结果：

图的遍历

• 深度优先遍历
• 广度优先遍历

一个点往下试。记录是否遍历过。

0-1-2-5-3-4-6

遍历完成后看没遍历过的点

// 求无权图的联通分量template 
     
      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];    }};
     

main.cpp

// 测试图的联通分量算法int main() {    // TestG1.txt    string filename1 = "testG1.txt";    SparseGraph g1 = SparseGraph(13, false);    ReadGraph
     
       readGraph1(g1, filename1);    Component
      
        component1(g1);    cout<<"TestG1.txt, Component Count: "<
       
        <
        
          readGraph2(g2, filename2);    Component
         
           component2(g2);    cout<<"TestG2.txt, Component Count: "<
          
           <
          
         
        
       
      
     

运行结果：

求出连通分量，可以求出两个结点是否相连

添加id来记录。

int *id;        // 每个节点所对应的联通分量标记

并查集只能让我们知道两个结点是否相连。而路径需要图论来解决

获得两点间的一条路径。

深度优先获得一条路径。遍历的同时保存是从哪遍历过来的。

int * from;     // 记录路径, from[i]表示查找的路径上i的上一个节点

// 路径查询template 
     
      class Path{private:    Graph &G;   // 图的引用    int s;      // 起始点    bool* visited;  // 记录dfs的过程中节点是否被访问    int * from;     // 记录路径, from[i]表示查找的路径上i的上一个节点    // 图的深度优先遍历    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;                dfs(i);            }        }    }public:    // 构造函数, 寻路算法, 寻找图graph从s点到其他点的路径    Path(Graph &graph, int s):G(graph){        // 算法初始化        assert( s >= 0 && s < G.V() );        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;    }    // 查询从s点到w点是否有路径    bool hasPath(int w){        assert( w >= 0 && w < G.V() );        return visited[w];    }    // 查询从s点到w点的路径, 存放在vec中    void path(int w, vector
      
        &vec){        assert( hasPath(w) );        stack
       
         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( hasPath(w) );        vector
        
          vec;        path( w , vec );        for( int i = 0 ; i < vec.size() ; i ++ ){            cout<
         
           ";        }    }};
         
        
       
      
     

main.cpp:

// 测试寻路算法int main() {    string filename = "testG.txt";    SparseGraph g = SparseGraph(7, false);    ReadGraph
     
       readGraph(g, filename);    g.show();    cout<
      
        path(g,0);    cout<<"Path from 0 to 6 : " << endl;    path.showPath(6);    return 0;}
      
     

运行结果：

复杂度：

• 稀疏图（邻接表）： O( V + E )
• 稠密图（邻接矩阵）：O( V^2 )

想获得一个节点的所有相邻节点的时候，我们要将图中所有节点扫一遍

深度优先遍历算法对有向图依然有效

图的广度优先遍历

使用队列。

队列为空。距离0节点的距离排序

层序遍历。<=

记录距离。from。

广度优先遍历：求出了无权图的最短路径。

代码实现：

// 寻找无权图的最短路径template 
     
      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
      
        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
       
         &vec){        assert( w >= 0 && w < G.V() );        stack
        
          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
         
           vec;        path(w, vec);        for( int i = 0 ; i < vec.size() ; i ++ ){            cout<
          
            "; } } // 查看从s点到w点的最短路径长度 int length(int w){ assert( w >= 0 && w < G.V() ); return ord[w]; }};
          
         
        
       
      
     

main.cpp:

// 测试无权图最短路径算法int main() {    string filename = "testG.txt";    SparseGraph g = SparseGraph(7, false);    ReadGraph
     
       readGraph(g, filename);    g.show();    cout<
      
        dfs(g,0);    cout<<"DFS : ";    dfs.showPath(6);    ShortestPath
       
         bfs(g,0);    cout<<"BFS : ";    bfs.showPath(6);    return 0;}
       
      
     

运行结果：

广度优先一定可以找到最短无权路径，深度也有可能找到。

图的存储，边加入的顺序。多条最短路径。跟遍历顺序有关。

更多算法：

flood fill

图的最短路径。

扫雷走迷宫本质是一颗树。能不能走出去就是两点能否连通。最短路径。

迷宫生成 是一个生成树的过程

选定入口与出口：选择一部分红色