gpt4 book ai didi

java - 迭代 DFS 比递归 DFS 更快吗?

转载 作者:行者123 更新时间:2023-12-01 12:04:32 37 4
gpt4 key购买 nike

我以迭代方式和递归方式实现了深度优先搜索算法。它们对于小尺寸(小于 1 MB)的文件都可以正常工作。然而,当我尝试在 50 MB 的文件上运行它们时,递归 DFS(9 秒)似乎比使用迭代方法(至少几分钟)快得多。事实上,迭代方法花了很长时间才完成。

我选择实现迭代DFS的唯一原因是我认为它可能比递归DFS更快。但事实似乎并非如此。这是预期的吗?

请注意:我已经在使用 java -Xmx1024m -Xms1024m -Xmn256m -Xss16m RunAlgo 来增加内存。

下面是我用来编写迭代 DFS 的代码。

class IterativeDFS{
long time;
LinkedList<Vertex>topological_sort_list = new LinkedList<Vertex>();

public IterativeDFS(Digraph G){
dfs(G);
}

public void dfs(Digraph G){
for(Vertex u : G.getAllVertices()){
u.set_color("WHITE");
u.set_pi(-1);
}
time = 0;

for(Vertex u : G.getAllVertices()){
if(u.get_color().equals("WHITE")){
dfs_stack(G, u);
}
}
}

public void dfs_stack(Digraph G, Vertex u){
int size = G.getAllVertices().size();

/*
* to be able to iterate over each adjacency list, keeping track of which
* vertex in each adjacency list needs to be explored next.
*/
HashMap<Vertex, Iterator<Vertex>> adj_map = new HashMap<Vertex, Iterator<Vertex>>();
for(Vertex i : G.getAllVertices()){
adj_map.put(i, G.adjEdges(i).iterator());
}

Stack<Vertex> stack = new Stack<Vertex>();
// time++; // white vertex u has just been discovered
u.set_d(time);
u.set_color("GRAY");
stack.push(u);

while(!stack.empty()){

Vertex k = stack.peek();

Vertex v = null;
if(adj_map.get(k).hasNext()){
v = adj_map.get(k).next(); // explore edges (k,v)
if(v.get_color().equals("WHITE")){
v.set_pi(k.get_node());
// time++;
v.set_d(time);
v.set_color("GRAY");
stack.push(v);
}
} else{
// v's adjacency list is exhausted
Vertex t = stack.pop();
time++;
t.set_f(time);
t.set_color("BLACK");
/*
* Topological Sort :
* 1. call DFS(G) to compute finishing times v.f for each vertex v
* 2. as each vertex is finished, insert it onto FRONT of linked list
* 3. return linked list of vertices
*/
topological_sort_list.addFirst(t);
}
}
}

public LinkedList<Vertex> topological_sort(){
return topological_sort_list;
}

}

最佳答案

如果你谈论的是时间复杂度,答案是两者是相同的。无论实现如何,DFS 的运行时间都是 O(V),因为您应该只访问图中的每个顶点一次。此外,运行时也是 Omega(V),因为无论输入大小如何,您都会访问图中的所有顶点一次。这使得 DFS 的运行时间为 Theta(V)。无论实现如何,总体 DFS 算法都保持不变。因此,递归 DFS 与迭代 DFS 的运行时间应该相同,均为 Theta(V)。

关于java - 迭代 DFS 比递归 DFS 更快吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27724054/

37 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com