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() （给定一个节点 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）然后，您必须小心不要两次击中相同的边缘，否则最终将进入无限环路 - > stackoverflow。

要查看您将以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 作为输入参数，也为前循环变量。

Answer 3

我看到了几个问题：

以下行

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

应该更改为

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

（您只想在具有的顶点上重复 不是 已经访问过。）

另外，您正在创建一个新变量 v 在里面 for 隐藏参数的循环 v: ：这是合法的C ++，但这几乎总是一个可怕的主意。