Best and easiest algorithm to find the top on the chart?

Question

After implementing most of the general and necessary functions for my implementation of Graph, I realized that several functions (delete the vertex, search vertex and get the vertex) do not have a "better" implementation.

I use adjacency lists with linked lists for my implementation of the Graph, and I searched one vertex after another until I find the one I want. As I said, I realized that I did not use the “best” implementation. I can have 10,000 vertices and need to look for the last one, but this vertex can have a link to the first one, which will significantly speed up the work. But this is just a hypothetical case, it may or may not happen.

So, what algorithm do you recommend for your search? Our teachers talked about the algorithm "Latitude-first" and "Depth-first basically" (and "Dikistra", but this is a completely different subject). Between the two, which ones do you recommend?

It would be great if I could implement both options, but I do not have time for this, I need to pick one and implement it when the first phase approaches ...

My guess is to go with Deep-first, it seems easier to implement and look at how they work seems like the best choice. But it really depends on the input.

But what do you offer?

Answer 1

If you have an adjacency list, finding the top just means moving that list. Perhaps you can even order a list to reduce the number of searches you need.

Bypassing a graph (such as DFS or BFS) will not improve it in terms of performance.

Answer 2

Finding and deleting nodes in a graph is a "search" problem, not a graph problem, therefore, to make it better than O (n) = linear search, BFS, DFS, you need to store your nodes in a different data structure optimized for search or sorting. This gives you O (log n) for search and delete operations. Candidates are tree structures such as b-trees or hash tables. If you want to code the material yourself, I would go to a hash table that usually gives very good performance and is reasonably easy to implement.

Answer 3

I think BFS will usually be faster than 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 the order of their distance from your starting node. Therefore, if your graph has N nodes and you want to search for node N and node 1 , which is node, you start your search form, attach to N , then you will find it immediately. DFS can expand the entire schedule before this happens. DFS will be faster if you're lucky, and BFS will be faster if the nodes you are looking for are close to your starting node. In short, they are both input dependent, but I would choose BFS.

DFS is also more difficult to encode without recursion, which makes BFS faster in practice because it is an iterative algorithm.

If you can normalize your nodes (their number is from 1 to 10,000 and access them by number), you can easily save Exists[i] = true if node i is in the graph and false otherwise , giving you O (1) search time. Otherwise, consider using a hash table if normalization is not possible or you do not want to do this.

Answer 4

Depth search is best because

• It uses much less memory.
• Easier to implement

Answer 5

the first and latitudinal depth algorithms are almost identical, with the exception of using the stack in one (DFS), the queue in the other (BFS), and several required member variables. Implementing both of them should not take much time.

Also, if you have a vertex adjacency list, then your look with O (V) anyway. Thus, little can be obtained using one of the other two searches.

Answer 6

I would comment on the Konrad post, but I can’t comment yet ... I would like to say that this does not affect performance if you implement DFS or BFS through a simple linear search through your list. The search for a specific node in a graph does not depend on the structure of the graph, so there is no need to be limited to graph algorithms. In terms of coding time, linear search is the best choice; if you want to improve your skills in graph algorithms, implement DFS or BFS, depending on how you feel.

Answer 7

If you are looking for a specific vertex and conclude when you find it, I would recommend using A * , which is the best -first search.

The idea is that you calculate the distance from the original vertex to the current vertex that you are processing, and then “guess” the distance from the current vertex to the target.

You start from the source, calculate the distance (0) plus fortune telling (no matter what it may be) and add it to the priority queue, where the priority is the distance + guess. At each step, you delete the element with the smallest distance + guess if you are performing calculations for each vertex in the adjacency list and inserting them into the priority queue. Stop when you find the target peak.

If your heuristic (your “hunch”) is acceptable, that is, if it is always underestimated, you are guaranteed to find the shortest path to your target peak on your first visit. If your heuristic is unacceptable, you will need to run the algorithm before completion to find the shortest path (although it sounds like you don't need the shortest path, just any path).

No more difficult to implement than a breadth-first search (you just need to add a heuristic, really), but this will probably give faster results. The only hard part is figuring out your heuristic. For peaks that represent geographic locations, a common heuristic is to use crow-fly-heuristics (forward distance).

Answer 8

Linear searches are faster than BFS and DFS. But faster than a linear search, there will be A * with zero step cost. When the step value is zero, A * will expand only those nodes that are closest to the target node. If the step cost is zero, then the cost of each path to the node is zero, and A * will not set priorities for nodes with a shorter path. This is what you want, since you do not need the shortest path.

A * is faster than a linear search, because a linear search will most likely end after O (n / 2) iterations (each node has an equal chance of becoming a target node), but A * gives priority to nodes that have a higher chance of becoming a target node,