Не удается выполнить ошибку времени выполнения при глубоком поиске (dfs). Функция перестает возвращаться - PullRequest
Новая
       6

Не удается выполнить ошибку времени выполнения при глубоком поиске (dfs). Функция перестает возвращаться

0 голосов
/ 18 марта 2020 
using namespace std;
bool *marked;
//graph API
class Digraph
{
    int v;
    vector<int>* adj;
    int e;
public:
    Digraph(int V)
    {
        e=0;
        v=V;
        adj=new vector<int>[v];
    }
    void addEdge(int v,int w)
    {
        adj[v].push_back(w);
        e++;
    }
    int V()
    {
        return v;
    }

    vector<int> adjacent(int i)
    {
        return adj[i];
    }
};
//API ends
//this is the problem
void dfs(Digraph g,int s)
{
    marked[s]=true;
    for(int w:g.adjacent(s))
    {
        if(!marked[w])
            dfs(g,w);
    }
}

Dfs здесь отлично работает при обходе узлов, но при возврате он останавливается на одном узле до последнего, и моя программа останавливается. Я скомпилировал его на кодовых блоках ide. Для примера рассмотрим график, идущий 1-> 2-> 3-> 4-> 0-> 1 при прохождении его штрафа, но при возврате остановится на вершине 3 На самом деле я реализовал циклы в графе и топологических сортировках тоже. но никто из них не работал, и я понятия не имею, почему.

...