1

有向グラフのメソッドDFSメソッドを書き込もうとしています。現在、セグメンテーション違反が発生していますが、それがどこにあるのかよくわかりません。有向グラフについて私が理解していることから、私の論理は正しいと信じています...しかし、新鮮な目が非常に役立つでしょう。

これが私の関数です：

void wdigraph::depth_first (int v) const {

static int fVertex = -1;
static bool* visited = NULL;

if( fVertex == -1 ) {
   fVertex = v;
   visited = new bool[size];
   for( int x = 0; x < size; x++ ) {
      visited[x] = false;
   }
}

cout << label[v];
visited[v] = true;

for (int v = 0; v < adj_matrix.size(); v++) {
   for( int x = 0; x < adj_matrix.size(); x++) {
     if( adj_matrix[v][x] != 0 && visited[x] != false ) {
        cout << " -> ";
        depth_first(x);
     }
     if ( v == fVertex ) {
        fVertex = -1;
        delete [] visited;
        visited = NULL;
     }
   }
}
}

クラス定義：

class wdigraph {
public:
wdigraph(int =NO_NODES);          // default constructor
~wdigraph() {};                   // destructor
int get_size() { return size; }   // returns size of digraph

void depth_first(int) const;// traverses graph using depth-first search
void print_graph() const;   // prints adjacency matrix of digraph

private:
int size;                         // size of digraph
vector<char> label;               // node labels
vector< vector<int> > adj_matrix; // adjacency matrix
};

ありがとう！

4

3 に答える 3

3

visitedプログラムが終了する前に削除しています。開始頂点に戻ることは、終了したことを意味するわけではありません。たとえば、V = {1,2,3}のグラフの場合、E = {（1,2）、（2,1）、（1,3）}。

vまた、入力パラメーターおよびforループ変数として使用していることに注意してください。

于 2010-12-02T07:13:03.707 に答える
2

いくつかの問題があります。

次の行

 if( adj_matrix[v][x] != 0 && visited[x] != false ) {

に変更する必要があります

 if( adj_matrix[v][x] != 0 && visited[x] == false ) {

（まだアクセスされていない頂点でのみ再帰する必要があります。）

また、パラメータを非表示にする新しい変数vをforループ内に作成していますv。これは正当なC ++ですが、ほとんどの場合、ひどい考えです。

于 2010-12-02T07:14:27.183 に答える
2

考慮したいことがいくつかあります。1つ目は、関数レベルの静的変数は通常は良い考えではないということです。おそらく、それらを再設計して通常の変数（追加の割り当てを犠牲にして）またはインスタンスメンバーを作成し、それらを存続させることができます。

この関数は、隣接行列が正方形であると想定していますが、初期化コードが表示されていないため、チェックする必要があります。仮定は、内部ループ条件adj_matrix[v].size()（ノードが与えられた場合v）を作成することによって削除できます。または、それが不変である場合は、その内部ループの前にアサートを追加しますassert( adj_matrix[v].size() == adj_matrix.size() && "adj_matrix is not square!" );。--メンバーsizeとそれ自体のサイズについても同じことが言えadj_matrixます。

アルゴリズム全体は本来よりも複雑に見えます。ノードvから始まるDFSの一般的な形状は次のとおりです。

dfs( v )
   set visited[ v ]
   operate on node (print node label...)
   for each node reachable from v:
      if not visited[ node ]:
         dfs( node )

あなたのアルゴリズムは（ちなみに間違って）グラフを反対方向に横切っているようです。指定されたノードをとして設定してvisitedから、そのノードへのエッジの開始点であるノードを見つけようとします。つまり、から到達可能vなノードを追跡する代わりに、到達可能なノードを取得しようとしていますv。その場合（つまり、目的が収束するすべてのパスを印刷する場合v）、同じエッジを2回ヒットしないように注意する必要があります。そうしないと、無限ループ->stackoverflowになります。

stackoverlowで終了することを確認するには、この例を検討してください。開始ノードは1です。visitedベクトルを作成し、1訪問した位置にマークを付けます。ツリーにエッジ（0,1）があり、それがif：をトリガーすることがわかります。そのため、開始ノードが再びadj_matrix[0][1] != 0 && visited[1]存在する状態で再帰的に入力します。1今回は補助データを作成しませんが、注意visited[1]してループに入り、同じエッジを見つけて再帰的に呼び出します...

于 2010-12-02T09:26:26.203 に答える