Depth First Search

Definitions
Adjacency
Two vertices are said to be adjacent to one another if they are connected by a single edge.
Paths
A path is a sequence of edges. There can be more than one path between two vertices.
Connected Graphs
A graph is said to be connected if there is at least on path from every vertex to every other vertex.

Representing a Graph in a Program
Vertices
In a very abstract graph program you could simply number the vertices 0 to N-1
class Vertex { public char label; // label (e.g. ‘A’) public boolean wasVisited; public Vertext(char lab) { // constructor label = lab; wasVistied = false; } } Edges
Two methods are commonly used for graphs: the adjacency matrix and the adjacency list.
The Adjacency Matrix
An adjacency matrix is a two-dimensional array in which the elements indicate whether an edge is present between two vertices. If a graph has N vertices, the adjacency matrix is an NxN array.
The Adjacency List
The list in adjacency list refers to a linked list. An adjacency list is an array of lists. Each individual list shows what vertices a given vertex is adjacent to.

Depth-First Search
Rule1
If possible, visit an adjacent unvisited vertex, mark it, and push it on the stack.
Rule2
If you can’t follow Rule 1, then, if possible, pop a vertex off the stack.
Rule3
If you can’t follow Rule 1 or Rule 2, you’re done.

You might say that the depth-first search algorithm likes to get as far away from the starting point as quickly as possible and returns only when it reaches a dead end. If you use the term depth to mean the distance from the starting point, you can see where the name depth-first search comes from.

Analogy
An analogy you might think about in relation to depth-first search is a maze. The maze – perhaps one of the people-size ones made of hedges, popular in England – consists of narrow passages (think of edges) and intersections where passages meet (vertices).

Depth-First Search and Game Simulations
Depth-First searches are often used in simulations of games (and game-like situations in the real world.) In a typical game you can choose one of several possible actions. Each choice leads to further choices, each of which leads to further choices, and so on into an ever-expanding tree-shaped graph of possibilities. a choice point corresponds to a vertex, and the specific choice taken corresponds to an edge, which leads to another choice-point vertex.

Chapter 13 Graphs
http://www.amazon.com/Data-Structures-Algorithms-Java-2nd/dp/0672324539/ref=sr_1_1?s=books&ie=UTF8&qid=1319590014&sr=1-1

Depth First Search Code

package com.test; //dfs.java //demonstrates depth-first search //to run this program: C>java DFSApp //////////////////////////////////////////////////////////////// class StackX { private final int SIZE = 20; private int[] st; private int top; // ———————————————————– public StackX() // constructor { st = new int[SIZE]; // make array top = -1; } // ———————————————————– public void push(int j) // put item on stack { st[++top] = j; } // ———————————————————– public int pop() // take item off stack { return st[top–]; } // ———————————————————— public int peek() // peek at top of stack { return st[top]; } // ———————————————————— public boolean isEmpty() // true if nothing on stack- { return (top == -1); } // ———————————————————— } // end class StackX // ////////////////////////////////////////////////////////////// class Vertex { public char label; // label (e.g. ‘A’) public boolean wasVisited; // ———————————————————— public Vertex(char lab) // constructor { label = lab; wasVisited = false; } // ———————————————————— } // end class Vertex // ////////////////////////////////////////////////////////////// class Graph { private final int MAX_VERTS = 20; private Vertex vertexList[]; // list of vertices private int adjMat[][]; // adjacency matrix private int nVerts; // current number of vertices private StackX theStack; // ———————————————————– public Graph() // constructor { vertexList = new Vertex[MAX_VERTS]; // adjacency matrix adjMat = new int[MAX_VERTS][MAX_VERTS]; nVerts = 0; for (int j = 0; j < MAX_VERTS; j++) // set adjacency for (int k = 0; k < MAX_VERTS; k++) // matrix to 0 adjMat[j][k] = 0; theStack = new StackX(); } // end constructor // ———————————————————– public void addVertex(char lab) { vertexList[nVerts++] = new Vertex(lab); } // ———————————————————– public void addEdge(int start, int end) { adjMat[start][end] = 1; adjMat[end][start] = 1; } // ———————————————————— public void displayVertex(int v) { System.out.print(vertexList[v].label); } // ———————————————————— public void dfs() // depth-first search { // begin at vertex 0 vertexList[0].wasVisited = true; // mark it displayVertex(0); // display it theStack.push(0); // push it while (!theStack.isEmpty()) // until stack empty, { // get an unvisited vertex adjacent to stack top int v = getAdjUnvisitedVertex(theStack.peek()); if (v == -1) // if no such vertex, theStack.pop(); else // if it exists, { vertexList[v].wasVisited = true; // mark it displayVertex(v); // display it theStack.push(v); // push it } } // end while // stack is empty, so we’re done for (int j = 0; j < nVerts; j++) // reset flags vertexList[j].wasVisited = false; } // end dfs // ———————————————————— // returns an unvisited vertex adj to v public int getAdjUnvisitedVertex(int v) { for (int j = 0; j < nVerts; j++) if (adjMat[v][j] == 1 && vertexList[j].wasVisited == false) return j; return -1; } // end getAdjUnvisitedVertex() // ———————————————————— } // end class Graph // ////////////////////////////////////////////////////////////// class DFSApp { public static void main(String[] args) { Graph theGraph = new Graph(); theGraph.addVertex('A'); // 0 (start for dfs) theGraph.addVertex('B'); // 1 theGraph.addVertex('C'); // 2 theGraph.addVertex('D'); // 3 theGraph.addVertex('E'); // 4 theGraph.addEdge(0, 1); // AB theGraph.addEdge(1, 2); // BC theGraph.addEdge(0, 3); // AD theGraph.addEdge(3, 4); // DE System.out.print("Visits: "); theGraph.dfs(); // depth-first search System.out.println(); } // end main() } // end class DFSApp // ////////////////////////////////////////////////////////////// Output:

Visits: ABCDE