如何在给定边缘阵列的情况下执行深度优先搜索
答
对于DFS
以及对于BFS
您需要一个数据结构,通过它们的来源提供对边缘的访问。
因此,需要这样的方法:
Edge getOutgoingEdge(source)
如果你只是有一组所有的边缘,你将无法获取下边缘以下的第一边缘后处理。假设你穿越了边缘a -> b
,那么你遵循的下一个边缘必须是b -> c
。因此,你需要某种结构,可提供每源边缘:
getOutgoingEdge(b)
如果你没有这样的,你需要在您所设定的遍历所有边缘和创造某种Map
source -> {e edge | alpha(e) = source}
之前构建它(其中alpha(e)
表示边缘的来源)。
您可以构建该地图上飞,即停止一旦你找到了一个边为您DFS
但复杂性仍然是O(|E|)
。
问题要求*作业帮助* **必须**包括您迄今为止解决问题所做的工作摘要,以及您解决问题的难点描述([help],[ask ])。 – Zabuza
您需要一种方法来访问从给定顶点出去的所有边。否则,由于您始终需要从给定顶点开始的下一个边,因此您无法执行DFS。 – Zabuza
@Zabuza。由于这是一个相当高层次的问题,我不认为我需要提供更多信息。对于访问所有边缘我有同样的想法,但不确定它的有效性或质量。 –