在图上搜索顶点的最佳和最简单的算法？

Question

在为我的图实现实现了大多数常见和所需的函数之后，我意识到有几个函数（删除顶点、搜索顶点和获取顶点）没有“最佳”实现。

我在图实现中使用带有链表的邻接表，并且我一个接一个地搜索顶点，直到找到我想要的顶点。就像我说的，我意识到我没有使用“最佳”实现。我可以有 10000 个顶点，需要搜索最后一个顶点，但该顶点可能有到第一个顶点的链接，这会大大加快速度。但这只是一个假设的情况，它可能会发生，也可能不会发生。

那么，您推荐什么算法用于搜索查找？我们的老师主要谈论的是广度优先和深度优先（还有 Dikjstra 的算法，但那是一个完全不同的主题）。在这两者之间，您推荐哪一个？

如果我可以同时实现这两个功能，那就完美了，但我没有时间，我需要选择一个并实现它，因为第一阶段的截止日期即将到来......

我的猜测是采用深度优先，似乎更容易实现，并且看看它们的工作方式，这似乎是最好的选择。但这实际上取决于输入。

但你们有什么建议呢？

Answer 1

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

一个图的遍历（如DFS或BFS）将不会从性能角度改善此。

Answer 2

查找和图形删除节点是“搜索”的问题不是一个图形的问题，所以使它比为O（n）=线性搜索，BFS，DFS，你需要你的节点存储在不同的数据结构搜索或排序它们进行优化。这给你O（log n）的用于发现和删除操作。 Candidatas是树形结构像B树或哈希表。如果你想自己编写的东西，我会去一个哈希表通常提供了很好的性能，是相当容易实现。

Answer 3

我觉得BFS通常会更快的平均值。阅读 DFS 和的 BFS 。

我说BFS更快的原因是因为它在到达节点的属性，从你的出发点的距离依次。所以，如果你的图具有N节点和你要搜索节点N和节点1，这是你开始搜索表单的节点，被链接到N，那么你会立刻发现它。然而，在此之前发生的DFS可能会扩大整个图形。 DFS只会更快，如果你很幸运，而BFS会更快，如果你搜索点距离较近你的出发点。总之，它们都依赖于输入，但我会选择BFS。

DFS也更难代码而不递归，这使得BFS实际上有点快，因为它是一种迭代算法。

如果你能正常化的节点（从1到10 000给它们编号，并以数字访问它们），那么你就可以轻松地Exists[i] = true if node i is in the graph and false otherwise，给你O（1）查找时间。否则，请考虑使用哈希表如果正常化是不可能的，或者你不想做它

Answer 4

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

1. 它使用的内存少得多
2. 更容易实施

Answer 5

深度第一和广度第一算法几乎相同的，除了在一个（DFS）使用的堆叠的，在其它（BFS）队列中，和几个所需成员变量。实现他们两个不应该占用你太多额外的时间。

此外，如果你有顶点，然后你的样子了为O（V）反正邻接表。所以，做这些事将通过使用其他两个搜索之一来获得。

Answer 6

我在康拉德的帖子发表评论，但我不能评论却又如此......我想第二，如果你在通过简单的线性搜索实现DFS或BFS它不会使性能差异的名单。您搜索的图中的一个特定节点并不依赖于图的结构，因此它没有必要给自己局限于图算法。在编码时间方面，线性搜索是最好的选择;如果你想刷你的技能，在图算法，实现DFS或BFS，无论你觉得像。

Answer 7

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

这个想法是，计算从源顶点到正在处理的当前顶点的距离，然后“猜测”从当前顶点到目标的距离。

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

如果你的启发式（你的“猜测”）是可接受的，也就是说，如果它是 总是 低估，那么您一定会在第一次访问目标顶点时找到到达目标顶点的最短路径。如果您的启发式方法不可接受，那么您将必须运行算法才能找到最短路径（尽管听起来您并不关心最短路径，而只关心任何路径）。

它实际上并不比广度优先搜索更难实现（实际上，您只需要添加启发式搜索），但它可能会产生更快的结果。唯一困难的部分是弄清楚你的启发式。对于表示地理位置的顶点，常见的启发式方法是使用“as-the-crow-flies”（直接距离）启发式方法。

Answer 8

线性搜索比BFS和DFS更快。但不是线性搜索快将与设置为零步骤成本A *。当步成本是零，A *只会扩大是最接近目标节点的节点。如果步成本为零，则每一个节点的路径成本是零，A *不会用较短的路径优先级的节点。这就是你想要的东西，因为你并不需要的最短路径。

A *是比线性搜索更快，因为线性搜索将最有可能完全ø后（N / 2）次迭代（每个节点具有作为目标节点的机会均等），但A *优先显示具有作为机会较高节点一个目标节点。