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
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.
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
That's all for this topic. If you guys have any suggestions or queries, feel free to drop a comment. We would be happy to add that in our post. You can also contribute your articles by creating contributor account here.
Happy Learning 🙂
If you like the content on CodePumpkin and if you wish to do something for the community and the planet Earth, you can donate to our campaign for planting more trees at CodePumpkin Cauvery Calling Campaign.
We may not get time to plant a tree, but we can definitely donate ₹42 per Tree.
About the Author
Tags: AdjacencyList, AjacencyMatrix, DataStructure, Directed Graph, Graph, Java
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.
