Graphs - DFS

Its been a while I posted because I had been busy with other stuff.From now on i would be posting basically what I learn and how I implement it in my journey of preparing for the best interviews.

Now I am going to implement GRAPH DFS algorithm.

Graphs as we all know many people tend to fear as we implement but once you start realising the underlying beauty and power of the data-structure, you can not hold yourself implementing it.

Graphs can be represented as 2 ways: Adjacency lists or Adjacency matrices.

Here I use adjacency list because as i am using java it pretty easy to implement it using Collections framework.

DFS is pretty simple : Start with a node timestamp it and go deep and deep until u cannot go anywhere and then timestamp it. Finally you would end up creating a forest of multiple trees(Starting nodes).

Code below is self explanatory and if any one has any queries please let me know.
And the algorithm is direct implementation of book by Cormen (Introduction to Algorithms)

//Implementation of DFS on a directed graph

import java.util.ArrayList;

import java.util.HashMap;

//Class to represent each Vertex or node in a graph 

class Vertex {

int d;

int f;

String color;

Vertex predecessor;

Vertex() {

d = 0;

f = 0;

color = "white";

predecessor = null;

}

}

// Class to represent a graph [Vertex + Adjacency list]

class Graph {

ArrayList<Vertex> Vertices = new ArrayList<Vertex>(); // Array of Vertices

HashMap<Vertex, ArrayList<Vertex>> adjList = new HashMap<Vertex, ArrayList<Vertex>>(); // Adjacency

// list

static int time = 0;

// Initialize Vertices and adjacency list

Graph(int noOfVertex) {

for (int i = 0; i < noOfVertex; i++) {

Vertices.add(new Vertex());

}

for (int j = 0; j < noOfVertex; j++) {

adjList.put(Vertices.get(j), new ArrayList<Vertex>());

}

}

// Method to specify Nodes and adjacent nodes.

// Insert elements into adjacency list of a vertex

void insertInAdjList(int first, int second) {

adjList.get(Vertices.get(first)).add(Vertices.get(second));

}

// DFS Algorithm implementation

static void DFS(Graph g) {

for (Vertex u : g.Vertices) {

if (u.color.equals("white")) {

dfsVisit(g, u);

}

}

}

// Helper method to visit a node and time-stamp it exploring depth wise

static private void dfsVisit(Graph g, Vertex u) {

time = time + 1;

u.d = time;

u.color = "grey";

for (Vertex v : g.adjList.get(u)) {

if (v.color.equals("white")) {

v.predecessor = u;

dfsVisit(g, v);

}

}

u.color = "black";

time = time + 1;

u.f = time;

}

}

public class Graphmain {

public static void main(String args[]) {

Graph g = new Graph(6);

g.insertInAdjList(0, 1);

g.insertInAdjList(0, 4);

g.insertInAdjList(1, 4);

g.insertInAdjList(2, 4);

g.insertInAdjList(2, 5);

g.insertInAdjList(3, 1);

g.insertInAdjList(4, 3);

g.insertInAdjList(5, 5);

Graph.DFS(g);

for (Vertex u : g.Vertices)

System.out.println(u.d + " " + u.f);

}

}