拓撲使用排序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

回答

相關問題