[C++]C++ STL 環檢測 帶權有向圖 DFS

環檢測

完整源碼

#include <iostream>
#include <vector> 
#include <tuple>
#include <stack>
#include <map>
using namespace std;

int V, E;

//帶權有向圖
map<int, vector<tuple<int , int , double>>> EWD;

bool marked[];   // v 是否已經被通路過？
bool onStack[];  // v 是否在棧裡？
tuple<int , int , double> edgeTo[]; // 到達頂點 v 的最後一條邊
stack<tuple<int , int , double>> cycle; // 有向環


void dfs(int v) {
    onStack[v] = true;
    marked[v] = true;

    for(vector<tuple<int, int, double>>::iterator ii = EWD[v].begin(); ii != EWD[v].end(); ii++)
    {

        int w = get<>(*ii);

        if(!cycle.empty()) {    // 已經找到了一個有向環
            return;
        }
        else if(!marked[w]) {   // 遇見沒通路過的頂點繼續dfs遞歸
            edgeTo[w] = *ii;
            dfs(w);
        }
        else if(onStack[w]) {   // 遇見一個通路過的頂點，并且該頂點在棧裡說明發現了一個新環
            tuple<int, int, double> f = *ii;
            while(get<>(f) != w) {
                cycle.push(f);
                f = edgeTo[get<>(f)];
            }

            cycle.push(f);
            return ;

        }
    }

    onStack[v] = false;
}

void findCycle() {
    for(int v =  ; v < V; v++)
        if(!marked[v]) dfs(v);
}

void showCycle() {
    cout << "Cycle : " << endl;
    while(!cycle.empty()) {
        tuple<int, int, double> f = cycle.top(); 
        cout << get<>(f) << "->" << get<>(f) << " " << get<>(f) << endl;
        cycle.pop();
    }
    cout << endl;
}


void readData() {
    cin >> V >> E;
    for(int i =  ; i < E ;i++)
    {
        int v, w;
        double weight;
        cin >> v >> w >> weight;
        EWD[v].push_back(make_tuple(v, w, weight));
    }
}

void showData() {
    cout << "EdgeWeightedDigraph : " << endl;
    for(int v = ; v < V; v++) 
    {
        cout << v << " : ";
        for(vector<tuple<int, int, double>>::iterator ii = EWD[v].begin(); ii != EWD[v].end(); ii++)
            cout << get<>(*ii) << "->" << get<>(*ii) << " " << get<>(*ii) << "  ";
        cout << endl;
    }

    system("pause");
}

int main()
{
    readData();
    showData();

    findCycle();
    showCycle();

}
           

測試運作

模拟資料

運作結果

EdgeWeightedDigraph :
 : ->   -> 
 :
 : -> 
 : -> 

請按任意鍵繼續. . .
Cycle :
-> 
-> 
-> 

--------------------------------
           

簡單地說

1. 從 出發，往左邊走，先遇到

   1

   ，到頭了，回不到 ，這不是環；
2. 從 出發，往右邊走，先遇到

   2

   ，繼續往深處走，遇到

   3

   ，再往深處走，遇到 ， 不僅通路過還在棧上面，這是環；

代碼說明

資料類型

tuple<int , int , double> edgeTo[]; // 到達頂點 v 的最後一條邊

stack<tuple<int , int , double>> cycle; // 有向環
           

1. 有向邊，頂點、頂點、權重，其實本文重點是 環 檢測，帶不帶權重都不重要，算法都一樣；

2. stack

   來存這條被找出來的有向邊；

主程式

int main()
{
    readData();  // 資料輸入
    showData();  // 顯示有向圖

    findCycle(); // 找到一個環
    showCycle(); // 顯示找到的環

}
           

環檢測

void findCycle() {
    for(int v =  ; v < V; v++)
        if(!marked[v]) dfs(v);
}


void dfs(int v) {
    onStack[v] = true;

    marked[v] = true;
    for()
    {
        if(!cycle.empty()) { 
            return; 
        }
        else if(!marked[w]) {   
            edgeTo[w] = *ii;
            dfs(w);
        }
        else if(onStack[w]) {
        }   
    }

    onStack[v] = false;
}
           

1. 本質就是

   DFS

   搜尋，增加了

   onStack

   數組來表示出現在 本次遞歸 之中的頂點；

2. onStack[]

   數組就是顯式地把記憶體棧的調用過程擺出來；
3. 兩個

   else if

   等價于

   if(marked[w] && onStack[w])

   ，被通路過也要在 本次遞歸 之中；

繼續DFS

else if(!marked[w]) {   // 遇見沒通路過的頂點繼續dfs遞歸
            edgeTo[w] = *ii;
            dfs(w);
        }
           

• marked[]

  數組和

  DFS

  是“打包”使用的，不要多想；

把環存起來

else if(onStack[w]) {   
            tuple<int, int, double> f = *ii;
            while(get<>(f) != w) {
                cycle.push(f);
                f = edgeTo[get<>(f)];
            }

            cycle.push(f);
            return ;

        }
           

• 因為存的是有向邊，順着邊，從

  to

  到

  from

  ，往回爬，爬到環的起點（就是那個被發現被通路的并且在本次遞歸中的點）就行了；

顯示環

void showCycle() {
    cout << "Cycle : " << endl;
    while(!cycle.empty()) {
        tuple<int, int, double> f = cycle.top(); 
        cout << get<>(f) << "->" << get<>(f) << " " << get<>(f) << endl;
        cycle.pop();
    }
    cout << endl;
}
           

• 就是把棧的内容拿出來；

思考體會

1. 遞歸寫代碼還是很不熟練，這個代碼完全是照着

   algs4

   的代碼寫的，隻不過是一種

   C++ STL

   的實作；

2. C++ STL

   其實也還不熟練，比如我覺得我應該是可以把

   tuple<int, int, double>

   用個什麼

   typedef

   還是

   struct

   打包一下，不用每次都

   copy

   這一串，但是我覺得我要寫個環檢測，也沒必要先窮盡

   C++ STL

   再寫吧，嗯，可以以後改進這裡；
3. 其實一開始我在

   showCycle()

   直接寫了個

   cout << f ;

   ，我一開始寫

   C++

   的輸出語句還是用的

   C

   的

   printf

   ，後來發現

   cout

   是個好東西，什麼都可以裝，就直接用

   cout

   了，這裡還是要分開寫的；
4. 代碼裡還是有把功能和具體實作沒有分開的問題，比如

   tuple<int, int, double>

   ，用

   get<0>

   取出來的是

   from

   ，以此類推，但是現在感覺這裡似乎不要把細節暴露出來比較好。

參考引用

[1] C++ STL stack

http://www.cplusplus.com/reference/stack/stack/

[2] algs4 Finds a directed cycle in an edge-weighted digraph.

http://algs4.cs.princeton.edu/44sp/EdgeWeightedDirectedCycle.java.html