算法與資料結構（七）圖論

圖論 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<vector<bool>> g; // 圖的具體資料

public:
    // 構造函數
    DenseGraph( int n , bool directed ){
        assert( n >= 0 );
        this->n = n;
        this->m = 0;    // 初始化沒有任何邊
        this->directed = directed;
        // g初始化為n*n的布爾矩陣, 每一個g[i][j]均為false, 表示沒有任和邊
        //g = vector<vector<bool>>(n, vector<bool>(n, false));
          for (int i = 0; i < n; ++i) {
            g.push_back(vector<bool>(n, false));
        }
    }

    ~DenseGraph(){ }

    int V(){ return n;} // 傳回節點個數
    int E(){ return m;} // 傳回邊的個數

    // 向圖中添加一個邊
    void addEdge( int v , int w ){

        assert( v >= 0 && v < n );
        assert( w >= 0 && w < n );

        if( hasEdge( v , w ) )
            return;

        g[v][w] = true;
        if( !directed )
            g[w][v] = true;

        m ++;
    }

    // 驗證圖中是否有從v到w的邊
    bool hasEdge( int v , int w ){
        assert( v >= 0 && v < n );
        assert( w >= 0 && w < n );
        return g[v][w];
    }
};

addedge的時候已經去除了平行邊的概念。因為如果有邊之間return

O(1)來判斷是否有邊

稀疏圖編碼

// 稀疏圖 - 鄰接表
class SparseGraph{

private:
    int n, m;       // 節點數和邊數
    bool directed;  // 是否為有向圖
    vector<vector<int>> g;  // 圖的具體資料

public:
    // 構造函數
    SparseGraph( int n , bool directed ){
        assert( n >= 0 );
        this->n = n;
        this->m = 0;    // 初始化沒有任何邊
        this->directed = directed;
        // g初始化為n個空的vector, 表示每一個g[i]都為空, 即沒有任和邊
        //g = vector<vector<int>>(n, vector<int>());
        for (int i = 0; i < n; ++i) {
            g.push_back(vector<int>());
        }
    }

    ~SparseGraph(){ }

    int V(){ return n;} // 傳回節點個數
    int E(){ return m;} // 傳回邊的個數

    // 向圖中添加一個邊
    void addEdge( int v, int w ){

        assert( v >= 0 && v < n );
        assert( w >= 0 && w < n );

        g[v].push_back(w);
        //處理自環邊
        if( v != w && !directed )
            g[w].push_back(v);

        m ++;
    }

    // 驗證圖中是否有從v到w的邊
    bool hasEdge( int v , int w ){

        assert( v >= 0 && v < n );
        assert( w >= 0 && w < n );

        //使用鄰接表在判斷解決平行邊複雜度高
        for( int i = 0 ; i < g[v].size() ; i ++ )
            if( g[v][i] == w )
                return true;
        return false;
    }
};

鄰接表取消平行邊複雜度度過大。

鄰接表的優勢

周遊鄰邊 - 圖算法中最常見的操作

周遊鄰邊，鄰接表有優勢

// 鄰邊疊代器, 傳入一個圖和一個頂點,
    // 疊代在這個圖中和這個頂點向連的所有頂點
    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 <typename Graph>
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 <typename Graph>
class Component{

private:
    Graph &G;       // 圖的引用
    bool *visited;  // 記錄dfs的過程中節點是否被通路
    int ccount;     // 記錄聯通分量個數
    int *id;        // 每個節點所對應的聯通分量标記

    // 圖的深度優先周遊(遞歸方式)
    void dfs( int v ){

        visited[v] = true;
        id[v] = ccount;
        typename Graph::adjIterator adj(G, v);
        for( int i = adj.begin() ; !adj.end() ; i = adj.next() ){
            if( !visited[i] )
                dfs(i);
        }
    }

public:
    // 構造函數, 求出無權圖的聯通分量
    Component(Graph &graph): G(graph){

        // 算法初始化
        visited = new bool[G.V()];
        id = new int[G.V()];
        ccount = 0;
        for( int i = 0 ; i < G.V() ; i ++ ){
            visited[i] = false;
            id[i] = -1;
        }

        // 求圖的聯通分量
        for( int i = 0 ; i < G.V() ; i ++ )
            if( !visited[i] ){
                dfs(i);
                ccount ++;
            }
    }

