如何在给定边缘阵列的情况下执行深度优先搜索

-2

对于类分配，我发现自己在图中具有一组边。我想知道是否可以在此图上执行DFS而无需将数据转换为一组顶点。如何在给定边缘阵列的情况下执行深度优先搜索

问题要求*作业帮助* **必须**包括您迄今为止解决问题所做的工作摘要，以及您解决问题的难点描述（[help]，[ask ]）。 – Zabuza

您需要一种方法来访问从给定顶点出去的所有边。否则，由于您始终需要从给定顶点开始的下一个边，因此您无法执行DFS。 – Zabuza

@Zabuza。由于这是一个相当高层次的问题，我不认为我需要提供更多信息。对于访问所有边缘我有同样的想法，但不确定它的有效性或质量。 –

对于DFS以及对于BFS您需要一个数据结构，通过它们的来源提供对边缘的访问。

因此，需要这样的方法：

Edge getOutgoingEdge(source)

如果你只是有一组所有的边缘，你将无法获取下边缘以下的第一边缘后处理。假设你穿越了边缘a -> b，那么你遵循的下一个边缘必须是b -> c。因此，你需要某种结构，可提供每源边缘：

getOutgoingEdge(b)

如果你没有这样的，你需要在您所设定的遍历所有边缘和创造某种Mapsource -> {e edge | alpha(e) = source}之前构建它（其中alpha(e)表示边缘的来源）。

您可以构建该地图上飞，即停止一旦你找到了一个边为您DFS但复杂性仍然是O(|E|)。

2017-10-28 15:00:29 Zabuza

回答