0

我正在制作一个有向图类。我想查找是否有任何循环并相应地用它的路径更新一个向量。我的函数有时会起作用，但其他函数会在路径的最后一条边缘添加两倍。所以我想它需要整理一下。

示例：具有这些路径的图表

0->1, 0->2, 1->2, 2->3, 3->4, 4->0, 4->6, 1->5, 5->6

应该将向量设置为 [0 2 3 4] 或其他任何有效的值。

我试过的：

#include <iostream>  
#include <vector>  
#include <list>  
#include <algorithm>  
using namespace std;  
  
class Graph {  
private:  
    int V;  
    list<int> *adj;  
    bool isCyclicHelp(int v, bool visited[], bool *rs, vector<int> &path) const{  
        if(visited[v] == false) {  
            visited[v] = true;  
            rs[v] = true;  
  
            list<int>::iterator i;  
            for(i=adj[v].begin(); i!=adj[v].end(); i++) {  
                if(!visited[*i] && isCyclicHelp(*i, visited, rs, path)) {  
                    path.push_back(*i);  
                    return true;  
                }  
                else if(rs[*i]) {  
                    return true;  
                }  
            }  
        }  
        rs[v] = false;  
        path.pop_back();  
        return false;  
    }  
public:  
    Graph(int V) {  
        this->V = V;  
        adj = new list<int>[V];  
    }  
    ~Graph() {  
  
    }  
    void addEdge(int v, int w) {  
        if(v != w) {  
            adj[v].push_back(w);  
        }  
    }  
    bool cycle(vector<int> &path) const {  
        bool *visited = new bool[V];  
        bool *recStack = new bool[V];  
        for(int i=0; i<V; i++) {  
            visited[i] = false;  
            recStack[i] = false;  
        }  
  
        for(int i=0; i<V; i++) {  
            path.push_back(i);  
            if(Graph::isCyclicHelp(i, visited, recStack, path)) {  
                reverse(path.begin(), path.end());  
                return true;  
            }  
            path.clear();  
        }  
        path.clear();  
        return false;  
    }  
};
4

0 回答 0