Search Algorithms - KeynesYouDigIt/Knowledge GitHub Wiki

Depth-First Search

  • Used in searching trees and graphs

Implementation

  1. Follow a path from the beginning vertex until the last vertex
  2. Then follow the next path
  3. Until there are no paths left.

Breadth-First Search

  • Used in searching trees and graphs
  • Uses a queue
  • Finds the shortest path

Implementation

  1. Find an unvisted vertex that is adjacent to the current vertex
    • Add it to the list of visited vertices
    • Add it to the queue
  2. Take the next vertex (v) from the graph and add it to the list of visited vertices
  3. Add all unmarked vertices that are adjacent to v and add them to the queue

Sequential Search

  • Also called linear or brute-force

Binary Search

Self-Sorting Data

Searching Text