algorithm - 有向图 - 无法到达的节点

Question

在有向加权图中找到不可达节点的最佳方法是什么。我已经使用 A* 进行寻路。因此，数据包含节点列表、链接和邻接列表。我在想 BFS/DFS（哪个是正确的？？），并寻找未标记的节点。节点数可能是 100 - 200，所以它不是一个大图。有没有更好的办法？

Answer 1

BFS 或 DFS 都可以：您需要从起始顶点遍历整个子图，然后可能声明其某些节点不可达，因此您发现可以到达的节点的顺序无关紧要。由于它不是一个大图，递归 DFS 应该不会出现问题，因为即使图实际上是一个列表，200 个节点也不应该足以威胁堆栈溢出。

Answer 2

从哪里无法到达？你必须给一个起始节点。bool[]为每个图形节点填充一个条目的 BFS将起作用，其中节点访问操作将节点设置bool[i]为 true i。最后，具有 的节点i是bool[i]==false无法访问的节点。就运行时间而言，这应该是最佳的。从 BFS 边界/队列中的“起始节点”开始。