What is a Graph?

A collection of Nodes and Edges

A graph is great establishing relationships between Nodes

Directed Graphs

• Graphs that has a specific direction to traverse
• Easier to maintain as you do not have to maintain visited nodes. There is no chance of going into ifinite loop

graph LR
  a --> b
	b --> c
	a --> c
	c --> d

Undirected Graphs

• Graphs that does not have specific direction to traverse
• Tougher as you do have to maintain visited nodes to avoid infinite cycles during traversal.

graph LR
  a --- b
	b --- c
	a --- c
	c --- d

Representation of Graphs

Adjacency Matrix / Sparse Matrix

• An adjacency matrix is a popular and simple way to represent a graph with time compllexity of traversal as $O(ne)$ and space complexity $O( ne)$
• However, it is most suitable when your model does not frequently manipulate vertices.
• Adjacency matrices are good for storing dense graphs, but in most of the other cases, an adjacency list is better than an adjacency matrix.

Adjacency List

• The adjacency matrix and adjacency list have the same time and space complexity as eventually in worst case, you will have to visite all nodes.
• Most suitable when when your model frequently manipulate vertices.
• If the graph is sparse, we need less space to represent the graph. Therefore, an adjacency list is more space-efficient than an adjacency matrix when we work on sparse graphs

Let Following be a Graph

graph LR
	a --> b  
	a --> c
	b --> d
	c --> e
	d --> f
	

Adjacency Matrix

Adjacency List

let gr = [
  [0, 1, 1, 0, 0, 0],
  [0, 0, 0, 1, 0, 0],
  [0, 0, 0, 0, 1, 0],
  [0, 0, 0, 0, 0, 1],
  [0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0]
];

let gr = [
	a: [c, b],
	b: [d],
	c: [e],
	d: [f]
	e: []
	f: []
}

<aside> 💡 Can you see the amount of space being wasted to store this simple graph in a adjacency matrix? For storing 5 relationships I have to always use $O(n*e)$ space. What if we could only save the Relationships instead of Non-Relationships? Therefore for sparse graphs like this, adhacency lists are optimal

</aside>

Traversals

DFS

DFS Traversal goes deep in a directon untill it can go no more.

DFS uses stack Data Structure

DFS visits nodes linearly

BFS

BFS is traversal that traverses “Nearest Neighbour First”.

BFS Queue Data structure.

BFS visits nodes radially

Iterative Approach - DFS

Iterative Approach - BFS

function dfs(graph, source='a') {
	let stack = [source];
	
	while(stack.length > 0) {
		let current = stack.pop();
		console.log(current)

		for(let neighbour of gr[current]) {
			stack.push(neighbour)
		}
	}	
}

function bfs(gr, source) {
	let queue = [source];
	
	//repeat till queue has elements
	while(queue.length > 0) { 
		
		// pop and print current element
		let current = queue.pop(); 
		console.log(current);
		
		//Add all neighbouring elements in queue
		for(let neighbour of gr[current]) {
			queue.unshift(neighbour)
		}
	}
}