c++ - 有向グラフの 2 つのノード間のすべてのパスを取得する

Question

2 つのノード間の有向グラフですべてのパスを取得しようとしています。サイクルに問題があり、その理由がわかりません。これが私のグラフです（http://www.technical-recipes.comから取得）：

[1,2] エッジ : 1->2 が原因で問題が発生します。取り外せば問題ありません。この特定のテストでは、2 から 5 までのすべてのパスが必要です。最後に小さなコードを提供します。

ケース 1 : [1,2] がない場合の出力:

//g.addEdge( 1, 2 );    
g.addEdge( 1, 3 );    
g.addEdge( 1, 4 );    
g.addEdge( 2, 1 );    
g.addEdge( 2, 4 );    
g.addEdge( 2, 3 );    
g.addEdge( 3, 5 );    
g.addEdge( 4, 5 );    
g.addEdge( 5, 3 ); 

出力は問題ありません:

2 1 3 5    
2 1 4 5  
2 3 5  
2 4 5

ケース 2 : g.addEdge( 1, 2 ); を導入します。=>出力は次のとおりです。

2 3 5 
2 4 5

そのため、現在のノードが 1 で、子として 2 を使用している場合は機能しません。注：visited[]を消去すると、visited[]にはまだ2が含まれています（これはメインで導入されており、そこにあるはずです）...コンテキストの保存が原因だと思います。

私のコードはかなり小さく、次のようになります。

主な機能

    Graph g(5);         //graph with 5 nodes
    std::vector<int> visitedmain;
    visitedmain.push_back(2);    //introduce the start node 2 in the vector

g.addEdge( 1, 2 );    //this is wrong 
g.addEdge( 1, 3 );    
g.addEdge( 1, 4 );    
g.addEdge( 2, 1 );    
g.addEdge( 2, 4 );    
g.addEdge( 2, 3 );    
g.addEdge( 3, 5 );    
g.addEdge( 4, 5 );    
g.addEdge( 5, 3 );  

g.DFS(5, visitedmain);    // 5 is the required (target) node

DFS 関数

void Graph::DFS(int required, std::vector<int>& visited) {
    int i, j;
    //the current node, where I am in recursivity
    int x = visited.back();  

    int ok = 1;

    for (i = 1; i <= n; i++) {
        //for all children
        if (isConnected(x, i)) { 
            //need this for ok, explanation down
            for (j = 0; j < visited.size(); j++) 
                    {
                if (i == visited[j])
                    ok = 0;
            }
            //if it is in the vector already, exit for
            if (!ok)  
                continue;

            ok = 1;
            //If I reached the target, I have the vector containing the nodes from the path
            if (i == required) { 
                //introduce the target node in the path
                visited.push_back(i); 

                for (j = 0; j < visited.size(); j++) {
                    //print the path
                    errs() << visited[j] << " "; 
                }
                errs() << "\n";
                //delete the vector. create one vector every time when traversing the graph
                visited.erase(visited.begin() + visited.size() - 1); 
                break;
            }
        }
    }
    //the case when I still have to traverse undiscovered nodes
    for (i = 1; i <= n; i++) { 
        //for all children
        if (isConnected(x, i)) { 

            for (j = 0; j < visited.size(); j++) {
                if (i == visited[j])
                    ok = 0;
            }
            //if it is already in the vector OR I reached the target, I exit the for
            if (!ok || i == required) 
                continue;
            ok = 1;
            //introduce the child in the vector
            visited.push_back(i); 
            //recursive for this child
            Graph::DFS(required, visited);  
            //delete the old vector
            visited.erase(visited.begin() + visited.size() - 1); 
        }
    }
}

いつもご提案ありがとうございます！