0

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]を作成する必要があると思いますが、その後どうすればよいですか?

4

1 に答える 1

2

いくつかの変更を行ったところ、ideoneでプログラムが正常に終了しました 。最も重要な変更は、行列と v を初期化しなかったことです (この変更がなくても、プログラムは正常に終了しましたが、出力は 0-s のみでした)。あなたが話しているエラーは見当たりませんでした。v を初期化しなかったときに 0 のみを取得する理由は明らかです。すべての値が非ゼロであり、すべてのノードが訪問されていないと見なされます。

編集:「= true;」を忘れたように見える27行目も変更しました。

EDIT 2:メモリを解放していないため、良くありません。また、a に動的配列が必要な理由もわかりません。事前にそのサイズを知っています。最後にもう 1 つ注意してください - 配列を行列にして v をグローバルにすると、それらは自動的にゼロになります (指摘するだけでこれが良いアプローチだと言っているわけではありません) が、それらはローカルであるためゼロにはなりません。

于 2012-04-28T11:11:28.743 に答える