Graph

Graph

A graph is a non-linear data structure. 

A graph G consists of vertices v (or nodes) connected by edges e (or arcs) where edges may be directed or undirected. 

G = (v,e)

The examples of graph are a social media network, computer network, Google Maps, etc.

Graph Terminology

Vertex: Vertices are the point that joints edges. It represents the data. It is also known as a node. It is denoted by a circle and it must be labeled. To construct a graph there must be at least a node. For example, house, bus stop, etc.

Edge: An edge is a line that connects two vertices. It represents the relation between the vertices. Edges are denoted by a line. For example, a path to the bus stop from your house.

Weight: It is labeled to edge. For example, the distance between two cities is 100 km, then the distance is called weight for the edge.

Path: The path is a way to reach a destination from the initial point in a sequence.

Types of Graph

Directed Graph: A graph in which edges represent direction is called a directed graph. In a directed graph, we use arrows instead of lines (edges). Direction denotes the way to reach from one node to another node. Note that in a directed graph, we can move either in one direction or in both directions. 

Undirected Graph: A graph in which edges are bidirectional is called an undirected graph. In an undirected graph, we can traverse in any direction. Note that we can use the same path for return through which we have traversed. While in the directed graph we cannot return from the same path. 

Weighted Graph: In a weighted graph, each edge contains some data (weight) such as distance, weight, height, etc. It denoted as w(e). It is used to calculate the cost of traversing from one vertex to another. 

Unweighted Graph: A graph in which edges are not associated with any value is called an unweighted graph. 

Applications of Graph

1. In Computer science graphs are used to represent the flow of computation.

2. Google maps uses graphs for building transportation systems, where intersection of two(or more) roads are considered to be a vertex and the road connecting two vertices is considered to be an edge, thus their navigation system is based on the algorithm to calculate the shortest path between two vertices.

3. In Facebook, users are considered to be the vertices and if they are friends then there is an edge running between them. Facebook’s Friend suggestion algorithm uses graph theory. Facebook is an example of undirected graph.

4. In World Wide Web, web pages are considered to be the vertices. There is an edge from a page u to other page v if there is a link of page v on page u. This is an example of Directed graph. It was the basic idea behind Google Page Ranking Algorithm.

5. In Operating System, we come across the Resource Allocation Graph where each process and resources are considered to be vertices. Edges are drawn from resources to the allocated process, or from requesting process to the requested resource. If this leads to any formation of a cycle then a deadlock will occur.

Graph Representation

Graphs can be represented using adjacency matrix and adjacency lists. 

Adjacency Matrix

Adjacency Matrix is a linear representation of graphs. This matrix stores the mapping of vertices and edges of the graph. In the adjacency matrix, vertices of the graph represent rows and columns. This means if the graph has N vertices, then the adjacency matrix will have size NxN.

If V is a set of vertices of the graph then intersection Mij in the adjacency list = 1 means there is an edge existing between vertices i and j.

The above diagram, we see that for vertex A, the intersections AB and AE are set to 1 as there is an edge from A to B and A to E. Similarly intersection BA is set to 1, as this is an undirected graph and AB = BA. Similarly, we have set all the other intersections for which there is an edge to 1. 

In case the graph is directed, the intersection Mij will be set to 1 only if there is a clear edge directed from Vi to Vj. 

Adjacency List

Instead of representing a graph as an adjacency matrix which is sequential in nature, we can also use linked representation. This linked representation is known as the adjacency list. 

An adjacency list is the array of linked list and each node in the list represents a vertex.

The presence of an edge between two vertices is denoted by a pointer from the first vertex to the second. This adjacency list is maintained for each vertex in the graph.

When we have traversed all the adjacent nodes for a particular node, we store NULL in the next pointer field of the last node of the adjacency list.

Now we will use the above graphs that we used to represent the adjacency matrix to demonstrate the adjacency list.

The above figure shows the adjacency list for the undirected graph. We see that each vertex or node has its adjacency list.

In the case of the undirected graph, the total lengths of adjacency lists are usually twice the number of edges. In the above graph, the total number of edges is 6 and the total or sum of the length of all the adjacency list is 12.

As seen from the above figure, in the directed graph the total length of the adjacency lists of the graph is equal to the number of edges in the graph. In the above graph, there are 9 edges and sum of the lengths of adjacency lists for this graph = 9.

Now let us consider the following weighted directed graph. Note that each edge of the weighted graph has a weight associated with it. So when we represent this graph with the adjacency list, we have to add a new field to each list node that will denote the weight of the edge.

Graph Implementation in Java

