Graph Theory Part-2
Hello to all know let's come to Second Interesting Part Of making Graph using Adjaceny List(LINKED LIST REPRESENTATION)........
LINKED LIST REPRESENTATION In this representation (also called adjacency list representation), we store a graph as a linked structure. First we store all the vertices of the graph in a list and then each adjacent vertices will be represented using linked list node. Here terminal vertex of an edge is stored in a structure node and linked to a corresponding initial vertex in the list. Consider a directed graph in Fig. above, it can be represented using linked list as Fig.2
Weighted graph can be represented using linked list by storing the corresponding weight along with the terminal vertex of the edge.Consider a weighted graph in Fig. above it can be represented using linked list as in Fig. below
Although the linked list representation requires very less memory as compared to the adjacency matrix, the simplicity of adjacency matrix makes it preferable when graph are reasonably small.
import java.util.Arrays; import java.util.LinkedList; import java.util.List; class Graph { //Create a class of Edges (we are using concept of Inner class...) class Edges { int v;int w; //no vertices and their weight public Edges(int v, int w) { this.v=v; this.w=w; } @Override public String toString() { return " [" + v + "," + w + "]"; } } List<Edges>G[]; //make a List of type Edges(it will store two values vertices and weight)
public Graph(int n) {
// Intialize variables of class G=new LinkedList[n]; for (int i = 0; i < G.length; i++) { G[i]=new LinkedList<>(); } } public void addEdges(int u,int v,int w) { G[u].add(new Edges(v, w)); } public boolean isConnected(int u, int v) { for (Edges i : G[u]) { if(i.v==v) return true; } return false; } @Override public String toString() {
//Print Graph String res=""; for (int i = 0; i < G.length; i++) { res=res+i+" ->"+G[i]+"\n"; } return res; } } public class GraphEample { public static void main(String[] args) { Graph g=new Graph(5); System.out.println("Graph Representtion"); g.addEdges(0, 1, 1); g.addEdges(0, 2, 1); g.addEdges(0, 3, 1); g.addEdges(0, 4, 1); g.addEdges(1, 0, 1); g.addEdges(1, 2, 1); g.addEdges(1, 3, 1); g.addEdges(1, 4, 1); g.addEdges(2, 0, 1); g.addEdges(2,4,1); g.addEdges(3,0,1); g.addEdges(3,3,1); g.addEdges(4,1,1); g.addEdges(4,2,1); System.out.println(g); } }
Output->
