[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

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台