📚 Plan for Learning Graph Algorithms

Core Concepts of Graphs
Basic Traversals
Shortest Path Algorithms
MST (Minimum Spanning Tree) Algorithms
Advanced Concepts (Cycles, Components, Topological Sort)
Very Advanced (Max Flow, Bridges, Articulation Points)

1. Core Concepts of Graphs

Before algorithms, understand these terms:

Term	Meaning
Vertex (Node)	A point in a graph
Edge	A connection between two nodes
Directed Graph	Edge has a direction (A ➔ B)
Undirected Graph	Edge has no direction (A — B)
Weighted Graph	Each edge has a weight (cost)
Adjacency List	Store neighbors for each node
Adjacency Matrix	2D array where `matrix[i][j] = 1` if edge exists

2. Traversals (Basic Foundation)

2.1 Breadth-First Search (BFS)

Goal: Visit all nodes level-by-level.
Technique: Queue (FIFO)

1. Push starting node into queue.
2. While queue is not empty:
    - extract
    - proceess node
    - Push neighbours into the queue
3. manage visited nodes

➡ Use cases: Shortest path in unweighted graphs, Level Order Traversal

Template

function bfs(graph, src) {
	let q =[src]
	let visited = new Set()
	
	while(q.length) {
		// extract
		let currentNode = q.shift()
		if(visited.has(currentNode)) continue
		
		//process
		console.log(currentNode)
		
		//visit neighbours
		for(let neighbour of graph[currentNode]){
				q.push(neighbour)
		}
	}
}

// Driver code ------
let inputGraph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D", "E"],
    "D": ["B", "C"],
    "E": ["C"]
}
dfs(inputGraph, "A")

2.2 Depth-First Search (DFS)

Goal: Visit all nodes deep first before backtracking.
Technique: Stack (explicit or via recursion)

1. Start from a node.
2. Visit it and mark visited.
3. For each unvisited neighbor:
    - Recurse/Push into stack

➡ Use cases: Cycle Detection, Connected Components

Template

function dfs(graph, node, visited = new Set()) {
	if(!node) return 
	
	//process node
	console.log(node)
	visited.add(node)
	
	for(let neighbour of graph[node]) {
		dfs(graph, neighbour, visited)
	}
}

// Driver code ------
let inputGraph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D", "E"],
    "D": ["B", "C"],
    "E": ["C"]
}
dfs(inputGraph, "A")