    // 析構函數
    ~Component(){
        delete[] visited;
        delete[] id;
    }

    // 傳回圖的聯通分量個數
    int count(){
        return ccount;
    }

    // 查詢點v和點w是否聯通
    bool isConnected( int v , int w ){
        assert( v >= 0 && v < G.V() );
        assert( w >= 0 && w < G.V() );
        return id[v] == id[w];
    }
};

main.cpp

// 測試圖的聯通分量算法
int main() {

    // TestG1.txt
    string filename1 = "testG1.txt";
    SparseGraph g1 = SparseGraph(13, false);
    ReadGraph<SparseGraph> readGraph1(g1, filename1);
    Component<SparseGraph> component1(g1);
    cout<<"TestG1.txt, Component Count: "<<component1.count()<<endl;

    cout<<endl;

    // TestG2.txt
    string filename2 = "testG2.txt";
    SparseGraph g2 = SparseGraph(7, false);
    ReadGraph<SparseGraph> readGraph2(g2, filename2);
    Component<SparseGraph> component2(g2);
    cout<<"TestG2.txt, Component Count: "<<component2.count()<<endl;

    return 0;
}

運作結果：

運作結果

求出連通分量，可以求出兩個結點是否相連

添加id來記錄。

int *id;        // 每個節點所對應的聯通分量标記

并查集隻能讓我們知道兩個結點是否相連。而路徑需要圖論來解決

獲得兩點間的一條路徑。

兩點間路徑

深度優先獲得一條路徑。周遊的同時儲存是從哪周遊過來的。

int * from;     // 記錄路徑, from[i]表示查找的路徑上i的上一個節點

// 路徑查詢
template <typename Graph>
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<int> &vec){

        assert( hasPath(w) );

        stack<int> s;
        // 通過from數組逆向查找到從s到w的路徑, 存放到棧中
        int p = w;
        while( p != -1 ){
            s.push(p);
            p = from[p];
        }

        // 從棧中依次取出元素, 獲得順序的從s到w的路徑
        vec.clear();
        while( !s.empty() ){
            vec.push_back( s.top() );
            s.pop();
        }
    }

    // 列印出從s點到w點的路徑
    void showPath(int w){

        assert( hasPath(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<<" -> ";
        }
    }
};

main.cpp:

// 測試尋路算法
int main() {

    string filename = "testG.txt";
    SparseGraph g = SparseGraph(7, false);
    ReadGraph<SparseGraph> readGraph(g, filename);
    g.show();
    cout<<endl;

    Path<SparseGraph> path(g,0);
    cout<<"Path from 0 to 6 : " << endl;
    path.showPath(6);

    return 0;
}

運作結果：

運作結果

複雜度：

稀疏圖（鄰接表）： O( V + E )
稠密圖（鄰接矩陣）：O( V^2 )

想獲得一個節點的所有相鄰節點的時候，我們要将圖中所有節點掃一遍

深度優先周遊算法對有向圖依然有效

檢視環：有向圖

圖的廣度優先周遊

使用隊列。

隊列

隊列為空。距離0節點的距離排序

層序周遊。<=

記錄距離。from。

廣度優先周遊：求出了無權圖的最短路徑。

代碼實作：

