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++有向图深度优先搜索

回答

相关问题