Showing posts with label depth first search. Show all posts
Showing posts with label depth first search. Show all posts

Tuesday, October 25, 2011

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

Depth First Search Code

Output:
Visits: ABCDE