CC-2 : Implement Bi-Directional/Undirectional graph using Adjacency List.

Description:

Create and test a custom unidirectional Graph implementation using Adjacency List.

Test cases and expected outputs:

Input Parameters	Expected outputs
GraphAdjacencyMatrix GraphAdjacencyList gph=new GraphAdjacencyList(5); gph.addEdge(0, 1); gph.addEdge(0, 2); gph.addEdge(0, 3); gph.addEdge(0, 4); gph.addEdge(1, 2); gph.addEdge(2, 3); gph.addEdge(3, 4); gph.displayGraph();	vertex 0->1->2->3->4 vertex 1->0->2 vertex 2->0->1->3 vertex 3->0->2->4 vertex 4->0->3

Pseudocode:

Initialize an int variable named vertices to hold the number of vertices in the graph.

Initialize a ArrayList of ArrayLists names adjacencyList to hold the information of edge connections between vertices of the graph.

Each ArrayList index represents a vertex of the graph.

Each ArrayList index points to a second level ArrayList, which has list of all nodes connected to the current vertex.

To add edge between vertice n1 and vertice n2, add following mapping to adjacencyList, indicating a bi-directional/ Undirectional edge :

adjacencyLists.get(n1).add(n2).

adjacencyLists.get(n2).add(n1).

To remove edge between vertice n1 and vertice n2, remove following mapping from adjacencyList:

adjacencyLists.get(n1).remove(n2).

adjacencyLists.get(n2).remove(n1).

Code:

public class GraphAdjacencyList {

 private int vertices;
 private ArrayList<ArrayList<Integer>> adjacencyLists=new ArrayList<ArrayList<Integer>>();
 private int[] visited;
 String dfsTraversal=new String();
 
 public GraphAdjacencyList(int vertices) {
	 this.vertices=vertices;
	 visited=new int[vertices];
	 for (int iIdx=0; iIdx < vertices; iIdx++) {
		 adjacencyLists.add(new ArrayList<Integer>());
		 visited[iIdx]=0;
	 }
 }
 
 public void addEdge(int source, int dest) {
	 adjacencyLists.get(source).add(dest);
	 adjacencyLists.get(dest).add(source);
 }
 
 public void removeEdge(int source, int dest) {
	 adjacencyLists.get(source).remove(dest);
	 adjacencyLists.get(dest).remove(source);
 }
 }

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

import java.util.ArrayList;
import java.util.Iterator;

public class GraphAdjacencyList {

 private int vertices;
 private ArrayList<ArrayList<Integer>> adjacencyLists=new ArrayList<ArrayList<Integer>>();
 private int[] visited;
 String dfsTraversal=new String();
 
 public GraphAdjacencyList(int vertices) {
	 this.vertices=vertices;
	 visited=new int[vertices];
	 for (int iIdx=0; iIdx < vertices; iIdx++) {
		 adjacencyLists.add(new ArrayList<Integer>());
		 visited[iIdx]=0;
	 }
 }
 
 public void addEdge(int source, int dest) {
	 adjacencyLists.get(source).add(dest);
	 adjacencyLists.get(dest).add(source);
 }
 
 public void removeEdge(int source, int dest) {
	 adjacencyLists.get(source).remove(dest);
	 adjacencyLists.get(dest).remove(source);
 }
 
 public void dfsTraversal(int vertex) {
	  visited[vertex]=1;
	 dfsTraversal+= vertex + " ";
	 Iterator<Integer> itr=adjacencyLists.get(vertex).iterator();
	 while (itr.hasNext()) {
		 int adjacentNode=itr.next();
		 if (visited[adjacentNode]==0) {
			 dfsTraversal(adjacentNode);
		 }
	 }
	
 }
  
 public void displayGraph() {
	 for (int iIdx=0;iIdx< adjacencyLists.size();iIdx++) {
		 System.out.println();
		 System.out.print("vertex "+iIdx);
		 for (int jIdx=0;jIdx< adjacencyLists.get(iIdx).size();jIdx++) {
			 System.out.print("->"+adjacencyLists.get(iIdx).get(jIdx));
		 }
	 }
 }

public static void main(String[] args) {
	/***********************
	 Test cases given below:
	 **********************/
	String retVal;
	try {
	GraphAdjacencyList gph=new GraphAdjacencyList(5);
	gph.addEdge(0, 1);
	gph.addEdge(0, 2);
	gph.addEdge(0, 3);
	gph.addEdge(0, 4);
	gph.addEdge(1, 2);
	gph.addEdge(2, 3);
	gph.addEdge(3, 4);
	gph.displayGraph();
	gph.dfsTraversal(0);
	System.out.println();
	System.out.println("Dfs Traversal: "+ gph.dfsTraversal);
	
	
	gph=new GraphAdjacencyList(5);
	gph.addEdge(0, 1);
	gph.addEdge(0, 2);
	gph.addEdge(1, 2);
	gph.addEdge(2, 3);
	gph.addEdge(2, 4);
	gph.displayGraph();
	gph.dfsTraversal(0);
	System.out.println();
	System.out.println("Dfs Traversal: "+ gph.dfsTraversal);
	
	
	gph=new GraphAdjacencyList(5);
	gph.addEdge(0, 2);
	gph.addEdge(0, 3);
	gph.addEdge(0, 1);
	gph.addEdge(2, 4);
	gph.displayGraph();
	gph.dfsTraversal(0);
	System.out.println();
	System.out.println("Dfs Traversal: "+ gph.dfsTraversal);
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}
}