Graph(Data Structures)
Graph(DS):
It is not a easy one but you can understand it by correlating with your day to day life. It is used everywhere beyond your imagination. It took me 1 week and more than 10 articles to understand Graph but i cannot still say that i have mastered Graph.
Definition: It is a network representation of set of objects where some pairs of objects are connected by links(edges)
e.g. the easiest one which we use in our daily life our facebook friends
where Sanyo is friends with Rahul and Malay but Rahul and Malay can also be friends with Abhimanyu and Aishwarya.
In this case Sanyo, Rahul, Malay, Chaitra, Abhimanyu and Aishwarya are nodes and the link connecting them will be called as edges.
Adjacent: If two nodes are connected to each other they will be called adjacent. Sanyo & Rahul are said to be adjacent but Rahul and Malay are not said to be adjacent
Adjacency can be represented in two forms:
1. Adjacency List: Vertices are stored as records or objects, and every vertex stores a list of adjacent vertices. This data structure allows the storage of additional data on the vertices. Additional data can be stored if edges are also stored as objects, in which case each vertex stores its incident edges and each edge stores its incident vertices.
2. Adjacency Matrix: A two-dimensional matrix, in which the rows represent source vertices and columns represent destination vertices. Data on edges and vertices must be stored externally. Only the cost for one edge can be stored between each pair of vertices.
Basic Operations:
1. Addition & Deletion of node.
2. Addition & Deletion of edge.
3. Find the adjacent node
Types Of Graph:
1. Undirected Graph:
A Graph in which there is no direction associated with edges. All the edges are considered as bidirectional
2. Directed Graph:
A Graph in which there is direction associated with edges. All the edges are uni-directional because they will be pointing in one direction.
There are other types of Graphs also:
1. Cyclic Graph: A cycle is said to be cycle when its last node and first node are same while traversing. A is connected to B, B is connected to C and C is connected to A. {A, B, C} forms one cycle
2. Acyclic Graph: In this graph node will be connected but they wont be forming a cycle structure. A is connected to B, B is connected to C, but C is not connected to A
3. Directed Acylic Graph: While traversing the graph according to directions associated with edges and it does not form a cycle. It is called directed acylic graph(combination of Directed Graph + Acyclic Graph)
4. Directed Cyclic Graph: It forms a cyclic graph while traversing from one node to another by following the directions associated with them(combination of Directed Graph + Cyclic Graph)
Graph Traversal: It means visiting every vertex and edge exactly once in a well defined order.
There are two traversal techniques for Graph:
1. Breadth first Traversal: It traverses from a selected node and traverse the graph layerwise thus exploring the neighbor nodes. After completing one level move towards next level neighbor nodes. It uses a queue to traverse
2. Depth first Traversal: It traverses a graph in a depth ward motion. From a selected node it traverses through it child after it returns to its neighbor nodes. It uses a stack to traverse
Dijkstra's Algorithm: (Shortest Path Algorithm)
As the name says shortest path algorithm. It is used for finding the shortest path between node in graph.
It can be used for road networking.
Algorithm for Dijkstra:
1. Select the source node first and destination code
Source Node: A
Destination Node: C
2. Assign all the nodes values as 0 or infinity.
3. Find the neighbors associated with that node.
A is connected to B and D
{A, B} has weight as 6
{A, D} has weight as 1
4. Update the associated edge weight to node.
Node D: it has weight 1
Node B: it has weight 6
5. Find the neighbors node of node B and D.
Since node B and D are also connected
{D, B} has weight as 2
{D, E} has weight as 1
{B, C} has weight as 5
6. Node C will have weight as 11(6 + 5) value of A + value of B
If we traverse from {A, D, B} the weight for Node B will be 2 + 1 = 3.
Node B has associated weight as 6
It will check with weight already associated with it. If it is less than associated value it will update else it will ignore the path.
For reaching node B {A, D, B} has less weight so it will be preferred and {A, B} path will be ignored.
Now update the Node B with value as 3.
update the node E with value as 2. {A, D, E}
After this Node C value is also getting affected. Node C will have value as 1 + 2 + 5 = 8.
Path: {A, D, B, C}
7. We have found the path for node C but one edges is still remaining. So, it will repeat it again.
8. Edge {E, C} has weight as 5.
Edge {E, B} has weight as 2. The path {A, D, E, B} has weight as 4. So it will not effect the node B and node C weight remains same.
If we traverse from A-> C by this path {A, D, E} the weight associated will be 7
Node C has weight as 8 and with this path it is 7 so it will update the node C value as 7 and ignore the previous path. New path will be followed.
So finally we found shortest path {A, D, E, C} as 7
// Code for Adjacency Matrix, BFT and DFT in java
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Stack;
public class AdjacencyList
{
private Map<Integer, List<Integer>> Adjacency_List;
private LinkedList<Integer> bftList = new LinkedList<Integer>();
// Adjacency List
public AdjacencyList(int vertices) {
Adjacency_List = new HashMap<Integer, List<Integer>>();
for(int x =1; x<=vertices; x++){
Adjacency_List.put(x, new LinkedList<Integer>());
}
}
// Set Edge
public void setEdge(int src, int dest){
if (src > Adjacency_List.size() || dest > Adjacency_List.size()){
System.out.println("Entered node is not present");
return;
}
List<Integer> slist = Adjacency_List.get(src);
slist.add(dest);
}
// Get Edge
public List<Integer> getEdge(int src){
if (src > Adjacency_List.size()){
System.out.println("Entered node is not present");
return null;
}
return Adjacency_List.get(src);
}
// Depth first Traversal
public void dft(int adjacency_matrix[][], int srcNode){
// int no_of_nodes
Stack<Integer> stack = new Stack<Integer>();
if(srcNode > Adjacency_List.size()){
return;
}
stack.push(srcNode);
System.out.println("Depth first Traversal is");
int[] visited = new int[Adjacency_List.size() + 1];
int i, element;
System.out.print(srcNode + "\t");
while(!stack.isEmpty()){
element = stack.peek();
i = element;
while(i<= Adjacency_List.size()){
if (adjacency_matrix[element][i] == 1 && visited[i] == 0){
stack.push(i);
visited[i] = 1;
element = i;
i = 1;
System.out.print(element + "\t");
continue;
}
i++;
}
stack.pop();
}
}
// Breadth first traversal
public void bft(int adjacency_matrix[][], int source)
{
if(source > Adjacency_List.size()){
return;
}
int number_of_nodes = adjacency_matrix[source].length - 1;
int[] visited = new int[number_of_nodes + 1];
int i, element;
visited[source] = 1;
bftList.add(source);
while (!bftList.isEmpty())
{
element = bftList.remove();
i = element;
System.out.print(i + "\t");
while (i <= number_of_nodes)
{
if (adjacency_matrix[element][i] == 1 && visited[i] == 0)
{
bftList.add(i);
visited[i] = 1;
}
i++;
}
}
}
public static void main(String...arg)
{
int number_of_vertices, number_of_edges, source, destination;
int source_node;
int count = 0;
Scanner sc = new Scanner(System.in);
System.out.println("Enter the number of nodes and edges");
number_of_vertices = sc.nextInt();
number_of_edges = sc.nextInt();
AdjacencyList adjacencyList = new AdjacencyList(number_of_vertices);
int adjacency_matrix[][] = new int[number_of_vertices + 1][number_of_vertices + 1];
System.out.println("Enter the source and destination of edges");
while (count < number_of_edges){
source = sc.nextInt();
destination = sc.nextInt();
adjacencyList.setEdge(source, destination);
count++;
}
// Given Adjacency Matrix for graph
System.out.println("Adjacency Matrix for Graph is");
System.out.print(" ");
for(int k =1; k<=number_of_vertices; k++){
System.out.print(k + " ");
}
for(int j =1; j<=number_of_vertices; j++){
List<Integer> source_list = adjacencyList.getEdge(j);
System.out.print("\n" + j + " ");
for(int x =1; x <= number_of_vertices; x++){
if (source_list.contains(x)){
System.out.print("1 ");
adjacency_matrix[j][x] = 1;
}else{
System.out.print("0 ");
adjacency_matrix[j][x] = 0;
}
}
}
// Breadth First Traversal
System.out.println("\n\n");
System.out.println("Enter the source node for Breadth First Traversal");
source_node = sc.nextInt();
adjacencyList.bft(adjacency_matrix, source_node);
// Depth First Traversal
System.out.println("\n\n");
System.out.println("Enter the source node for Depth First Traversal");
source_node = sc.nextInt();
adjacencyList.dft(adjacency_matrix, source_node);
sc.close();
}
}
It is not a easy one but you can understand it by correlating with your day to day life. It is used everywhere beyond your imagination. It took me 1 week and more than 10 articles to understand Graph but i cannot still say that i have mastered Graph.
Definition: It is a network representation of set of objects where some pairs of objects are connected by links(edges)
e.g. the easiest one which we use in our daily life our facebook friends
In this case Sanyo, Rahul, Malay, Chaitra, Abhimanyu and Aishwarya are nodes and the link connecting them will be called as edges.
Adjacent: If two nodes are connected to each other they will be called adjacent. Sanyo & Rahul are said to be adjacent but Rahul and Malay are not said to be adjacent
Adjacency can be represented in two forms:
1. Adjacency List: Vertices are stored as records or objects, and every vertex stores a list of adjacent vertices. This data structure allows the storage of additional data on the vertices. Additional data can be stored if edges are also stored as objects, in which case each vertex stores its incident edges and each edge stores its incident vertices.
2. Adjacency Matrix: A two-dimensional matrix, in which the rows represent source vertices and columns represent destination vertices. Data on edges and vertices must be stored externally. Only the cost for one edge can be stored between each pair of vertices.
Basic Operations:
1. Addition & Deletion of node.
2. Addition & Deletion of edge.
3. Find the adjacent node
Types Of Graph:
1. Undirected Graph:
A Graph in which there is no direction associated with edges. All the edges are considered as bidirectional
2. Directed Graph:
A Graph in which there is direction associated with edges. All the edges are uni-directional because they will be pointing in one direction.
There are other types of Graphs also:
1. Cyclic Graph: A cycle is said to be cycle when its last node and first node are same while traversing. A is connected to B, B is connected to C and C is connected to A. {A, B, C} forms one cycle
2. Acyclic Graph: In this graph node will be connected but they wont be forming a cycle structure. A is connected to B, B is connected to C, but C is not connected to A
3. Directed Acylic Graph: While traversing the graph according to directions associated with edges and it does not form a cycle. It is called directed acylic graph(combination of Directed Graph + Acyclic Graph)
4. Directed Cyclic Graph: It forms a cyclic graph while traversing from one node to another by following the directions associated with them(combination of Directed Graph + Cyclic Graph)
Graph Traversal: It means visiting every vertex and edge exactly once in a well defined order.
There are two traversal techniques for Graph:
1. Breadth first Traversal: It traverses from a selected node and traverse the graph layerwise thus exploring the neighbor nodes. After completing one level move towards next level neighbor nodes. It uses a queue to traverse
2. Depth first Traversal: It traverses a graph in a depth ward motion. From a selected node it traverses through it child after it returns to its neighbor nodes. It uses a stack to traverse
Dijkstra's Algorithm: (Shortest Path Algorithm)
As the name says shortest path algorithm. It is used for finding the shortest path between node in graph.
It can be used for road networking.
Algorithm for Dijkstra:
1. Select the source node first and destination code
Source Node: A
Destination Node: C
2. Assign all the nodes values as 0 or infinity.
3. Find the neighbors associated with that node.
A is connected to B and D
{A, B} has weight as 6
{A, D} has weight as 1
4. Update the associated edge weight to node.
Node D: it has weight 1
Node B: it has weight 6
5. Find the neighbors node of node B and D.
Since node B and D are also connected
{D, B} has weight as 2
{D, E} has weight as 1
{B, C} has weight as 5
6. Node C will have weight as 11(6 + 5) value of A + value of B
If we traverse from {A, D, B} the weight for Node B will be 2 + 1 = 3.
Node B has associated weight as 6
It will check with weight already associated with it. If it is less than associated value it will update else it will ignore the path.
For reaching node B {A, D, B} has less weight so it will be preferred and {A, B} path will be ignored.
Now update the Node B with value as 3.
update the node E with value as 2. {A, D, E}
After this Node C value is also getting affected. Node C will have value as 1 + 2 + 5 = 8.
Path: {A, D, B, C}
7. We have found the path for node C but one edges is still remaining. So, it will repeat it again.
8. Edge {E, C} has weight as 5.
Edge {E, B} has weight as 2. The path {A, D, E, B} has weight as 4. So it will not effect the node B and node C weight remains same.
If we traverse from A-> C by this path {A, D, E} the weight associated will be 7
Node C has weight as 8 and with this path it is 7 so it will update the node C value as 7 and ignore the previous path. New path will be followed.
So finally we found shortest path {A, D, E, C} as 7
// Code for Adjacency Matrix, BFT and DFT in java
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Stack;
public class AdjacencyList
{
private Map<Integer, List<Integer>> Adjacency_List;
private LinkedList<Integer> bftList = new LinkedList<Integer>();
// Adjacency List
public AdjacencyList(int vertices) {
Adjacency_List = new HashMap<Integer, List<Integer>>();
for(int x =1; x<=vertices; x++){
Adjacency_List.put(x, new LinkedList<Integer>());
}
}
// Set Edge
public void setEdge(int src, int dest){
if (src > Adjacency_List.size() || dest > Adjacency_List.size()){
System.out.println("Entered node is not present");
return;
}
List<Integer> slist = Adjacency_List.get(src);
slist.add(dest);
}
// Get Edge
public List<Integer> getEdge(int src){
if (src > Adjacency_List.size()){
System.out.println("Entered node is not present");
return null;
}
return Adjacency_List.get(src);
}
// Depth first Traversal
public void dft(int adjacency_matrix[][], int srcNode){
// int no_of_nodes
Stack<Integer> stack = new Stack<Integer>();
if(srcNode > Adjacency_List.size()){
return;
}
stack.push(srcNode);
System.out.println("Depth first Traversal is");
int[] visited = new int[Adjacency_List.size() + 1];
int i, element;
System.out.print(srcNode + "\t");
while(!stack.isEmpty()){
element = stack.peek();
i = element;
while(i<= Adjacency_List.size()){
if (adjacency_matrix[element][i] == 1 && visited[i] == 0){
stack.push(i);
visited[i] = 1;
element = i;
i = 1;
System.out.print(element + "\t");
continue;
}
i++;
}
stack.pop();
}
}
// Breadth first traversal
public void bft(int adjacency_matrix[][], int source)
{
if(source > Adjacency_List.size()){
return;
}
int number_of_nodes = adjacency_matrix[source].length - 1;
int[] visited = new int[number_of_nodes + 1];
int i, element;
visited[source] = 1;
bftList.add(source);
while (!bftList.isEmpty())
{
element = bftList.remove();
i = element;
System.out.print(i + "\t");
while (i <= number_of_nodes)
{
if (adjacency_matrix[element][i] == 1 && visited[i] == 0)
{
bftList.add(i);
visited[i] = 1;
}
i++;
}
}
}
public static void main(String...arg)
{
int number_of_vertices, number_of_edges, source, destination;
int source_node;
int count = 0;
Scanner sc = new Scanner(System.in);
System.out.println("Enter the number of nodes and edges");
number_of_vertices = sc.nextInt();
number_of_edges = sc.nextInt();
AdjacencyList adjacencyList = new AdjacencyList(number_of_vertices);
int adjacency_matrix[][] = new int[number_of_vertices + 1][number_of_vertices + 1];
System.out.println("Enter the source and destination of edges");
while (count < number_of_edges){
source = sc.nextInt();
destination = sc.nextInt();
adjacencyList.setEdge(source, destination);
count++;
}
// Given Adjacency Matrix for graph
System.out.println("Adjacency Matrix for Graph is");
System.out.print(" ");
for(int k =1; k<=number_of_vertices; k++){
System.out.print(k + " ");
}
for(int j =1; j<=number_of_vertices; j++){
List<Integer> source_list = adjacencyList.getEdge(j);
System.out.print("\n" + j + " ");
for(int x =1; x <= number_of_vertices; x++){
if (source_list.contains(x)){
System.out.print("1 ");
adjacency_matrix[j][x] = 1;
}else{
System.out.print("0 ");
adjacency_matrix[j][x] = 0;
}
}
}
// Breadth First Traversal
System.out.println("\n\n");
System.out.println("Enter the source node for Breadth First Traversal");
source_node = sc.nextInt();
adjacencyList.bft(adjacency_matrix, source_node);
// Depth First Traversal
System.out.println("\n\n");
System.out.println("Enter the source node for Depth First Traversal");
source_node = sc.nextInt();
adjacencyList.dft(adjacency_matrix, source_node);
sc.close();
}
}
Comments
Post a Comment