拓扑使用排序DFS

这里是使用++ DFS在C，它有缺陷，拓扑排序（出界错误）拓扑使用排序DFS

#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]，但之后如何继续？

来源

2012-04-28 dato datuashvili

下面是超出范围访问'a [count ++] = u;'的一个候选人。你怎么知道在递归调用期间'count'总是*在范围内？ – 2012-04-28 11:05:27

您遇到什么错误？它与'v'和'matrix'中的许多元素是否未初始化有关？ – Attila 2012-04-28 11:05:55

@BoPersson - 调用'dfs'的条件是'v [i]'是'false'。 'v'中只有8个元素，而'dfs'中当前的元素被设置为'false'，所以我不认为会因为递归而导致过度索引。 – Attila 2012-04-28 11:07:38

我已经做了一些更改，现在您的程序已成功完成ideone 最重要的变化是您没有初始化矩阵和v（即使没有此更改，程序仍然成功完成，但输出仅为0-s ）。我没有看到你正在谈论的错误。当你没有初始化v时只有0-s的原因很明显 - 所有的值都是非零的，所有的节点都被认为没有被访问。

编辑：我也改变了行27，你似乎忘记了“= true;”

编辑2：你没有释放内存，这是不好的。另外我不明白你为什么需要动态数组。你事先知道它的大小。最后一点 - 如果你制作数组矩阵和全局变量，它们将自动归零（我不是说这是指出的好办法），但是因为它们是本地的，所以它们不会归零。

来源

2012-04-28 11:11:28

拓扑使用排序DFS

回答

相关问题