Graphs

Graphs are collections of nodes (vertices) connected by edges. Used to represent relationships and networks.

Animated Visualization

Step 1 of 5

Undirected Graph: 4 nodes (A, B, C, D) with 5 edges

javascript

← Scroll →

// Graph Representation (Adjacency List)
class Graph {
  constructor() {
    this.adjacencyList = {};
  }
  // Add vertex
  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) {
      this.adjacencyList[vertex] = [];
    }
  }
  // Add edge
  addEdge(v1, v2) {
    this.adjacencyList[v1].push(v2);
    this.adjacencyList[v2].push(v1);
  }
  // BFS - Breadth First Search
  bfs(start) {
    const queue = [start];
    const visited = { [start]: true };
    const result = [];
    while (queue.length) {
      const vertex = queue.shift();
      result.push(vertex);
      this.adjacencyList[vertex].forEach(neighbor => {
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          queue.push(neighbor);
        }
      });
    }
    return result;
  }
  // DFS - Depth First Search
  dfs(start) {
    const visited = {};
    const result = [];
    const dfsHelper = (vertex) => {
      if (!vertex) return;
      visited[vertex] = true;
      result.push(vertex);
      this.adjacencyList[vertex].forEach(neighbor => {
        if (!visited[neighbor]) {
          dfsHelper(neighbor);
        }
      });
    };
    dfsHelper(start);
    return result;
  }
  // Time Complexity:
  // BFS: O(V + E)
  // DFS: O(V + E)
  // Add Vertex: O(1)
  // Add Edge: O(1)

Swipe horizontally to view full code

Explanation

Graphs represent relationships between entities. BFS explores level by level using a queue, while DFS explores deeply using recursion/stack. Both have O(V + E) time complexity where V is vertices and E is edges.

Operations & Complexity

BFSO(V + E)

Breadth-first traversal

DFSO(V + E)

Depth-first traversal

Add VertexO(1)

Add new node

Add EdgeO(1)

Connect two nodes

Time Complexity