C++有向圖深度優先搜索

我正在嘗試爲有向圖編寫一種方法DFS方法。現在我遇到了分割錯誤，我真的不確定它在哪裏。根據我對有向圖的瞭解，我相信我的邏輯是正確的......但是一組新的眼睛將會是一個很好的幫助。C++有向圖深度優先搜索

這裏是我的功能：

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 
};

的感謝！

來源

2010-12-02 rajh2504

有幾件事情你可能要考慮。首先是函數級別的靜態變量通常不是一個好主意，您可以重新設計並使其成爲常規變量（以額外分配爲代價）或實例成員，並使它們保持活躍狀態。

該函數假定鄰接矩陣是方形的，但初始化代碼沒有顯示，所以應該檢查它。通過使內部環路條件adj_matrix[v].size()（給定節點v）或者如果這是不變量，則在內部循環之前添加斷言：assert(adj_matrix[v].size() == adj_matrix.size() && "adj_matrix is not square!"); - 成員size和adj_matrix的大小相同它自我。

整個算法似乎比它應該更加複雜，一個DFS開始節點V具有的一般形狀：

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中收斂的所有路徑），那麼您必須小心不要碰到相同的邊緣兩次，否則將以無限循環 - > stackoverflow結束。

要看到您將以stackoverlow結束，請考慮此示例。起始節點是1。您創建了visited矢量，並將標記位置1視爲已訪問。您發現樹中存在邊（0,1），並觸發if：adj_matrix[0][1] != 0 && visited[1]，因此您再次輸入起始節點爲1。這次你不構造輔助數據，但註釋visited[1]，進入循環，找到相同的邊和遞歸調用...

來源

2010-12-02 09:26:26

很好的答案。（Paddity墊） – 2010-12-05 01:16:12

您正在刪除程序結束前的visited。回到起點頂點並不意味着你完成了。例如，對於V = {1,2,3}，E = {（1,2），（2,1），（1,3）}的圖。

此外，請注意您正在使用v作爲輸入參數，也作爲for循環變量。

來源

2010-12-02 07:13:03 Itsik

我看到一對夫婦的問題：

下面一行

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

應改爲

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

（您想遞歸僅在具有不了頂點已經訪問過。）

另外，y您在for循環中創建一個新變量v，隱藏參數v：這是合法的C++，但它幾乎總是一個可怕的想法。

來源

2010-12-02 07:14:27

C++有向圖深度優先搜索

回答

相關問題