GRAPHS:
A graph is a data structure that contains two components :
- 1.
A finite set of vertices called nodes
- 2.
A finite set of ordered pairs called edges.
An ordered pair (u,v) representing an edge between vertex u
and vertex v. Graphs are generally used to represent many real time
applications. Graphs are extremely useful in case of computer networks. A
country connecting various cities can be represented using a graph. Consider an
example of social networking website, facebook where each user is represented
using a node and two users are said to be friends only if there exists an edge
between them. A graph can be a directed or undirected graph. A graph is said to be directed if there
exists a specific direction from one vertex to another vertex. A directed graph is unidirectional. A graph
is said to be undirected graph if there exists a bidirectional path between two
vertices. Example of directed and undirected graph is shown below:
REPRESENTATION OF GRAPHS:
Graphs can be represented using two methods:
- Adjacency matrix
- Adjacency list
Adjacency matrix:
In this method, the entire graph is represented using a
2-Dimensional matrix of size V x V .Here V represents the number of vertices of
the graph G. The matrix entry adj[i][j] is 1 if there is an edge from I to j.
Otherwise the entry adj[i][j] is 0.
Pros:
Representation is easier to implement and follow.
Removing an edge takes O(1)
time.
Queries like whether there
is an edge from vertex ‘u’ to vertex ‘v’ are efficient and can be done O(1).
Cons:
Consumes more space O(V^2).
Even if the graph is
sparse(contains less number of edges), it consumes the same space.
Adding a vertex is O(V^2) time.
Adjacency matrix representation in java :
package
graph;
import java.util.Scanner;
public class Graph {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
System.out.println("enter the number of vertices");
int n=sc.nextInt();
int graph[][]=new int[n][n];
while(true){
System.out.println("enter your choice");
System.out.println("1.create an edge");
System.out.println("2. check if there is an edge");
System.out.println("3. remove an edge");
System.out.println("4.exit");
System.out.println("****************");
int ch=sc.nextInt();
if(ch>4)
System.out.println("wrong choice");
else{
switch(ch){
case 1:
System.out.println("PLEASE NOTE THAT THE VERTEX RANGE IS FROM 0 TO "+ (n-1));
System.out.println("*****************************************************");
System.out.println("enter vertex 1");
int e1=sc.nextInt();
System.out.println("enter vertex 2");
int e2=sc.nextInt();
if(e1<0||e2<0||e1>=n||e2>=n)
System.out.println("WRONG INPUT");
else{
graph[e1][e2]=1;
graph[e2][e1]=1;
}
System.out.println("CREATED EDGE SUCCESFULLY");
System.out.println("*****************************************************");
break;
case 2: System.out.println("PLEASE NOTE THAT THE VERTEX RANGE IS FROM 0 TO "+(n-1));
System.out.println("*****************************************************");
System.out.println("enter vertex 1");
int u=sc.nextInt();
System.out.println("enter vertex 2");
int v=sc.nextInt();
if(u<0||v<0||u>=n||v>=n)
System.out.println("WRONG INPUT");
else{
if(graph[u][v]==1)
System.out.println("EDGE EXISTS");
else
System.out.println("NO EDGE BETWEEN "+u+" and "+v);
}
System.out.println("*****************************************************");
break;
case 3: System.out.println("PLEASE NOTE THAT THE VERTEX RANGE IS FROM 0 TO "+ (n-1));
System.out.println("*****************************************************");
System.out.println("enter vertex 1");
int t1=sc.nextInt();
System.out.println("1.create an edge");
int t2=sc.nextInt();
if(t1<0||t2<0||t1>=n||t2>=n)
System.out.println("WRONG INPUT");
else{
graph[t1][t2]=0;
System.out.println("EDGE REMOVED SUCCESSFULLY");
}
System.out.println("*****************************************************");
break;
case 4: System.exit(1);
}
}
}
}
}
Adjacency List:
Here an array of linked lists is used. Size of
the array is equal to number of vertices. Let the array be a[]. An entry a[i]
represents the linked list of vertices adjacent to the ith
vertex. This representation can also be used to represent a weighted graph. The
weights of edges can be stored in nodes of linked lists.
Following is adjacency
list representation of the above graph in java.
class Graph {
//Map of adjacency lists for each node
Map<Integer, List<Integer>> adj;
public Graph(int[] nodes) {
//your node labels are consecutive integers starting with one.
//to make the indexing easier we will allocate an array of adjacency one element larger than necessary
adj = new HashMap<Integer, LinkedList<Integer>>();
for (int i = 0; i < nodes.length; ++i) {
adj.put(i, new LinkedList<Integer>());
}
}
public addNeighbor(int v1, int v2) {
adj.get(v1).add(v2);
}
public List<Integer> getNeighbors(int v) {
return adj.get(v);
}
public static void main(String[] args) {
try {
BufferedReader br = new BufferedReader(new StreamReader(System.in));
String line = br.readLine();
if (line != null) {
//read nodes
String[] nodeNames = line.split(" ");
int[] nodes = new int[nodeNames.length]
for (int i = 0; i < nodes.length; ++i) {
nodes[i] = Integer.parseInt(nodeNames[i]);
}
//create graph
Graph g = new Graph(nodes);
//read edges
while((line = br.readLine()) != null) {
String[] tokens = line.split(" ");
int v1 = Integer.parseInt(tokens[0]);
int v2 = Integer.parseInt(tokens[1]);
//we add neighbor to each node in both directions.
g.addNeighbor(v1, v2);
g.addNeighbor(v2, v1);
}
}
br.close();
}
catch(IOException e) {
System.out.println(e);
}
}
}
There are other representations also like, Incidence Matrix and Incidence List. The choice of the graph representation is situation specific. It totally depends on the type of operations to be performed and ease of use.
Comments
Post a Comment
Thanks for your comments!