Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Many graph search algorithms can be expressed as a generic graph search algorithm where you have a "white set" of unvisited nodes, a "black set" of visited nodes, and a "grey set" of nodes that you've encountered but have yet to visit. The structure of the grey set determines the algorithm:

Queue = BFS

Stack = DFS

Priority queue by distance from start = Dijkstra's algorithm

Priority queue by distance + heuristic = A*

Bounded priority queue by heuristic = Beam search

Priority queue by connecting edge weights = Prim's algorithm

Pointer reversal = Mark & sweep garbage collector

Check on whether it points into from-space = Copying garbage collector.



Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: