我试图在两个节点之间的有向图中获取所有路径。我的循环有问题，我找不到原因。这是我的图表（取自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);
}
}
}
谢谢你的每一个建议！