How many Graph Searching Algorithms you know

14 July, 2021
289 read  ·  1 Hearts

If you are familiar with Computer Science or you are just a Programmer, you might have come across a data structure called Graph. That means you also know the algorithms used for searching in Graph.

But there are more Graph Searching algorithms than we think, If you even know the names of all of them, you are a legend in Graph Data Structure. Let's see.

  1. A*: special case of best-first search that uses heuristics to improve speed
  2. B*: a best-first graph search algorithm that finds the least-cost path from a given initial node to any goal node (out of one or more possible goals)
  3. Backtracking: abandons partial solutions when they are found not to satisfy a complete solution
  4. Beam search: is a heuristic search algorithm that is an optimization of best-first search that reduces its memory requirement
  5. Beam stack search: integrates backtracking with beam search
  6. Best-first search: traverses a graph in the order of likely importance using a priority queue
  7. Bidirectional search: find the shortest path from an initial vertex to a goal vertex in a directed graph
  8. Breadth-first search: traverses a graph level by level
  9. Brute-force search: An exhaustive and reliable search method, but computationally inefficient in many applications.
  10. D*: an incremental heuristic search algorithm
  11. Depth-first search: traverses a graph branch by branch
  12. Dijkstra's algorithm: A special case of A* for which no heuristic function is used
  13. General Problem Solver: a seminal theorem-proving algorithm intended to work as a universal problem solver machine.
  14. Iterative deepening depth-first search (IDDFS): a state-space search strategy
  15. Jump point search: An optimization to A* which may reduce computation time by an order of magnitude using further heuristics.
  16. Lexicographic breadth-first search (also known as Lex-BFS): a linear time algorithm for ordering the vertices of a graph
  17. Uniform-cost search: a tree search that finds the lowest-cost route where costs vary
  18. SSS*: state space search traversing a game tree in a best-first fashion similar to that of the A* search algorithm

So, How many did you already know? Comment below.

Programming Graph Search Programming computer science Data Structures
Comments  ·  0
You need to be Logged in to Comment. Login

More from @pirogrammar


Need Help? ·  About
Terms and Conditions ·  Contact ·  Privacy

© 2021 ayedot. All Rights Reserved.