c++ - 获取有向图中2个节点之间的所有路径

Question

我正在尝试获取两个节点之间有向图中的所有路径。我的循环有问题，我找不到原因。这是我的图表(取自 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(在 main 中引入，我认为它应该在那里)...我认为是因为上下文保存。

我的代码很小，看起来像这样:

主函数

    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); 
        }
    }
}

感谢您的每一个建议!

Answer 1

你关于 ok 的逻辑看起来很可疑。

您在函数的开头设置 ok=1，并且在测试之后只有 ok=1 时才会通过。

我建议在将其设置为 0 的 for 循环之前设置 ok=1。

即改变

for(j=0; j<visited.size(); j++) 

到

ok=1;
for(j=0; j<visited.size(); j++) 

在发生这种情况的两个地方。