C ++定向图形深度首次搜索
-
30-09-2019 - |
题
我正在尝试为有向图编写方法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
};
谢谢!
解决方案
您可能想考虑一些事情。首先是函数级别的静态变量通常不是一个好主意,您可能可以重新设计并使这些常规变量(以额外的分配为代价)或实例成员并保持生命。
该函数假设邻接矩阵为正方形,但未显示初始化代码,因此应检查。可以通过使内部循环条件消除假设 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]
, ,输入循环,找到相同的边缘并递归呼叫...
其他提示
您正在删除 visited
在程序结束之前。回到起始顶点并不意味着您完成了。例如,对于V = {1,2,3}的图,E = {(1,2),(2,1),(1,3)}。
另外,请注意您正在使用 v
作为输入参数,也为前循环变量。
我看到了几个问题:
以下行
if( adj_matrix[v][x] != 0 && visited[x] != false ) {
应该更改为
if( adj_matrix[v][x] != 0 && visited[x] == false ) {
(您只想在具有的顶点上重复 不是 已经访问过。)
另外,您正在创建一个新变量 v
在里面 for
隐藏参数的循环 v
: :这是合法的C ++,但这几乎总是一个可怕的主意。