这里是在c++中使用DFS的拓扑排序,有bug(out of bound error)
#include<iostream>
#include<stdio.h>
using namespace std;
int count=0;
static int *a=new int[8];
void dfs(int u,bool v[],bool matrix[][8])
{
v[u]=true;
for(int i=0;i<8;i++)
if(!v[i]&& matrix[u][i])
dfs(i,v,matrix);
a[count++]=u;
}
int main()
{
bool v[8];
bool matrix[8][8];
matrix[7][6]=true;
matrix[0][1];
matrix[1][2]=true;
matrix[2][3]=true;
matrix[3][4]=true;
matrix[2][5]=true;
for(int i=0;i<8;i++)
if(!v[i])
dfs(i,v,matrix);
for(int i=0;i<8;i++)
cout<<a[7-i]<<" ";
}
请帮我解决这个错误,我想我应该创建矩阵[8][2],但之后如何继续?
最佳答案
我做了一些更改,现在您的程序已在 ideone 上成功完成 最重要的变化是你没有初始化矩阵和 v(即使没有这个变化程序仍然成功完成但输出只是 0-s)。我没有看到你说的错误。当你没有初始化 v 时只得到 0-s 的原因很明显——所有的值都是非零的,所以所有的节点都被认为没有被访问过。
编辑:我还更改了第 27 行,您似乎忘记了“= true;”
编辑 2:您没有为不好的 a 释放内存。另外我不明白为什么你需要一个动态数组。你事先知道它的大小。最后一点 - 如果您将数组矩阵和 v 设为全局,它们将自动归零(我并不是说这是一个很好的方法,只是指出),但由于它们是本地的,因此它们不会被归零。
关于c++ - 使用 dfs 进行拓扑排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10362848/