无法在基于 DFS 的任务排序程序中填充"stack"

Question

我正在编写一个程序，该程序使用递归BFS算法来确定无向图中的依赖关系。我使用 5x5 数组作为邻接矩阵来表示图形。调试时，我注意到我的"stack s"变量在运行时保持为空，我无法弄清楚逻辑错误在哪里。请注意，我是编程新手，如果我在代码中犯了任何基本错误或误解，请告诉我。

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
void TaskOrderHelper(int A[5][5], int start, vector<bool> visited, stack<int> s)
{
for(int i = 0; i < 5; i++)
{
if(A[start][i] == 1 && visited[i] == false)
{
visited[i] = true;
TaskOrderHelper(A, i, visited, s);
s.push(i);
}
}
}
vector<int> taskOrder(int A[5][5], int start)
{
vector<bool> visited(5,false);
stack<int> s;
vector<int> result;
for(int i = 0; i < 5; i++)
{
visited[i] = true;
}
visited[start] = true;
TaskOrderHelper(A, start, visited, s);
while(!s.empty())
{
int w = s.top();
result.push_back(w);
s.pop();
}
return result;
}
int main()
{
int A[5][5] = 
{
{0,1,1,0,0},
{1,0,0,1,0},
{1,0,0,0,1},
{0,1,0,0,1},
{0,0,1,1,0}
};
vector<int> result = taskOrder(A, 0);
for(auto i: result)
{
cout << i;
}
return 0;
}

Answer 1

您为所有访问者设置visited[i] = true;的第 26 行，您的递归 if 语句永远不会命中

Answer 2

BFS 还有其他问题，但要回答您的问题，为什么您的堆栈为空，您的堆栈是按值传递的，修改传递给另一个函数的参数，您需要通过引用传递。尝试将TaskOrderHelper更改为

void TaskOrderHelper(int A[5][5], int start, vector<bool>& visited, stack<int>& s)