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