GRAPH REPRESENTATION

There are 3 ways in which we can represent graphs:

  1. Array of edges
  2. Adjacency Matrix
  3. Adjacency List.

DEPTH FIRST SEARCH

  1. Recursive <
  2. Iterative -> Stack

BREADTH FIRST SEARCH

  1. Recursive is hard.
  2. Iterative

CODE

public class GraphRep {

class Node{
private int data;
private boolean visited;

Node(int data){
this.data = data;
}

}

class Graph{
private int nE;
private int nV;
private Map<Node, List<Node>> edges;


}

public void insertEdge(){}
public void removeEdge(){}
public void isAdjacent(Node node1, Node node2){}


public List<Node> getEdgeList(Node vertex1, Node vertex2){
List<Node> edge = new ArrayList<Node>();

edge.add(vertex1);
edge.add(vertex2);

return edge;
}
public Graph getDummyGraph(){
Graph graph = new Graph();

graph.nE = 10;
graph.nV = 3;

Node vertex1 = new Node(1);
Node vertex2 = new Node(2);
Node vertex3 = new Node(3);

Map<Node,List<Node>> edges = new HashMap<Node,List<Node>>();
edges.put(vertex1, getEdgeList(vertex2,vertex3));
edges.put(vertex2, getEdgeList(vertex1,vertex3));
edges.put(vertex3, getEdgeList(vertex1,vertex2));

graph.edges = edges;

return graph;

}

public boolean DfsRecursive(Graph g, Node src, Node dest){
src.visited = true;

if(src.equals(dest)){
return true;
}
else{
for(Node edge:g.edges.get(src)){
if(!edge.visited){
return DfsRecursive(g,edge,dest);
}
}
}

return false;
}

public boolean DfsIterative(Graph g, Node src, Node dest){
src.visited = true;

if(src.equals(dest)){
return true;
}

Stack<Node> stack = new Stack<Node>();

stack.push(src);

while(!stack.empty()){
Node node = stack.pop();
node.visited = true;
if(node.equals(dest)){
return true;
}
for(Node edge:g.edges.get(node)){
if(!edge.visited){
stack.push(edge);
}
}
}

return false;
}


public boolean BfsIterative(Graph g, Node src, Node dest){
src.visited = true;

if(src.equals(dest)){
return true;
}
Queue<Node> queue = new LinkedList<Node>();

queue.add(src);

while(!queue.isEmpty()){
Node node = queue.remove();
node.visited = true;

if(node.equals(dest)){
return true;
}

for(Node edge:g.edges.get(node)){
queue.add(edge);
}
}

return false;

}
}

Exploring and discovering. Learning everyday.