Java doesn’t have a default implementation of the graph data structure. However, we can implement the graph using Java Collections.

Example-1: Undirected Graph

Consider the following undirected graph with 5 vertices.

The following program will print the all the vertices and its adjacency vertices.

// FindVertices.java

import java.util.Iterator;

import java.util.LinkedList;

public class FindVertices {

  int vertices;   // No. of vertices 

  LinkedList<Integer> adj_list[]; // adjacency list declaration

  // Constructor: to initialize adjacency lists as per no of vertices 

  FindVertices(int v) { 

      vertices = v; 

      adj_list = new LinkedList[v]; 

      for (int i=0; i<v; ++i) 

          adj_list[i] = new LinkedList(); 

  } 

  //add an edge to the graph 

  void addEdge(int v, int w) { 

      adj_list[v].add(w);  // Add w to v's list. 

  } 

  public void printGraph(){

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

       if(adj_list[i].size()>0) {

System.out.print("Vertex " + i + " is connected to: ");

        for (int j = 0; j <adj_list[i].size() ; j++) 

            System.out.print(adj_list[i].get(j)+" ");

        System.out.println();

       }

      }

  }

  public static void main(String[] args) { 

  //create a graph with 5 vertices

  FindVertices g = new FindVertices(5); 

  //add edges to the graph  

  g.addEdge(0, 1); 

  g.addEdge(0, 4);

  g.addEdge(1, 2); 

  g.addEdge(1, 3); 

  g.addEdge(1, 4); 

  g.addEdge(2, 3); 

  g.addEdge(3, 4); 

  g.printGraph(); // print the edges

}

} 

The output will be:

Vertex 1 is connected to: 2 3 4 

Vertex 2 is connected to: 4 5 

Vertex 3 is connected to: 4 5 

Vertex 4 is connected to: 5 

Example-2: Weighted Graph

Consider the following weighted graph. Write a program to print all the vertices and its adjacency vertices.

// WGraph.java

import java.util.LinkedList;

class WGraph {

        int vertices;

        LinkedList<Edge> [] adjacencylist;

        WGraph(int vertices) {

              this.vertices = vertices;

              adjacencylist = new LinkedList[vertices];

               for (int i = 0; i <vertices ; i++) {  //initialize all the vertices

                    adjacencylist[i] = new LinkedList<>();

               }

          }

        public void addEdge(int source, int destination, int weight) {

            Edge edge = new Edge(source, destination, weight);

            adjacencylist[source].addFirst(edge); //for directed graph

        }

        public void printGraph(){

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

                LinkedList<Edge> list = adjacencylist[i];

                for (int j = 0; j <list.size() ; j++) 

                    System.out.println("vertex-" + i + " is connected to " +

                            list.get(j).dest + " with weight " +  list.get(j).weight);

             }

         }

        public static void main(String[] args) {

            int vertices = 6;

            WGraph graph = new WGraph(vertices);

            graph.addEdge(0, 1, 4);

            graph.addEdge(0, 2, 3);

            graph.addEdge(1, 3, 2);

            graph.addEdge(1, 2, 5);

            graph.addEdge(2, 3, 7);

            graph.addEdge(3, 4, 2);

            graph.addEdge(4, 0, 4);

            graph.addEdge(4, 1, 4);

            graph.addEdge(4, 5, 6);

            graph.printGraph();

        }

}

The class Edge is:

// Edge.java

//class to store edges of the weighted graph

public class Edge {

    int src, dest, weight;

    Edge(int src, int dest, int weight) {

            this.src = src;

            this.dest = dest;

            this.weight = weight;

        }

}

The output will be:

vertex-0 is connected to 2 with weight 3

vertex-0 is connected to 1 with weight 4

vertex-1 is connected to 2 with weight 5

vertex-1 is connected to 3 with weight 2

vertex-2 is connected to 3 with weight 7

vertex-3 is connected to 4 with weight 2

vertex-4 is connected to 5 with weight 6

vertex-4 is connected to 1 with weight 4

vertex-4 is connected to 0 with weight 4

Graph Traversal / Search

To perform any meaningful action like searching for the presence of any data, we need to traverse the graph such that each vertex and the edge of the graph is visited at least once. This is done using graph algorithms that are nothing but a set of instructions that help us to traverse the graph. (Unlike tree traversal, graph traversal may require that some vertices be visited more than once, since it is not necessarily known before transitioning to a vertex that it has already been explored. )

There are two algorithms supported to traverse the graph in Java.

1. Depth-first search (DFS)

2. Breadth-first search (BFS)

Depth-first Search (DFS)

