[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