1

我正在尝试为有向图编写方法 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
};

谢谢！

4

3 回答 3

3

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

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

于 2010-12-02T07:13:03.707 回答
2

我看到几个问题：

以下行

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

应该改为

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

（您只想对尚未访问过的顶点进行递归。）

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

于 2010-12-02T07:14:27.183 回答
2

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

该函数假设邻接矩阵是方阵，但是初始化代码没有显示，所以应该检查一下。可以通过使内部循环条件adj_matrix[v].size()（给定一个 node 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，然后尝试定位作为该节点边缘起点的任何节点。也就是说，您尝试获取可访问的节点，而不是跟踪可从到达的节点。如果是这种情况（即，如果目标是打印所有会聚的路径），那么您必须小心不要两次碰到相同的边缘，否则您将陷入无限循环 - > stackoverflow。vvv

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

于 2010-12-02T09:26:26.203 回答