# Introduction to Algorithms:Finding a path through a network

### 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.

## 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.