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.
- A*: special case of best-first search that uses heuristics to improve speed
- 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)
- Backtracking: abandons partial solutions when they are found not to satisfy a complete solution
- Beam search: is a heuristic search algorithm that is an optimization ofbest-first searchthat reduces its memory requirement
- Beam stack search: integrates backtracking withbeam search
- Best-first search: traverses a graph in the order of likely importance using apriority queue
- Bidirectional search: find the shortest path from an initial vertex to a goal vertex in a directed graph
- Breadth-first search: traverses a graph level by level
- Brute-force search: An exhaustive and reliable search method, but computationally inefficient in many applications.
- D*: anincremental heuristic searchalgorithm
- Depth-first search: traverses a graph branch by branch
- Dijkstra's algorithm: A special case of A* for which no heuristic function is used
- General Problem Solver: a seminal theorem-proving algorithm intended to work as a universal problem solver machine.
- Iterative deepening depth-first search (IDDFS): a state-space search strategy
- Jump point search: An optimization to A* which may reduce computation time by an order of magnitude using further heuristics.
- Lexicographic breadth-first search(also known as Lex-BFS): a linear time algorithm for ordering the vertices of a graph
- Uniform-cost search: atree searchthat finds the lowest-cost route where costs vary
- 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.