Depth-first search (DFS) is a technique that is used to traverse a tree or a graph. DFS technique starts with a root node and then traverses the adjacent nodes of the root node by going deeper into the graph. In the DFS technique, the nodes are traversed depth-wise until there are no more children to explore.

Once we reach the leaf node (no more child nodes), the DFS backtracks and starts with other nodes and carries out traversal in a similar manner. DFS technique uses a stack data structure to store the nodes that are being traversed.

The following is the algorithm for the DFS technique.

Algorithm

1. Start with the root node and insert it into the stack

2. Pop the item from the stack and insert into the ‘visited’ list

3. For node marked as ‘visited’ (or in visited list), add the adjacent nodes of this node that are not yet marked visited, to the stack.

4. Repeat steps 2 and 3 until the stack is empty.

Suppose we have the following graph. For DFS, we will use stack data structure.

We will start with A to begin with, mark it as visited, and add it to the visited list. Then we will consider all the adjacent nodes of A and push these nodes onto the stack as shown below. 

Next, we pop a node from the stack i.e. B and mark it as visited. We then add it to the ‘visited’ list. This is represented below. 

Now we consider the adjacent nodes of B which are A and C. Out of this A is already visited. So we ignore it. Next, we pop C from the stack. Mark C as visited. The adjacent node of C i.e. E is added to the stack. 

Next, we pop the next node E from the stack and mark it as visited. Node E’s adjacent node is C that is already visited. So we ignore it. 

Now only node D remains in the stack. So we mark it as visited. Its adjacent node is A which is already visited. So we do not add it to the stack. 

At this point the stack is empty. This means we have completed the depth-first traversal for the given graph.

The visited list gives the final sequence of traversal using the depth-first technique. The final DFS sequence for the above graph is A->B->C->E->D.

Example-3: DFS

//ExampleDFS.java

import java.util.Iterator;

import java.util.LinkedList;

//DFS Technique for undirected graph

public class ExampleDFS{ 

int vertices;   // No. of vertices 

LinkedList<Integer> adj_list[]; // adjacency list declaration

// Constructor: to initialize adjacency lists as per no of vertices 

ExampleDFS(int v) { 

   vertices = v; 

   adj_list = new LinkedList[v]; 

   for (int i=0; i<v; ++i) 

       adj_list[i] = new LinkedList(); 

} 

//add an edge to the graph 

void addEdge(int v, int w) { 

   adj_list[v].add(w);  // Add w to v's list. 

} 

public void printGraph(){

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

      if(adj_list[i].size()>0) {

         System.out.print("Vertex " + i + " is connected to: ");

         for (int j = 0; j <adj_list[i].size() ; j++) 

            System.out.print(adj_list[i].get(j)+" ");

         System.out.println();

      }

   }

}

// helper function for DFS technique

void DFS_helper(int v,boolean visited[]) { 

      // current node is visited 

      visited[v] = true; 

      System.out.print(v+" "); 

      // process all adjacent vertices 

      Iterator<Integer> i = adj_list[v].listIterator(); 

      while (i.hasNext()) 

      { 

          int n = i.next(); 

          if (!visited[n]) 

              DFS_helper(n, visited); 

      } 

} 

void DFS(int v) { 

      //initially none of the vertices are visited 

      boolean visited[] = new boolean[vertices];   

      // call recursive DFS_helper function for DFS technique 

      DFS_helper(v, visited); 

}

public static void main(String args[]) { 

   //create a graph object and add edges to it

   ExampleDFS g = new ExampleDFS(5); 

   g.addEdge(0, 1); 

   g.addEdge(0, 2); 

   g.addEdge(0, 3); 

   g.addEdge(1, 2);

   g.addEdge(2, 4); 

   //print the DFS Traversal sequence

   System.out.println("Depth First Traversal for given graph"+ 

                           "(with 0 as starting vertex)"); 

   g.DFS(0); 

} 

}

The output will be:

Depth First Traversal for given graph(with 0 as starting vertex)

0 1 2 4 3 

Applications Of DFS

1. Detect a cycle in a graph: DFS facilitates to detect a cycle in a graph when we can backtrack to an edge.

2. Pathfinding: As we have already seen in the DFS illustration, given any two vertices we can find the path between these two vertices.

3. Minimum spanning tree and shortest path: If we run the DFS technique on the non-weighted graph, it gives us the minimum spanning tree and the shorted path.

4. Topological sorting: Topological sorting is used when we have to schedule the jobs. We have dependencies among various jobs. We can also use topological sorting for resolving dependencies among linkers, instruction schedulers, data serialization, etc.

