C ++指示グラフ深さ最初の検索

StackOverflow https://stackoverflow.com/questions/4332363

質問

指示されたグラフのメソッド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
};

ありがとう！

役に立ちましたか？

解決

考慮したいことがいくつかあります。 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 )

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

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

他のヒント

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

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

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

次の行

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

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

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

（あなたは持っている頂点でのみ再発したい いいえ すでに訪問されています。）

また、新しい変数を作成しています v の中に for パラメーターを隠すループ v: ：それは合法的なC ++ですが、ほとんど常にひどい考えです。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top