Introduction to Algorithms:
Finding a path through a network

Paul Taylor

13 March 2001

This is just a list of the topics that I talked about during today's lecture. Please see Richard Bornat's notes and the textbooks for detailed treatments.

1  Stacks and queues as arrays

Here is most of a Stack JAVA class.
    class Stack {
       private int[] array;
       private int   contents; // stack pointer
       private int   capacity; // array.length;
       public Stack () { this (10); }  // default size
       public Stack (int size) {
          array = new int[size];
          contents = 0;
          capacity = size;
       }
       public void push (int new_value) {
          if (capacity==contents) resize ();
          array[contents] = new_value;
          contents++;
       }
       public int pop () {
          if (contents==0) throw IllegalArgumentException ("Stack Underflow");
          contents--;
          return array[contents];
       }
       private int resize () {
          // you can do this one!
       }
For a Queue you need two pointers: one to write and one to read. The array is used in a "circular" fashion, which means some if statements.
This is a good programming exercise. I recommend that you do it.

2  Boolean-valued depth-first recursive search in a tree

We use children[][] to represent the tree (or, equally well, directed graph or binary relation) as follows:
for node #i, children[i] is an array, which lists (as its values) the numbers of the nodes that are the children of node #i.
Using this, here is a depth-first search that says whether there is a path from source to dest.
    boolean exists_path (int source, int dest) {
       if (source==dest) return true;
       int[] list = children [source];
       for (int i=0; i<list.length; i++) {
          int child = list[i];
          if (exists_path (child, dest)) return true;
       }
       return false;
    }
Modify this so that it returns a Vector containing the numbers of the successive nodes in the path. Better: make this an array, if you can think of a way of finding out the length of the path before you need to allocate it.

3  Depth-first search using a stack

4  Breadth-first search using a queue

5  Shortest (positive-)weighted path using a heap

This is www.PaulTaylor.EU/algorithms/graph.html and it was derived from algorithms/graph.tex which was last modified on 21 July 2007.