Breadth-first Traversal (BFS)

Breadth-first (BFS) technique uses a queue to store the nodes of the graph. As against the DFS technique, in BFS we traverse the graph breadth-wise. This means we traverse the graph level wise. When we explore all the vertices or nodes at one level we proceed to the next level.

The following is the algorithm for the BFS technique.

Algorithm

• Step 1: Begin with the root node and insert it into the queue.

• Step 2: Repeat steps 3 and 4 for all nodes in the graph.

• Step 3: Remove the root node from the queue, and add it to the Visited list.

• Step 4: Now add all the adjacent nodes of the root node to the queue and repeat steps 2 to 4 for each node.[END OF LOOP]

• Step 6: EXIT

Suppose we have the following graph. For BFS, we will use queue data structure.

First, we start with root i.e. node A and add it to the visited list. All the adjacent nodes of the node A i.e. B, C, and D are added to the queue. 

Next, we remove the node B from the queue. We add it to the Visited list and mark it as visited. Next, we explore the adjacent nodes of B in the queue (C is already in the queue). Another adjacent node A is already visited so we ignore it. 

Next, we remove node C from the queue and mark it as visited. We add C to the visited list and its adjacent node E is added to the queue. 

Next, we delete D from the queue and mark it as visited. Node D’s adjacent node A is already visited, so we ignore it. 

So now only node E is in the queue. We mark it as visited and add it to the visited list. The adjacent node of E is C which is already visited. So ignore it. 

At this point, the queue is empty and the visited list has the sequence we obtained as a result of BFS traversal. The sequence is, A->B->C->D->E. 

Example 4: BFS

// ExampleBFS.java

import java.util.Iterator;

import java.util.LinkedList;

public class ExampleBFS{ 

int vertices;   // No. of vertices 

LinkedList<Integer> adj_list[]; // adjacency list declaration

// Constructor: to initialize adjacency lists as per no of vertices 

ExampleBFS(int v) { 

vertices = v; 

adj_list = new LinkedList[v]; 

for (int i=0; i<v; ++i) 

adj_list[i] = new LinkedList(); 

} 

//add an edge to the graph 

void addEdge(int v, int w) { 

adj_list[v].add(w);  // Add w to v's list. 

} 

public void printGraph(){

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

if(adj_list[i].size()>0) {

System.out.print("Vertex " + i + " is connected to: ");

for (int j = 0; j <adj_list[i].size() ; j++) 

System.out.print(adj_list[i].get(j)+" ");

System.out.println();

      }

   }

}

// BFS traversal from the root_node 

public void BFS(int root_node)   { 

// initially all vertices are not visited 

boolean visited[] = new boolean[vertices]; 

// BFS queue 

LinkedList<Integer> queue = new LinkedList<Integer>(); 

// current node = visited, insert into queue 

visited[root_node]=true; 

queue.add(root_node); 

while (queue.size() != 0)  { 

// deque an entry from queue and process it  

root_node = queue.poll(); 

System.out.print(root_node+" "); 

// get all adjacent nodes of current node and process

Iterator<Integer> i = adj_list[root_node].listIterator(); 

while (i.hasNext()){ 

int n = i.next(); 

if (!visited[n]) { 

visited[n] = true; 

queue.add(n); 

} 

} 

} 

} 

    public static void main(String args[]) 

    { 

        //create a graph with 5 vertices

     ExampleBFS g = new ExampleBFS(5); 

        //add edges to the graph  

        g.addEdge(0, 1); 

        g.addEdge(0, 2); 

        g.addEdge(0, 3); 

        g.addEdge(1, 2); 

        g.addEdge(2, 4);

        //print BFS sequence

        System.out.println("Breadth-first traversal of graph with 0 as starting vertex:"); 

        g.BFS(0); 

    } 

}

The output will be:

Breadth-first traversal of graph with 0 as starting vertex:

0 1 2 3 4 

Applications Of BFS Traversal

1. Garbage collection: One of the algorithms used by the garbage collection technique to copy Garbage collection is “Cheney’s algorithm”. This algorithm uses a breadth-first traversal technique.

2. Broadcasting in networks: Broadcasting of packets from one point to another in a network is done using the BFS technique.

3. GPS navigation: We can use the BFS technique to find adjacent nodes while navigating using GPS.

4. Social networking websites: BFS technique is also used in social networking websites to find the network of people surrounding a particular person.

5. Shortest path and minimum spanning tree in un-weighted graph: In the unweighted graph, the BFS technique can be used to find a minimum spanning tree and the shortest path between the nodes.