Home / Technical / Programming / Algorithm / Basic methods for searching graphs

Basic methods for searching graphs

There are two methods for searching graphs that are extremely prevalent, and will form the foundations for more advanced algorithms later on. These two methods are the Depth First Search and the Breadth First Search.


Depth First Search

The depth first search method, which will utilize a stack. This stack can either by represented explicitly (by a stack data-type in our language) or implicitly when using recursive functions.

Stack is one of the simplest data structures available. There are four main operations on a stack:

Push – Adds an element to the top of the stack
Pop – Removes the top element from the stack
Top – Returns the top element on the stack
Empty – Tests if the stack is empty or not

In Java, we use the Stack class:

import java.util.*;
Stack stack = new Stack();

The depth first search is well geared towards problems where we want to find any solution to the problem (not necessarily the shortest path), or to visit all of the nodes in the graph.

the memory for the implicit stack, is more limited than the general heap memory.

Stack memory is used whenever you call a function; the variables to the function are pushed onto the stack by the compiler for you. When using a recursive function, the variables keep getting pushed on until the function returns. Also any variables the compiler needs to save between function calls must be pushed onto the stack as well. This makes it somewhat difficult to predict if you will run into stack difficulties. I recommend using the explicit Depth First search for every situation you are at least somewhat concerned about recursion depth.

Basic Structure of DFS

void dfs(node start) {
 stack s;
 while (s.empty() == false) {
  top = s.top();
  mark top as visited;

  check for termination condition

  add all of top’s unvisited neighbors to the stack.

  mark top as not visited;

Queue is a simple extension of the stack data type. Whereas the stack is a FILO (first-in last-out) data structure the queue is a FIFO (first-in first-out) data structure.

There are four main operations on a queue:

  1. Push – Adds an element to the back of the queue
  2. Pop – Removes the front element from the queue
  3. Front – Returns the front element on the queue
  4. Empty – Tests if the queue is empty or not

In Java, we unfortunately don’t have a Queue class, so we will approximate it with the LinkedList class.The operations map to the LinkedList class as follows:

  1. Push – boolean LinkedList.add(Object o)
  2. Pop – Object LinkedList.removeFirst()
  3. Front – Object LinkedList.getFirst()
  4. Empty – int LinkedList.size()

Breadth First Search
The Breadth First search is an extremely useful searching technique. It differs from the depth-first search in that it uses a queue to perform the search, so the order in which the nodes are visited is quite different. It has the extremely useful property that if all of the edges in a graph are unweighted (or the same weight) then the first time a node is visited is the shortest path to that node from the source node.

void bfs(node start) {
 queue s;
 while (s.empty() == false) {
  top = s.front();
  mark top as visited;

  check for termination condition (have we reached the node we want to?)

  add all of top’s unvisited neighbors to the stack. 

DFS and BFS differ only in the data structure used and BFS doesn’t mark top as unvisited again.

About Mohammad Khazab

%d bloggers like this: