java - Java中的深度优先搜索

Question

我有一个任务需要在 java 中实现 DFS。

刺是这样写的:

public List<Integer> DepthFirstList(Integer v) 
{
    List<Integer> vertices = new ArrayList<Integer>();
    Deque<Integer> toExplore = new ArrayDeque<Integer>();
    List<Integer> visited = new ArrayList<Integer>();
    return vertices;
}

它以v(整数形式的起点)为参数，遍历所有图。我知道 toExplore 是所有节点序列的堆栈。 “visited”是包含节点是否被访问的数组(通过分配“0”或“1”)，并且它们被初始化为全“0”。但是需要返回的“顶点”是什么？

典型的图表如下所示:

9//Number of vertices
0: {1,6} {8,2} {5,4}//{edge with, weight}
1: {0,6} {2,7} {4,9}
2: {3,4} {4,3} {1,7}
3: {1,5} {5,3}
4: {2,3} {6,1}
5: {3,3} {0,7}
6: {4,1} {1,2}

读取输入的代码已经写好。

Answer 1

But what is the "vertices" that needs to return?

根据函数名称，我想您应该按照访问的顺序返回访问顶点的列表。

除非我遗漏了什么，否则这将与 visited 相同，这有点多余。但是 visited 确实应该是一个 Set 以进行高效查找，这将使 vertices 更有意义。

但我不能确定你的老师在想什么。你可能应该去问问他们确认一下。

我假设(根据您的问题)您不是在寻求编写此函数的帮助，只是在了解这部分内容。