Graphs

Graph Data Structure

A graph consists of vertices (nodes) and edges (connections). Graphs can be directed/undirected, weighted/unweighted, and cyclic/acyclic.

Graph Representation

// Adjacency List
class Graph {
  constructor() {
    this.adjacencyList = {};
  }

  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
  }

  addEdge(v1, v2) {
    this.adjacencyList[v1].push(v2);
    this.adjacencyList[v2].push(v1); // For undirected
  }
}

// BFS - Breadth First Search
function bfs(graph, start) {
  const visited = new Set();
  const queue = [start];
  const result = [];
  
  visited.add(start);
  
  while (queue.length) {
    const vertex = queue.shift();
    result.push(vertex);
    
    for (const neighbor of graph.adjacencyList[vertex]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }

  

    
Learn More
    

      
        
GeeksforGeeks: Graph
        
Comprehensive guide to Graph data structures and algorithms.
      
      
        
LeetCode: Graph
        
Practice graph traversal and shortest path problems.
      
    
  

  return result;
}

// DFS - Depth First Search
function dfs(graph, start, visited = new Set(), result = []) {
  visited.add(start);
  result.push(start);
  
  for (const neighbor of graph.adjacencyList[start]) {
    if (!visited.has(neighbor)) {
      dfs(graph, neighbor, visited, result);
    }
  }
  return result;
}