Graph traversal

  1. Array of edges
  2. Adjacency Matrix
  3. Adjacency List.
  1. Recursive <
  2. Iterative -> Stack
  1. Recursive is hard.
  2. Iterative
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.

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Performance optimization in React | useCallback & useMemo hooks

GSoC 2020 — Rocket.Chat.ReactNative Full-Screen Composer

filter() vs find(): JavaScript Array methods

JavaScript Interview Questions and Answers for 2021

Using redux-loop to make tacos at Grubhub

Solving Natas 11

What's different in React Router v5 and v6

Promisify Modals with React&Redux

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Smrita Pokharel

Smrita Pokharel

Exploring and discovering. Learning everyday.

More from Medium

Convert MLMultiArray to Image for PyTorch models without performance lags

Generating and Solving Mazes using Graph Algorithms

LE Analysis timeout on Production — 12/14/2021

Expo Part 2: History