C++有向グラフの深さの最初の検索

Question

有向グラフのメソッド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 
}; 

おかげ

は、ここに私の機能です！

Answer 1

考慮すべき点がいくつかあります。第一に、関数レベルの静的変数は通常は良い考えではないので、（余分な割り振りを犠牲にして）それらの通常の変数を再設計して、それらを生き続けることができます。

この関数は、隣接行列が正方形であることを前提としていますが、初期化コードは表示されないため、チェックする必要があります。この仮定は、内部ループ条件をadj_matrix[v].size()（ノードが与えられている場合）にするか、またはそれが不変であれば、その内部ループの前にアサートを追加することによって取り除くことができます。assert(adj_matrix[v].size() == adj_matrix.size() && "adj_matrix is not square!"); - メンバーsizeと同じです。adj_matrixそれは自己です。反対に、グラフを横切る（誤っ介して）あなたのアルゴリズムがあると思われる

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

：

全体アルゴリズムは、それが必要以上に複雑と思われる、ノードvから始まるDFSは、一般的な形状を有しています方向。指定したノードをvisitedと設定し、そのノードのエッジの開始点であるノードを見つけようとします。つまり、ノードがからvに到達するのではなく、vに到達可能なノードを取得しようとしています。その場合（つまり目的がvに収束するすべてのパスを印刷している場合）、同じエッジを2回ヒットしないように注意する必要があります。そうしないと、無限ループ→スタックオーバーフローになります。

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

Answer 2

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

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

私は問題のカップルを見

Answer 3

：

次の行

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

が

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

に変更する必要があります（あなたが唯一となってないを持つ頂点に再帰したいですすでに訪問している）

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