Day 9: Graphs

What You'll Learn Today

• Fundamental graph concepts and terminology
• Graph representations (adjacency list & matrix)
• BFS (Breadth-First Search) and DFS (Depth-First Search)
• Dijkstra's shortest path algorithm

---

What Is a Graph?

A graph consists of nodes (vertices) connected by edges. Trees are a special case of graphs.

flowchart LR
    A["A"] --- B["B"]
    A --- C["C"]
    B --- D["D"]
    C --- D
    B --- E["E"]
    D --- E
    style A fill:#3b82f6,color:#fff
    style B fill:#8b5cf6,color:#fff
    style C fill:#22c55e,color:#fff
    style D fill:#f59e0b,color:#fff
    style E fill:#ef4444,color:#fff

Terminology

Term	Description
Vertex	A node in the graph
Edge	A connection between vertices
Directed graph	Edges have direction
Undirected graph	Edges have no direction
Weighted graph	Edges have costs (weights)
Adjacent	Directly connected by an edge
Degree	Number of edges connected to a vertex
Path	A sequence of connected vertices
Cycle	A path where start equals end

---

Types of Graphs

flowchart TB
    subgraph Undirected["Undirected"]
        U1["A"] --- U2["B"]
        U2 --- U3["C"]
        U1 --- U3
    end
    subgraph Directed["Directed"]
        D1["A"] --> D2["B"]
        D2 --> D3["C"]
        D3 --> D1
    end
    subgraph Weighted["Weighted"]
        W1["A"] -->|"5"| W2["B"]
        W2 -->|"3"| W3["C"]
        W1 -->|"10"| W3
    end
    style Undirected fill:#3b82f6,color:#fff
    style Directed fill:#8b5cf6,color:#fff
    style Weighted fill:#22c55e,color:#fff

---

Graph Representations

Adjacency List

Stores each vertex's neighbors in a list. Best for sparse graphs.

class Graph {
  constructor() {
    this.adjacencyList = new Map();
  }

  addVertex(vertex) {
    if (!this.adjacencyList.has(vertex)) {
      this.adjacencyList.set(vertex, []);
    }
  }

  addEdge(v1, v2) {
    this.adjacencyList.get(v1).push(v2);
    this.adjacencyList.get(v2).push(v1);
  }

  removeEdge(v1, v2) {
    this.adjacencyList.set(v1, this.adjacencyList.get(v1).filter(v => v !== v2));
    this.adjacencyList.set(v2, this.adjacencyList.get(v2).filter(v => v !== v1));
  }

  getNeighbors(vertex) {
    return this.adjacencyList.get(vertex) || [];
  }
}

const graph = new Graph();
["A", "B", "C", "D", "E"].forEach(v => graph.addVertex(v));
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "D");
graph.addEdge("C", "D");
graph.addEdge("D", "E");

Adjacency Matrix

Uses a 2D array to represent edges. Best for dense graphs.

class GraphMatrix {
  constructor(size) {
    this.size = size;
    this.matrix = Array.from({ length: size }, () =>
      new Array(size).fill(0)
    );
    this.vertices = new Map();
  }

  addVertex(name) {
    const index = this.vertices.size;
    this.vertices.set(name, index);
  }

  addEdge(v1, v2, weight = 1) {
    const i = this.vertices.get(v1);
    const j = this.vertices.get(v2);
    this.matrix[i][j] = weight;
    this.matrix[j][i] = weight;
  }

  hasEdge(v1, v2) {
    const i = this.vertices.get(v1);
    const j = this.vertices.get(v2);
    return this.matrix[i][j] !== 0;
  }
}

Adjacency List vs. Matrix

Feature	Adjacency List	Adjacency Matrix
Space	O(V + E)	O(V²)
Edge lookup	O(degree)	O(1)
All edges	O(V + E)	O(V²)
Add edge	O(1)	O(1)
Best for	Sparse graphs	Dense graphs

---

BFS (Breadth-First Search)

BFS explores nodes level by level, visiting the closest nodes first. It uses a queue.

flowchart LR
    subgraph BFS["BFS: A→B→C→D→E"]
        A["A\n(0)"] --> B["B\n(1)"]
        A --> C["C\n(1)"]
        B --> D["D\n(2)"]
        C -.-> D
        D --> E["E\n(3)"]
    end
    style A fill:#3b82f6,color:#fff
    style B fill:#8b5cf6,color:#fff
    style C fill:#8b5cf6,color:#fff
    style D fill:#22c55e,color:#fff
    style E fill:#f59e0b,color:#fff

function bfs(graph, start) {
  const visited = new Set();
  const queue = [start];
  const result = [];

  visited.add(start);

  while (queue.length > 0) {
    const vertex = queue.shift();
    result.push(vertex);

    for (const neighbor of graph.getNeighbors(vertex)) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
  return result;
}

console.log(bfs(graph, "A")); // ["A", "B", "C", "D", "E"]

BFS Shortest Path

function shortestPath(graph, start, end) {
  const visited = new Set();
  const queue = [[start, [start]]];
  visited.add(start);

  while (queue.length > 0) {
    const [vertex, path] = queue.shift();

    if (vertex === end) return path;

    for (const neighbor of graph.getNeighbors(vertex)) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push([neighbor, [...path, neighbor]]);
      }
    }
  }
  return null;
}

console.log(shortestPath(graph, "A", "E")); // ["A", "B", "D", "E"]

---

DFS (Depth-First Search)

DFS explores as deep as possible before backtracking. It uses a stack or recursion.

