在图上搜索顶点的最佳和最简单的算法？
在为我的图实现实现了大多数常见和所需的函数之后，我意识到有几个函数（删除顶点、搜索顶点和获取顶点）没有“最佳”实现。
我在图实现中使用带有链表的邻接表，并且我一个接一个地搜索顶点，直到找到我想要的顶点。就像我说的，我意识到我没有使用“最佳”实现。我可以有 10000 个顶点，需要搜索最后一个顶点，但该顶点可能有到第一个顶点的链接，这会大大加快速度。但这只是一个假设的情况，它可能会发生，也可能不会发生。
那么，您推荐什么算法用于搜索查找？我们的老师主要谈论的是广度优先和深度优先（还有 Dikjstra 的算法，但那是一个完全不同的主题）。在这两者之间，您推荐哪一个？
如果我可以同时实现这两个，那就太完美了，但我没有时间，我需要拿起一个并实现它，第一阶段的截止日期即将到来......
我的猜测是，似乎是采用深度优先更容易实施并看看他们的工作方式，这似乎是最好的选择。但这实际上取决于输入。
但你们有什么建议呢？
After implementing most of the common and needed functions for my Graph implementation, I realized that a couple of functions (remove vertex, search vertex and get vertex) don't have the "best" implementation.
I'm using adjacency lists with linked lists for my Graph implementation and I was searching one vertex after the other until it finds the one I want. Like I said, I realized I was not using the "best" implementation. I can have 10000 vertices and need to search for the last one, but that vertex could have a link to the first one, which would speed up things considerably. But that's just an hypothetical case, it may or may not happen.
So, what algorithm do you recommend for search lookup? Our teachers talked about Breadth-first and Depth-first mostly (and Dikjstra' algorithm, but that's a completely different subject). Between those two, which one do you recommend?
It would be perfect if I could implement both but I don't have time for that, I need to pick up one and implement it has the first phase deadline is approaching...
My guess, is to go with Depth-first, seems easier to implement and looking at the way they work, it seems a best bet. But that really depends on the input.
But what do you guys suggest?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（8）
如果您有一个邻接列表，搜索顶点就意味着遍历该列表。您甚至可以对列表进行排序以减少所需的查找操作。
从性能的角度来看，图遍历（例如 DFS 或 BFS）不会改善这一点。
If you’ve got an adjacency list, searching for a vertex simply means traversing that list. You could perhaps even order the list to decrease the needed lookup operations.
A graph traversal (such as DFS or BFS) won’t improve this from a performance point of view.
在图中查找和删除节点是一个“搜索”问题而不是图问题，因此为了使其比 O(n) = 线性搜索、BFS、DFS 更好，您需要将节点存储在针对搜索而优化的不同数据结构中或对它们进行排序。这为查找和删除操作提供了 O(log n) 时间复杂度。候选数据是树结构，如 B 树或哈希表。如果您想自己编写这些内容，我会选择哈希表，它通常会提供非常好的性能并且相当容易实现。
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。
我之所以说 BFS 更快，是因为它具有按照距起始节点的距离顺序到达节点的属性。因此，如果您的图表有
N个节点，并且您想要搜索节点N和节点1（这是您启动搜索表单的节点），链接到N，那么你会立即找到它。然而，DFS 可能会在此之前扩展整个图。如果你幸运的话，DFS 只会更快，而如果你搜索的节点靠近你的起始节点，BFS 会更快。简而言之，它们都取决于输入，但我会选择 BFS。如果没有递归，DFS 也更难编码，这使得 BFS 在实践中更快一些，因为它是一种迭代算法。
如果您可以标准化节点（将它们编号为 1 到 10 000 并按编号访问它们），那么您可以轻松地保持
Exists[i] = true（如果节点 i 在图中），否则为 false，给你 O(1) 的查找时间。否则，如果标准化不可能或者您不想这样做，请考虑使用 哈希表它。I think BFS would usually be faster an average. Read the wiki pages for DFS and BFS.
The reason I say BFS is faster is because it has the property of reaching nodes in order of their distance from your starting node. So if your graph has
Nnodes and you want to search for nodeNand node1, which is the node you start your search form, is linked toN, then you will find it immediately. DFS might expand the whole graph before this happens however. DFS will only be faster if you get lucky, while BFS will be faster if the nodes you search for are close to your starting node. In short, they both depend on the input, but I would choose BFS.DFS is also harder to code without recursion, which makes BFS a bit faster in practice, since it is an iterative algorithm.
If you can normalize your nodes (number them from 1 to 10 000 and access them by number), then you can easily keep
Exists[i] = true if node i is in the graph and false otherwise, giving you O(1) lookup time. Otherwise, consider using a hash table if normalization is not possible or you don't want to do it.深度优先搜索是最好的，因为
Depth-first search is best because
深度优先和广度优先算法几乎相同，除了其中一个使用堆栈（DFS）、另一个使用队列（BFS）以及一些必需的成员变量之外。实现它们不会花费您太多额外的时间。
另外，如果你有一个顶点的邻接列表，那么你的查找无论如何都是 O(V) 。因此，通过使用其他两个搜索之一几乎不会获得任何结果。
the depth first and breadth first algorithms are almost identical, except for the use of a stack in one (DFS), a queue in the other (BFS), and a few required member variables. Implementing them both shouldn't take you much extra time.
Additionally if you have an adjacency list of the vertices then your look up with be O(V) anyway. So little to nothing will be gained via using one of the two other searches.
我想对 Konrad 的帖子发表评论，但我还不能发表评论，所以……我想补充一点，如果你在列表中通过简单的线性搜索实现 DFS 或 BFS，那么性能不会有任何影响。您对图中特定节点的搜索不依赖于图的结构，因此不必将自己局限于图算法。就编码时间而言，线性搜索是最佳选择；如果您想提高图算法方面的技能，请实现 DFS 或 BFS，无论您喜欢哪种。
I'd comment on Konrad's post but I can't comment yet so... I'd like to second that it doesn't make a difference in performance if you implement DFS or BFS over a simple linear search through your list. Your search for a particular node in the graph doesn't depend on the structure of the graph, hence it's not necessary to confine yourself to graph algorithms. In terms of coding time, the linear search is the best choice; if you want to brush up your skills in graph algorithms, implement DFS or BFS, whichever you feel like.
如果您正在搜索特定顶点并在找到它时终止，我建议使用 A*，这是最佳优先搜索。
这个想法是，计算从源顶点到正在处理的当前顶点的距离，然后“猜测”从当前顶点到目标的距离。
您从源开始，计算距离 (0) 加上猜测（无论可能是什么），并将其添加到优先级队列，其中优先级为距离 + 猜测。在每一步中，您都会删除距离最小的元素+猜测，对其邻接列表中的每个顶点进行计算并将其放入优先级队列中。当找到目标顶点时停止。
如果您的启发式（您的“猜测”）是可接受的，也就是说，如果它总是低估，那么您一定会在第一次访问目标顶点时找到到达目标顶点的最短路径。如果您的启发式方法不可接受，那么您将必须运行算法才能找到最短路径（尽管听起来您并不关心最短路径，而只关心任何路径）。
它实际上并不比广度优先搜索更难实现（实际上，您只需要添加启发式搜索），但它可能会产生更快的结果。唯一困难的部分是弄清楚你的启发式。对于表示地理位置的顶点，常见的启发式方法是使用“as-the-crow-flies”（直接距离）启发式方法。
If you are searching for a specific vertex and terminating when you find it, I would recommend using A*, which is a best-first search.
The idea is that you calculate the distance from the source vertex to the current vertex you are processing, and then "guess" the distance from the current vertex to the target.
You start at the source, calculate the distance (0) plus the guess (whatever that might be) and add it to a priority queue where the priority is distance + guess. At each step, you remove the element with the smallest distance + guess, do the calculation for each vertex in its adjacency list and stick those in the priority queue. Stop when you find the target vertex.
If your heuristic (your "guess") is admissible, that is, if it's always an under-estimate, then you are guaranteed to find the shortest path to your target vertex the first time you visit it. If your heuristic is not admissible, then you will have to run the algorithm to completion to find the shortest path (although it sounds like you don't care about the shortest path, just any path).
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.
线性搜索比 BFS 和 DFS 更快。但比线性搜索更快的是 A*，且步骤成本设置为零。当步骤成本为零时，A*只会扩展距离目标节点最近的节点。如果步骤成本为零，则每个节点的路径成本为零，并且 A* 不会优先考虑路径较短的节点。这就是您想要的，因为您不需要最短路径。
A* 比线性搜索更快，因为线性搜索很可能在 O(n/2) 次迭代后完成（每个节点成为目标节点的机会均等），但 A* 会优先考虑成为目标节点的机会较高的节点。
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.