Graphs (A Brief Overview, Depth-First Search algorithm)

   This article is intended to be a slight introduction to graph theory and in particular to it’s applications in computer science. First thing’s first: what is a graph?
In mathematics the so called “graph” (not to be confused with a “diagram”) is in general a representation of a set of objects. Those objects are defined by mathematical abstractions called vertices (or nodes). Some of them can be connected by links, which in this article will appear under the name “edges”. The edges can have a direction and can be assigned with a particular weight.

   Graph theoretical ideas are highly utilized, especially in research areas such as networking, data mining, image segmentation, clustering, image capturing, etc. A few examples:
– modeling of network topologies can be done using graph concepts
– a data structure can be designed in the form of tree which in turn utilized vertices and edges
– the graph coloring concept can be applied in resource allocation, scheduling.
– and many, many more..
This leads to the development of new algorithms and new theorems that can be used in enormous applications. [1]
I will explain and provide a simple Java implementation of one of the easiest algorithms – the depth-first search of a directed graph.
Two last things you need to know before I begin are:
1. There are two main types of graphs: the undirected and the directed (depends on the type of the edges in the graph)
2. There are two main ways to represent a graph: by its adjacency matrix or by its adjacency list.

   The basic idea of the Depth-first search is to start at some arbitrary vertex* v and explore as far as possible along each branch. Once all of v’s edges have been explored, the search “backtracks” to look for edges leaving the vertex from which v was discovered. This process continues until we have all the vertices that are reachable from the original source vertex. [2]

   When the depth-first search has backtracked all the way back to the original source vertex v, it has built a DFS tree of all vertices reachable from that source. If there still undiscovered vertices in the graph then it selects one of them as the source for another DFS tree. The result is a forest of DFS-trees. The strategy the algorithm follows is to search “deeper” in the graph whenever it can achieve more vertices.

 Here is a picture better than any longer explanation:

   Depth-first search finds application as a building block of more complex algorithms including topological sorting, maze generation, puzzle solving, etc.
You can check the implementation my colleague Rene Rahn and I made a while ago:
GraphDFS

* if we have a tree formed structure – we start at the root
Sources:
[1] Applications of graph theory, an overview. S.G.Shirinivas, S.Vetrivel, Dr. N.M.Elango
[2] Introduction to algorithms. T.Cormen
[3] Applications of graph theory. A.Dharwadker, S.Pirzada

---