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

您将在程序结束前删除visited。
回到起始顶点并不意味着你已经完成了。
例如，对于 V = {1,2,3} 的图，E={(1,2),(2,1),(1,3)}。

另外，请注意您使用 v 作为输入参数以及 for 循环变量。

Answer 2

您可能需要考虑一些事情。首先，函数级静态变量通常不是一个好主意，您可以重新设计并制作这些常规变量（以额外分配为代价）或实例成员，并使它们保持活动状态。

该函数假设邻接矩阵是方阵，但未显示初始化代码，因此应检查。可以通过设置内部循环条件 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 中汇聚的所有路径），那么您必须小心，不要两次击中同一条边，否则您将陷入无限循环 ->堆栈溢出。

要看到您将以 stackoverlow 结束，请考虑此示例。起始节点是1。您创建 visited 向量并将位置 1 标记为已访问。你发现树中有一条边 (0,1)，这会触发 if: adj_matrix[0][1] != 0 &&访问了[1]，因此您再次递归输入，起始节点为1。这次不构造辅助数据，而是备注visited[1]，进入循环，找到相同的边，递归调用...

Answer 3

我看到几个问题：

以下行

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

应更改为

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

（您只想在尚未访问过的顶点上递归。）

此外，您正在创建一个新变量 v 在 for 循环中隐藏参数 v：这是合法的 C++，但它几乎总是一个糟糕的主意。