Graphs
02 Sep 2014Graphs are data structures to represent road networks, the web, social networks etc. Moreover, hundreds of computational problems are related to graphs.They have two main ingredient which are;
 \(Vertices (V)\) as known as nodes.

\(Edges (E)\) : pair of vertices
 can be undirected.
 or directed.
When we are talking about of a graph, \( G = (V , E) \) notation refers to a graph \( G \) which has \( V \) number of vertices and \( E \) number of edges.
Graph Representations
Graphs are commonly represented by two ways related to their structures. These are:
 Adjacency List Representation
 Adjacency Matrix Representation
Both representation has their own advantages and disadvantages. Adjacency list is preferred when the graph is sparse; which means \( E \) is much less than \( V^{2} \). Adjacency matrix is preferred when the graph is dense; which means \( E \) is close to \( V^{2} \).
1. Adjacency Matrix
Adjacency matrix of a graph \( G = (V , E) \) consists of a \( V x V \) matrix A where;
 \(A_{ij}\) = 1 if G has an ij edge.
 \(A_{ij}\) = 0 otherwise.
The adjacency matrix representation of a graph requires \( \theta(V^{2}) \) memory space indepently on E.
2. Adjacency List
Adjacency list representation of a graph G = (V , E) contains an array of vertices – lets call it Adj , and for each vertex \( u \in V \), the adjacency list \( Adj[u] \) contains all adjacent vertices \( v \) such that there is an edge \( (u , v) \in E \). In other words, \( Adj[u] \) has an array which contains only adjacent vertices to it. Thus, we can briefly say the main ingredients are;
 array (or list) of vertices.
 array (or list) of edges.
The memory for adjacency list requires \( \theta (V+E) \).
Graph Search
Now we will see two main algorithm to search a graph;
 Breadth first search.
 Depth first search.
1. Breadth First Search
Breadth first search explores graph level by level with using a queue data structure. By this search behavior we are able to compute shortest paths in a given graph \( G = (V , E) \). The algorithm starts from a given source vertex s ,and it searches it’s adjacent level of vertices ,and goes on.
 Initialize each vertex except the source.
 Take vertex v from the queue.
 Iterate each node u in adjacency list of v if it is unvisited.
 Put every node u in queue and mark it as visited.
A visual illustration is shown below;
The Vertex class looks like below;
public class Vertex {
private boolean visited;
private int distance;
private Vertex parent;
private ArrayList<Vertex> adjList;
private final String label;
// getters and setters
}
and the code of breadFirstSearch procedure can be seen below;
public void breadthFirstSearch(ArrayList<Vertex> graph, Vertex source) {
// check if graph or source is null
if (graph == null  source == null) {
throw new IllegalArgumentException("Parameters are illegal");
}
initVertices(graph, source);
initSourceVertex(source);
Queue<Vertex> queue = new LinkedList<>();
queue.add(source);
while (!queue.isEmpty()) {
// take next vertex from the queue
Vertex v = queue.poll();
// iterate in adjacency list of v
for (Vertex u : v.getAdjList()) {
if (!u.isVisited()) {
// set u as visited
u.setVisited(true);
u.setDistance(v.getDistance() + 1);
u.setParent(v);
// put u in queue to be processed in next level
queue.add(u);
}
}
}
}
private void initVertices(ArrayList<Vertex> graph, Vertex source) {
for (Vertex vertex : graph) {
if (vertex != source) {
vertex.setVisited(false);
vertex.setDistance(Integer.MAX_VALUE);
vertex.setParent(null);
}
}
}
private void initSourceVertex(Vertex source) {
source.setVisited(true);
source.setParent(null);
source.setDistance(0);
}
The running time of initializing vertices will take \( O(V) \) time, and total running time of breadthfirst search takes \( O(V + E) \).
2. Depth First Search
Depth first search explores vertices by going deeper and deeper in the graph. So, at every turn an adjacent undiscovered vertex is selected from the most recently visited vertex. Whenever, a vertex is finished (when there is no any undiscovered vertex from it) then depth first search backtracks until it finds another unfinished vertex from most discovered vertex. If there is any undiscovered vertex left, then depth first search will select any undiscovered vertex as a source ,and applies dfs on it. This process continues until every vertex is finished. We are going to use discovery time and finishing time for every vertex.
 Initialize each vertex as undiscovered and set their discovery and finishing times to 0.
 Take an undiscovered vertex v from the graph and apply a depth first search on it.
 Adjust discovery time of current vertex ,and continue to search from its adjacency list. Thus, take an adjacent undiscovered vertex u from current discovered vertex, and go deeper.
 If there is no any undiscovered vertex from last discovered vertex then mark that vertex as finished, and initialize its finishing time. Later on, backtrack while until you hit an undiscovered vertex.
 Do depth first search until every vertices is finished.
A visual illustration of depthfirstsearch is shown below;
Vertex for depthfirstsearch will look like below;
public class Vertex {
private boolean explored;
private boolean finished;
private Vertex parent;
private ArrayList<Vertex> adjList;
private final String label;
private int discoveredTime;
private int finishedTime;
// getters and setters
}
Later on, implementation of depthfirstsearch class with main two procedures dfs, and dfsVisit could be seen below;
public class DepthFirstSearch {
// global timer to set discovery and finishing times of each vertex
private static int time = 0;
public void dfs(ArrayList<Vertex> graph) {
if (graph == null) {
throw new IllegalArgumentException("Graph is null");
}
// init all vertices
initVertices(graph);
for (Vertex v : graph) {
// select a vertex 'v' if it is unexplored
if (!v.isExplored()) {
// discover every vertex which are reachable from 'v'
dfsVisit(v);
}
}
}
private void dfsVisit(Vertex v) {
time = time + 1;
// set discovery time of 'v'
v.setDiscoveryTime(time);
// set it as explored (not finished yet)
v.setExplored(true);
for (Vertex u : v.getAdjList()) {
if (!u.isExplored()) {
dfsVisit(u);
}
}
time = time + 1;
// finally all vertices reachable from 'v' are finished, so mark it as finished
v.setFinished(true);
// set 'v' s finis
v.setFinishingTime(time);
}
private void initVertices(ArrayList<Vertex> graph) {
for (Vertex vertex : graph) {
vertex.setExplored(false);
vertex.setDiscoveryTime(0);
vertex.setFinishedTime(0);
}
}
}
The running time of initializing vertices will take \( O(V) \) time, and total running time of depthfirst search takes \( O(V + E) \).