Code Pumpkin

Graph

March 31, 2017
Posted by Pumpkin
Subscribe

Directed Graph

Graph is a non linear data structure, it contains a set of points known as nodes (or vertices) and set of links known as edges which connects the vertices. The pictorial representation is shown in the image in the left pane.

Types of Graph:

  • Undirected Graph is a graph that is a set of vertices connected by edges, where the edges are bidirectional.
  • Directed Graph is a graph that is a set of vertices connected by edges, where the edges have a direction associated with them.
  • Weighted Graph is a graph in which each eadge is given a numerical weight.
  • Complete Graph is a graph in which every vertex directly connected to every other vertex 

Graph Representation:

Adjacency Matrix: Adjacency Matrix is a 2D array of size V x V where V is the number of vertices in a graph. Let the 2D array be adj[][], a slot adj[i][j] = 1 indicates that there is an edge from vertex i to vertex j.

We can also represent weighted graph by putting weight of the edge instead of 1.

In the right pane we have shown the Adjancency Matrix representation of the above graph.

This representation is easy to implement. Removing edges and find checking link between two vertices is done in O(1) time

adjacencyMatrix

This way of representation is not effective as when there is very large number of vertices we are not ustilizing the space effectively(Consumes O(V^2)). Even adding new vertex to the matrix is also costly operation.  So we have one more graph representation Adjacency List.

adjacencyList

Adjacency List: An array of linked lists is used. Size of the array is equal to number of vertices. Let the array be array[]. An entry array[i] represents the linked list of vertices adjacent to the ith vertex.

Image in the left pane is Adjacency List representation of the Directed Graph shown in the first image.

Here we are able to reduce the space complexity to O(|V|+|E|) which is much lower than previous case. Here adding new vertex to the graph is also easy. But this comes one trade off when we want to check  whether there is an edge from vertex u to vertex v, it is not efficient and can be done O(V). Which was O(1) in case of Adjacency Matrix.

Representaion by Adjacency List:


public class Graph{
 
        private int v;
        private LinkedList<integer> adj[];
                /**
          *  We initialize the Graph with number of vertices v in the graph 
          */
        public Graph(int v) {
            this.v = v;
            adj = new LinkedList[v];
            for (int i = 0; i < v; i++) {
				adj[i] = new LinkedList<Integer>();
	        }
        }
 
        /**
          * This method will add an  edge between node u and w.
          */
        void addEdge(int u, int w){
            adj[u].add(w);
        }
}

The above is the simple implementation of the Adjacency List using array of linked list. The same way we can also implement graph representation using Adjacency Matrix.

References: Wiki Pages

Happy Learning 🙂

Tags: , , , , ,


Comments and Queries

If you want someone to read your code, please put the code inside <pre><code> and </code></pre> tags. For example:
<pre><code class="java"> 
String foo = "bar";
</code></pre>
For more information on supported HTML tags in disqus comment, click here.

Total Post : 80
Subscribe
Contribute Your Articles

Interview Experiences

Related Books

Like Us On Facebook

Alexa Page Rank