// Recursive DFS
function dfs(graph, start, visited = new Set()) {
  visited.add(start);
  const result = [start];

  for (const neighbor of graph.getNeighbors(start)) {
    if (!visited.has(neighbor)) {
      result.push(...dfs(graph, neighbor, visited));
    }
  }
  return result;
}

// Iterative DFS
function dfsIterative(graph, start) {
  const visited = new Set();
  const stack = [start];
  const result = [];

  while (stack.length > 0) {
    const vertex = stack.pop();
    if (visited.has(vertex)) continue;

    visited.add(vertex);
    result.push(vertex);

    for (const neighbor of graph.getNeighbors(vertex)) {
      if (!visited.has(neighbor)) {
        stack.push(neighbor);
      }
    }
  }
  return result;
}

BFS vs. DFS

Feature	BFS	DFS
Data structure	Queue	Stack/Recursion
Order	Level by level	As deep as possible
Shortest path	Yes	No
Space	O(V)	O(V)
Use cases	Shortest path, level traversal	Cycle detection, topological sort

---

Cycle Detection

function hasCycle(graph) {
  const visited = new Set();

  function dfs(vertex, parent) {
    visited.add(vertex);
    for (const neighbor of graph.getNeighbors(vertex)) {
      if (!visited.has(neighbor)) {
        if (dfs(neighbor, vertex)) return true;
      } else if (neighbor !== parent) {
        return true;
      }
    }
    return false;
  }

  for (const vertex of graph.adjacencyList.keys()) {
    if (!visited.has(vertex)) {
      if (dfs(vertex, null)) return true;
    }
  }
  return false;
}

---

Dijkstra's Algorithm (Shortest Path)

Finds the shortest path from a source to all vertices in a weighted graph.

flowchart LR
    A["A"] -->|"4"| B["B"]
    A -->|"2"| C["C"]
    B -->|"3"| D["D"]
    C -->|"1"| B
    C -->|"5"| D
    B -->|"1"| E["E"]
    D -->|"2"| E
    style A fill:#3b82f6,color:#fff
    style E fill:#22c55e,color:#fff

function dijkstra(graph, start) {
  const distances = new Map();
  const previous = new Map();
  const visited = new Set();

  for (const vertex of graph.keys()) {
    distances.set(vertex, Infinity);
  }
  distances.set(start, 0);

  while (visited.size < graph.size) {
    let minVertex = null;
    let minDist = Infinity;
    for (const [vertex, dist] of distances) {
      if (!visited.has(vertex) && dist < minDist) {
        minVertex = vertex;
        minDist = dist;
      }
    }

    if (minVertex === null) break;
    visited.add(minVertex);

    for (const { node, weight } of graph.get(minVertex)) {
      if (visited.has(node)) continue;
      const newDist = distances.get(minVertex) + weight;
      if (newDist < distances.get(node)) {
        distances.set(node, newDist);
        previous.set(node, minVertex);
      }
    }
  }

  return { distances, previous };
}

const weightedGraph = new Map();
weightedGraph.set("A", [{ node: "B", weight: 4 }, { node: "C", weight: 2 }]);
weightedGraph.set("B", [{ node: "D", weight: 3 }, { node: "E", weight: 1 }]);
weightedGraph.set("C", [{ node: "B", weight: 1 }, { node: "D", weight: 5 }]);
weightedGraph.set("D", [{ node: "E", weight: 2 }]);
weightedGraph.set("E", []);

const result = dijkstra(weightedGraph, "A");
console.log(result.distances);
// Map { 'A' => 0, 'B' => 3, 'C' => 2, 'D' => 6, 'E' => 4 }

Dijkstra's Complexity

Implementation	Complexity
Array	O(V²)
Priority Queue	O((V + E) log V)

---

Topological Sort

Orders vertices of a Directed Acyclic Graph (DAG) according to edge direction.

function topologicalSort(graph) {
  const visited = new Set();
  const stack = [];

  function dfs(vertex) {
    visited.add(vertex);
    for (const neighbor of graph.get(vertex) || []) {
      if (!visited.has(neighbor)) {
        dfs(neighbor);
      }
    }
    stack.push(vertex);
  }

  for (const vertex of graph.keys()) {
    if (!visited.has(vertex)) {
      dfs(vertex);
    }
  }

  return stack.reverse();
}

const tasks = new Map();
tasks.set("A", ["C"]);
tasks.set("B", ["C", "D"]);
tasks.set("C", ["E"]);
tasks.set("D", ["E"]);
tasks.set("E", []);

console.log(topologicalSort(tasks));
// e.g., ["B", "D", "A", "C", "E"]

---

Summary

Concept	Description
Graph	Data structure of vertices and edges
BFS	Queue-based level-order exploration
DFS	Stack/recursion-based deep exploration
Dijkstra's	Shortest path in weighted graphs
Topological Sort	Dependency ordering for DAGs

Key Takeaways

1. Adjacency lists suit sparse graphs; matrices suit dense graphs
2. BFS guarantees shortest path in unweighted graphs
3. DFS is ideal for cycle detection and topological sorting
4. Dijkstra's cannot handle negative weights (use Bellman-Ford instead)

---

Practice Problems

Problem 1: Basic

Implement a function to check if a path exists between two vertices in an undirected graph.

Problem 2: Intermediate

Count the number of connected components in an undirected graph.

Challenge

Implement Dijkstra's algorithm with a priority queue and return both the shortest path and its cost from source to destination.

---

References

• Wikipedia - Graph
• Visualgo - Graph
• Wikipedia - Dijkstra's algorithm

---

Next up: In Day 10, we'll explore "Dynamic Programming & Greedy Algorithms" — two powerful techniques for solving optimization problems.