# [C++]C++ STL 环检测 带权有向图 找到全部的环

2017-01-04 19:18:23来源:CSDN作者:u014786849人点击

# 带权有向图找到全部的环

## 完整源码

``#include <iostream>#include <vector> #include <tuple>#include <stack>#include <map>using namespace std;int V, E;int n;//带权有向图map<int, vector<tuple<int , int , double>>> EWD;bool marked[100];   // v 是否已经被访问过？bool onStack[100];  // v 是否在栈里？tuple<int , int , double> edgeTo[100]; // 到达顶点 v 的最后一条边stack<tuple<int , int , double>> cycle[100];    // 有向环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<1>(*ii);        if(!marked[w]) {    // 遇见没访问过的顶点继续dfs递归            edgeTo[w] = *ii;            dfs(w);        }        else if(onStack[w]) {   // 遇见一个访问过的顶点，并且该顶点在栈里说明发现了一个新环            tuple<int, int, double> f = *ii;            while(get<0>(f) != w) {                cycle[n].push(f);                f = edgeTo[get<0>(f)];            }            cycle[n].push(f);            n++;            return ;        }    }    onStack[v] = false;}void findCycle() {    for(int v = 0 ; v < V; v++)        if(!marked[v]) dfs(v);}void showCycle() {    cout << "Cycle : " << endl;    for(int i = 0 ; i < n;i++)     {        double weight = 0.0;        while(!cycle[i].empty()) {            tuple<int, int, double> f = cycle[i].top();             cout << get<0>(f) << "->" << get<1>(f) << " " << get<2>(f) << endl;            weight += get<2>(f);            cycle[i].pop();        }        cout << "weight = " << weight << endl << endl;    }}void readData() {    cin >> V >> E;    for(int i = 0 ; 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 = 0; v < V; v++)     {        cout << v << " : ";        for(vector<tuple<int, int, double>>::iterator ii = EWD[v].begin(); ii != EWD[v].end(); ii++)            cout << get<0>(*ii) << "->" << get<1>(*ii) << " " << get<2>(*ii) << "  ";        cout << endl;    }    system("pause");}int main(){    readData();    showData();    findCycle();    showCycle();}``

## 测试运行

``780 1 0.11 2 -0.22 3 -0.33 1 -0.40 4 0.54 5 -0.65 6 -0.76 4 -0.8EdgeWeightedDigraph :0 : 0->1 0.1  0->4 0.51 : 1->2 -0.22 : 2->3 -0.33 : 3->1 -0.44 : 4->5 -0.65 : 5->6 -0.76 : 6->4 -0.8请按任意键继续. . .Cycle :1->2 -0.22->3 -0.33->1 -0.4weight = -0.94->5 -0.65->6 -0.76->4 -0.8weight = -2.1--------------------------------Process exited after 9.19 seconds with return value 0请按任意键继续. . .``

## 代码说明

### 对比联动

• 之前实现过找到带权有向图任意一个环的代码（点我，或者见引用[1]），本文目的是找到全部的环.

### 使用stack数组来存每个环

``int n; // 变量 n 用来记录这是第几个环；stack<tuple<int , int , double>> cycle[100];    // 栈的数组来记录全部的环cycle[n].push(f); // f 是环上的一条有向边， 压入栈；``

### 找环

#### 任意一个环 vs 全部环

• 任意一个：
``  else if(onStack[w]) {               tuple<int, int, double> f = *ii;            while(get<0>(f) != w) {                cycle.push(f);                f = edgeTo[get<0>(f)];            }            cycle.push(f);            return ;        }``
• 全部环 ：
`` else if(onStack[w]) {              tuple<int, int, double> f = *ii;            while(get<0>(f) != w) {                cycle[n].push(f);                f = edgeTo[get<0>(f)];            }            cycle[n].push(f);            n++;            return ;        }``

#### 删除一条代码块用于找全部环

``  if(!cycle.empty()) {    // 已经找到了一个有向环            return;        }``
• 这个代码段 在本文中其实是被删除掉了的，如果去看引用[1]的文章就可以发现；
• 这个代码段 的作用就是在找到任意的一个环之后就让算法跳出循环；

### 输出环

• 任意一个：
• 因为就只是一个栈，所以只要用一个`while{}`把栈元素弹出来即可；
``void showCycle() {    cout << "Cycle : " << endl;    while(!cycle.empty()) {        tuple<int, int, double> f = cycle.top();         cout << get<0>(f) << "->" << get<1>(f) << " " << get<2>(f) << endl;        cycle.pop();    }    cout << endl;}``
• 全部环：
• 因为现在是栈的数组了， 所以就再加一个`for{}`循环把`while{}`循环包起来，达到把每个环、环的每条边都遍历一下的效果；
``void showCycle() {    cout << "Cycle : " << endl;    for(int i = 0 ; i < n;i++)     {        double weight = 0.0;        while(!cycle[i].empty()) {            tuple<int, int, double> f = cycle[i].top();             cout << get<0>(f) << "->" << get<1>(f) << " " << get<2>(f) << endl;            weight += get<2>(f);            cycle[i].pop();        }        cout << "weight = " << weight << endl << endl;    }}``

# 引用参考

[1] [C++]C++ STL 环检测 带权有向图 DFS
http://blog.csdn.net/cook2eat/article/details/53980745