在为我的 Graph 实现实现了大部分常用和需要的功能之后，我意识到有几个功能（删除顶点、搜索顶点和获取顶点）没有“最佳”实现。
我正在为我的 Graph 实现使用带有链接列表的邻接列表，并且我正在一个接一个地搜索一个顶点，直到找到我想要的那个。就像我说的，我意识到我没有使用“最好的”实现。我可以有 10000 个顶点并且需要搜索最后一个顶点，但是那个顶点可以有一个到第一个顶点的链接，这会大大加快速度。但这只是一个假设的情况，它可能会发生也可能不会发生。
那么，您推荐什么算法用于搜索查找？我们的老师主要谈论广度优先和深度优先（还有 Dikjstra 的算法，但那是完全不同的主题）。在这两者之间，你推荐哪一个？
如果我能同时实现这两者就完美了，但我没有时间，我需要拿起一个并在第一阶段截止日期临近时实现它......
我的猜测是，使用深度优先，似乎更容易实现，并且查看它们的工作方式，这似乎是最好的选择。但这实际上取决于输入。
但是你们有什么建议呢？
如果你有一个邻接列表，搜索一个顶点仅仅意味着遍历该列表。您甚至可以订购列表以减少所需的查找操作。
从性能的角度来看，图遍历（例如 DFS 或 BFS）不会改善这一点。
Finding and deleting nodes in a graph is a "search" problem not a graph problem, so to make it better than O(n) = linear search, BFS, DFS, you need to store your nodes in a different data structure optimized for searching or sort them. This gives you O(log n) for find and delete operations. Candidatas are tree structures like b-trees or hash tables. If you want to code the stuff yourself I would go for a hash table which normally gives very good performance and is reasonably easy to implement.
我认为 BFS 通常平均速度会更快。阅读DFS和BFS的 wiki 页面。
我说 BFS 更快的原因是因为它具有按节点与起始节点的距离顺序到达节点的属性。因此，如果您的图表有N节点，并且您想搜索 nodeN并且 node 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) 查找时间。否则，如果无法进行规范化或您不想这样做，请考虑使用哈希表。
深度优先搜索是最好的，因为
深度优先和广度优先算法几乎相同，除了在一个（DFS）中使用堆栈，在另一个（BFS）中使用队列，以及一些必需的成员变量。实施它们不应该花费你太多额外的时间。
此外，如果您有顶点的邻接列表，那么无论如何您的查找都是 O(V)。通过使用其他两个搜索之一将几乎没有获得任何东西。
我想对 Konrad 的帖子发表评论，但我还不能发表评论……我想再说一下，如果您通过列表中的简单线性搜索实现 DFS 或 BFS，它不会对性能产生影响。您在图中搜索特定节点不依赖于图的结构，因此不必将自己局限于图算法。在编码时间方面，线性搜索是最佳选择；如果你想提高你在图算法方面的技能，实现 DFS 或 BFS，随你的便。
如果您正在搜索特定顶点并在找到它时终止，我建议您使用A*，这是最佳优先搜索。
这个想法是你计算从源顶点到你正在处理的当前顶点的距离，然后“猜测”从当前顶点到目标的距离。
您从源头开始，计算距离 (0) 加上猜测（无论可能是什么），然后将其添加到优先级队列中，其中优先级为距离 + 猜测。在每一步中，您删除距离最小的元素 + 猜测，对其邻接列表中的每个顶点进行计算，并将它们放在优先级队列中。找到目标顶点时停止。
如果你的启发式（你的“猜测”）是可以接受的，也就是说，如果它总是被低估，那么你可以保证在你第一次访问它时找到到目标顶点的最短路径。如果您的启发式方法不可接受，那么您将不得不运行算法完成以找到最短路径（尽管听起来您不关心最短路径，只是任何路径）。
It's not really any more difficult to implement than a breadth-first search (you just have to add the heuristic, really) but it will probably yield faster results. The only hard part is figuring out your heuristic. For vertices that represent geographical locations, a common heuristic is to use an "as-the-crow-flies" (direct distance) heuristic.
Linear search is faster than BFS and DFS. But faster than linear search would be A* with the step cost set to zero. When the step cost is zero, A* will only expand the nodes that are closest to a goal node. If the step cost is zero then every node's path cost is zero and A* won't prioritize nodes with a shorter path. That's what you want since you don't need the shortest path.
A* is faster than linear search because linear search will most likely complete after O(n/2) iterations (each node has an equal chance of being a goal node) but A* prioritizes nodes that have a higher chance of being a goal node.