// 尋找無權圖的最短路徑
template <typename Graph>
class ShortestPath{

private:
    Graph &G;       // 圖的引用
    int s;          // 起始點
    bool *visited;  // 記錄dfs的過程中節點是否被通路
    int *from;      // 記錄路徑, from[i]表示查找的路徑上i的上一個節點
    int *ord;       // 記錄路徑中節點的次序。ord[i]表示i節點在路徑中的次序。

public:
    // 構造函數, 尋找無權圖graph從s點到其他點的最短路徑
    ShortestPath(Graph &graph, int s):G(graph){

        // 算法初始化
        assert( s >= 0 && s < graph.V() );

        visited = new bool[graph.V()];
        from = new int[graph.V()];
        ord = new int[graph.V()];
        for( int i = 0 ; i < graph.V() ; i ++ ){
            visited[i] = false;
            from[i] = -1;
            ord[i] = -1;
        }
        this->s = s;

        // 無向圖最短路徑算法, 從s開始廣度優先周遊整張圖
        queue<int> q;

        q.push( s );
        visited[s] = true;
        ord[s] = 0;
        while( !q.empty() ){

            int v = q.front();
            q.pop();

            typename Graph::adjIterator adj(G, v);
            for( int i = adj.begin() ; !adj.end() ; i = adj.next() )
                if( !visited[i] ){
                    q.push(i);
                    visited[i] = true;
                    from[i] = v;
                    ord[i] = ord[v] + 1;
                }
        }

    }

    // 析構函數
    ~ShortestPath(){

        delete [] visited;
        delete [] from;
        delete [] ord;
    }

    // 查詢從s點到w點是否有路徑
    bool hasPath(int w){
        assert( w >= 0 && w < G.V() );
        return visited[w];
    }

    // 查詢從s點到w點的路徑, 存放在vec中
    void path(int w, vector<int> &vec){

        assert( w >= 0 && w < G.V() );

        stack<int> s;
        // 通過from數組逆向查找到從s到w的路徑, 存放到棧中
        int p = w;
        while( p != -1 ){
            s.push(p);
            p = from[p];
        }

        // 從棧中依次取出元素, 獲得順序的從s到w的路徑
        vec.clear();
        while( !s.empty() ){
            vec.push_back( s.top() );
            s.pop();
        }
    }

    // 列印出從s點到w點的路徑
    void showPath(int w){

        assert( w >= 0 && w < G.V() );

        vector<int> vec;
        path(w, vec);
        for( int i = 0 ; i < vec.size() ; i ++ ){
            cout<<vec[i];
            if( i == vec.size()-1 )
                cout<<endl;
            else
                cout<<" -> ";
        }
    }

    // 檢視從s點到w點的最短路徑長度
    int length(int w){
        assert( w >= 0 && w < G.V() );
        return ord[w];
    }
};

main.cpp:

// 測試無權圖最短路徑算法
int main() {

    string filename = "testG.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;
}

運作結果：

廣度優先一定可以找到最短無權路徑

廣度優先一定可以找到最短無權路徑，深度也有可能找到。

圖的存儲，邊加入的順序。多條最短路徑。跟周遊順序有關。

更多算法：

flood fill

摳圖圖周遊

圖的最短路徑。

掃雷走迷宮本質是一顆樹。能不能走出去就是兩點能否連通。最短路徑。

迷宮生成是一個生成樹的過程

標明入口與出口：選擇一部分紅色

迷宮生成

算法與資料結構（七）圖論

圖論 Graph Theory

圖的表示

鄰接表的優勢

算法封裝成類

圖的周遊

圖的廣度優先周遊

繼續閱讀

goalng nil interface淺析持續學習

模組化：數學模組化

開源軟體：NoSql資料庫 - 圖資料庫 Neo4j轉載自原文位址：http://www.cnblogs.com/loveis715/p/5277051.html

資料在網絡7層中的傳輸過程

當今世界十大經典算法

字元串功能實作

【算法提高班】貪婪政策

《貪婪的動态規劃》

分治法實作求解最大子數組

UVA 10154:Weights and Measures Weights and Measures

Linux Kernel Development　學習

動态規劃、最小費用流例題 — nyoj_712 探尋寶藏

計算機開路人阿蘭·圖靈

基礎算法之二分查找

poj3249

PAT 1089 Insert or Merge[難]

算法與資料結構（七） 圖論

圖論 Graph Theory

圖的表示

鄰接表的優勢

算法封裝成類

圖的周遊

圖的廣度優先周遊

繼續閱讀

算法與資料結構（七）圖論