在图中搜索顶点的最佳和最简单算法是什么？

Question

在我实现了大部分图表的常见和必需函数之后，我意识到一些函数（删除顶点、搜索顶点和获取顶点）没有最佳实现。

我的图表实现使用邻接链表和链表，我一直在寻找一个另一个顶点，直到找到我想要的那个。正如我所说，我意识到我没有使用最佳实现。我可能有10000个顶点，需要搜索最后一个，但是该顶点可能链接到第一个顶点，这将极大地加速事情。但那只是一个假设情况，它可能发生也可能不会发生。

那么，您推荐哪种搜索查找算法？我们的老师主要讲解了广度优先和深度优先（以及Dikjstra算法，但那是完全不同的主题）。在这两者之间，你推荐哪一个？

如果我能够同时实现两者，那就太完美了，但我没有时间去实现它们，因为第一阶段的截止日期即将到来......

我猜测，选择深度优先算法，因为它似乎更容易实现，并且从它们的工作方式来看，它似乎是一个更好的选择。但这确实取决于输入。

但你们有什么建议呢？

- rfgamaral

---

你如何定义图形的“最后一个顶点”？无论如何，在图形中找到给定顶点的最快方法完全取决于您对图形构造以及起点和终点的了解。 - Cascabel

我会选择广度优先搜索，因为我猜你在谈论递归深度优先搜索。迭代深度优先搜索实现起来有点困难，而递归速度较慢，所以我会选择广度优先搜索。 - IVlad

@Jefromi：在图中，我所说的“最后一个顶点”是指与顶点链表相关联的最后一个顶点。 @IVlad：实际上，由于这个项目依赖于大量数据输入，我正在尝试迭代地编写每个操作。到目前为止，我没有任何递归的想法，我的想法是实现迭代深度优先搜索，除非我发现很难完成... - rfgamaral

IVlad，如果你做得对的话，从迭代BFS切换到迭代DFS就像将队列换成栈一样简单。 - user287792

@Nazgulled：我不理解你所说的“链表上的最后一个”。你说最后一个顶点可以链接到第一个顶点——那么你如何定义“最后一个”呢？（图是由顶点和边组成的集合。即使您随意选择了“第一个顶点”，它也没有“最后一个顶点”）。 - Cascabel

我猜你可能的意思是，你不想要被搜索的顶点是你检查的最后一个。无论如何，我和Konrad的回答完全解决了这个问题，我相信。 - Cascabel

Answer 1

如果您有一个邻接表，查找顶点只需遍历该列表。您甚至可以对列表进行排序以减少所需的查找操作。

图遍历（例如DFS或BFS）从性能角度来看不会改善这一点。

- Konrad Rudolph

---

你是说使用DFS/BFS或遍历链表在性能方面可能是相同的吗？ - rfgamaral

@Nazgulled 如果你在搜索某些东西时，一旦找到了就停止了，那么结果可能会因输入数据的不同而有所差异。如果你要在整个图形中搜索具有某种属性的所有节点，那么可能不会有显著的差异。但是，如果没有提供数据的具体细节，我们无法预测结果。 - Pete Kirkham

Answer 2

在图中查找和删除节点是一个“搜索”问题，而不是图问题。因此，为了使其优于O(n) = 线性搜索、BFS、DFS，您需要将节点存储在不同的数据结构中，该结构经过优化以进行搜索或排序。这将为查找和删除操作提供O(log n)的时间复杂度。候选结构包括B树或哈希表等树形结构。如果你想自己编写代码，我建议使用哈希表，它通常具有非常好的性能并且相对容易实现。

- Arno

Answer 3

我认为BFS通常会更快。阅读维基页面DFS和BFS。

我之所以说BFS更快，是因为它具有按照节点距离起始节点的顺序到达节点的属性。因此，如果您的图形具有N个节点，并且您想搜索节点N和节点1，即从节点1开始搜索，该节点链接到N，那么您将立即找到它。然而，在此发生之前，DFS可能会扩展整个图形。如果您很幸运，DFS可能会更快，而如果您要搜索的节点靠近起始节点，则BFS会更快。简而言之，它们都取决于输入，但我会选择BFS。

没有递归的情况下编写DFS也更难，这使得BFS在实践中稍微快一些，因为它是一种迭代算法。

如果您可以将节点进行标准化（从1到10,000编号，并通过编号访问它们），那么您可以轻松地保持Exists[i] = true，如果节点i在图中，则为false，这样可以获得O(1)的查找时间。否则，如果无法进行标准化或者您不想这样做，请考虑使用哈希表。

- IVlad

---

实际上，我已经实现了一个哈希表，它将保存与图中相同的数据（数据将通过指针共享）。然而，这个大学项目的要求之一是，在我们实现数据结构时，也要实现最常见的操作。我可能甚至不会在图中搜索特定节点，而是使用哈希表。 - rfgamaral

Answer 4

深度优先搜索是最好的，因为

1. 它使用的内存更少
2. 更容易实现

- Peter Alexander

---

DFS如何比BFS使用更少的内存？递归也会使用内存，而迭代版本无论如何都需要一个堆栈。如果说有什么区别，那就是如果递归实现，DFS至少使用和相同数量的内存，如果迭代实现，使用的内存与BFS相同。 - IVlad

IVlad - 让我们看一个可能有些牵强的例子 - 一个有100万个相邻顶点的图。DFS在任何给定时间最多只会在堆栈上包含2个顶点，而BFS在开始时将包含100万个顶点在队列中。 - Niki Yoshiuchi

@Niki - 让我们来看一个有100万个节点的链表图。事实恰恰相反。通常，DFS和BFS使用的内存量是相同的。如果DFS是递归实现的，则DFS使用的内存可能会更多（尽管仍然是O（V）），因为我们可能会为函数添加多个参数以及函数调用开销。如果DFS是迭代实现的，则实际上使用的内存通常是相同的。因此，说DFS（或BFS）“使用的内存要少得多”是完全错误的。 - IVlad

@IVlad - 你是对的，有些情况下BFS使用的内存比DFS少。但声称“DFS使用至少相同数量的内存”是错误的，正如我已经证明的那样，“它使用的内存要少得多”也是错误的，正如你所展示的。我从未声称DFS总是使用较少的内存。 - Niki Yoshiuchi

Answer 5

深度优先搜索和广度优先搜索算法几乎相同，除了在其中一个（DFS）中使用堆栈，在另一个（BFS）中使用队列以及一些必需的成员变量。实现它们两个不应该花费太多额外的时间。

此外，如果您有顶点的邻接表，则查找的复杂度无论如何都是O（V）。因此，使用另外两种搜索方式几乎没有任何收益。

- zellio

---

其实我已经实现了一个简单的栈库，但是没有队列（不过应该也不难，我只是想尽量减少浪费时间，如果在截止日期之前还有时间，我可以再处理它）。无论如何，你是说（第二段）使用DFS/BFS或遍历链表可能是一样的吗？ - rfgamaral

Answer 6

我想评论Konrad的帖子，但我还不能评论，所以...我想强调一下，如果你在列表中实现DFS或BFS，与简单的线性搜索相比，它不会对性能产生影响。你在图中寻找特定节点的搜索并不取决于图的结构，因此没有必要局限于图算法。从编码时间的角度来看，线性搜索是最好的选择；如果你想提高自己的图算法技能，可以实现DFS或BFS，任选其一。

- saramah

Answer 7

如果您正在搜索特定的顶点，并在找到它时终止，我建议使用A*，这是一种最佳优先搜索。

其思想是计算源顶点到当前处理的顶点的距离，然后“猜测”从当前顶点到目标的距离。

您从源开始，计算距离（0）加上猜测（无论是什么），并将其添加到优先级队列中，其中优先级是距离+猜测。在每个步骤中，您都会删除具有最小距离+猜测的元素，对其邻接列表中的每个顶点进行计算，并将其放入优先级队列中。当您找到目标顶点时停止。

如果您的启发式（即“猜测”）是可接受的，也就是说，如果它始终是一个低估值，那么您保证第一次访问目标顶点时找到最短路径。如果您的启发式不可接受，则必须运行该算法以完成查找最短路径（尽管听起来您并不关心最短路径，只要有任何路径即可）。

实现起来并不比广度优先搜索更困难（你只需要添加启发式算法），但它可能会产生更快的结果。唯一困难的部分是找出你的启发式算法。对于代表地理位置的顶点，常见的启发式算法是使用“直线距离”（直接距离）启发式算法。

- Niki Yoshiuchi

Answer 8

线性搜索比BFS和DFS更快。但比线性搜索更快的是将步骤成本设置为零的A*算法。当步骤成本为零时，A*只会扩展最靠近目标节点的节点。如果步骤成本为零，则每个节点的路径成本为零，A*不会优先考虑较短路径的节点。这正是您想要的，因为您不需要最短路径。

A*比线性搜索更快，因为线性搜索很可能在O(n/2)次迭代后完成（每个节点都有相等的机会成为目标节点），但A*优先考虑具有更高概率成为目标节点的节点。

- Default picture