Graph Data Structures: Algorithms & Applications

Master graph representations, traversal algorithms, and pathfinding techniques. This tutorial covers adjacency matrices/lists, BFS/DFS, shortest path algorithms, and advanced graph theory concepts with implementation examples.

Graph Usage in Systems (2023)

Social Networks (35%)

Routing Systems (25%)

Recommendation Engines (20%)

Dependency Analysis (20%)

1. Graph Fundamentals

Core Properties:

Vertices (Nodes) and Edges: Fundamental building blocks
Directed vs Undirected: Edge direction significance
Weighted vs Unweighted: Edge cost considerations
Cyclic vs Acyclic: Presence of cycles

Representation Methods:

Adjacency Matrix


class GraphMatrix {
  constructor(size) {
    this.matrix = Array(size).fill()
                   .map(() => Array(size).fill(0));
  }
  
  addEdge(i, j, weight = 1) {
    this.matrix[i][j] = weight;
    // For undirected:
    // this.matrix[j][i] = weight;
  }
}

Adjacency List


class GraphList {
  constructor() {
    this.adjList = new Map();
  }
  
  addVertex(v) {
    this.adjList.set(v, []);
  }
  
  addEdge(v, w, weight = 1) {
    this.adjList.get(v).push({ node: w, weight });
    // For undirected:
    // this.adjList.get(w).push({ node: v, weight });
  }
}

Time Complexities:

Operation	Matrix	List
Add Vertex	O(V²)	O(1)
Add Edge	O(1)	O(1)
Remove Vertex	O(V²)	O(E)
Remove Edge	O(1)	O(V)
Query	O(1)	O(V)
Storage	O(V²)	O(V+E)

2. Graph Traversal Algorithms

Essential Algorithms:

Breadth-First Search (BFS)


function BFS(start) {
  const queue = [start];
  const visited = new Set([start]);
  const result = [];
  
  while (queue.length) {
    const vertex = queue.shift();
    result.push(vertex);
    
    for (const neighbor of this.adjList.get(vertex)) {
      if (!visited.has(neighbor.node)) {
        visited.add(neighbor.node);
        queue.push(neighbor.node);
      }
    }
  }
  return result;
}

Depth-First Search (DFS)


function DFS(start) {
  const stack = [start];
  const visited = new Set();
  const result = [];
  
  while (stack.length) {
    const vertex = stack.pop();
    if (!visited.has(vertex)) {
      visited.add(vertex);
      result.push(vertex);
      
      // Reverse to maintain order
      const neighbors = [...this.adjList.get(vertex)].reverse();
      for (const neighbor of neighbors) {
        stack.push(neighbor.node);
      }
    }
  }
  return result;
}

Application Scenarios:

BFS: Shortest path in unweighted graphs, web crawling
DFS: Topological sorting, maze solving, cycle detection
Iterative Deepening: Combines BFS and DFS advantages
Bidirectional Search: Pathfinding from both ends

3. Shortest Path Algorithms

Pathfinding Techniques:

Dijkstra's Algorithm


function dijkstra(start) {
  const distances = {};
  const prev = {};
  const pq = new PriorityQueue();
  
  // Initialize distances
  for (const vertex of this.adjList.keys()) {
    distances[vertex] = Infinity;
  }
  distances[start] = 0;
  pq.enqueue(start, 0);
  
  while (!pq.isEmpty()) {
    const { element: u, priority: dist } = pq.dequeue();
    
    for (const { node: v, weight } of this.adjList.get(u)) {
      const alt = dist + weight;
      if (alt < distances[v]) {
        distances[v] = alt;
        prev[v] = u;
        pq.enqueue(v, alt);
      }
    }
  }
  return { distances, prev };
}

Bellman-Ford Algorithm


function bellmanFord(start) {
  const distances = {};
  const prev = {};
  
  // Initialize
  for (const vertex of this.adjList.keys()) {
    distances[vertex] = Infinity;
  }
  distances[start] = 0;
  
  // Relax all edges V-1 times
  for (let i = 1; i < this.adjList.size; i++) {
    for (const [u, edges] of this.adjList.entries()) {
      for (const { node: v, weight } of edges) {
        if (distances[u] + weight < distances[v]) {
          distances[v] = distances[u] + weight;
          prev[v] = u;
        }
      }
    }
  }
  
  // Check for negative cycles
  // (Code omitted for brevity)
  
  return { distances, prev };
}

Algorithm Comparison:

Algorithm	Time	Space	Use Case
Dijkstra	O(E + V log V)	O(V)	No negative weights
Bellman-Ford	O(VE)	O(V)	Negative weights, detect cycles
A*	O(E)	O(V)	Heuristic-based pathfinding
Floyd-Warshall	O(V³)	O(V²)	All pairs shortest paths

Graph Problem-Solving Cheat Sheet

Problem Type	Algorithm	Time Complexity
Shortest Path (Unweighted)	BFS	O(V + E)
Shortest Path (Weighted)	Dijkstra	O(E + V log V)
Negative Weights	Bellman-Ford	O(VE)
All Pairs Shortest Path	Floyd-Warshall	O(V³)
Minimum Spanning Tree	Prim/Kruskal	O(E log V)
Topological Sort	DFS	O(V + E)

4. Advanced Graph Concepts

Minimum Spanning Trees

Prim's and Kruskal's algorithms


function primMST() {
  const parent = {};
  const key = {};
  const inMST = new Set();
  const pq = new PriorityQueue();
  
  // Initialize
  for (const vertex of this.adjList.keys()) {
    key[vertex] = Infinity;
  }
  const start = this.adjList.keys().next().value;
  key[start] = 0;
  pq.enqueue(start, 0);
  
  while (!pq.isEmpty()) {
    const { element: u } = pq.dequeue();
    inMST.add(u);
    
    for (const { node: v, weight } of this.adjList.get(u)) {
      if (!inMST.has(v) && weight < key[v]) {
        parent[v] = u;
        key[v] = weight;
        pq.enqueue(v, key[v]);
      }
    }
  }
  return parent;
}

Strongly Connected Components

Kosaraju's algorithm


function kosaraju() {
  const visited = new Set();
  const order = [];
  const components = [];
  
  // First pass (reverse graph)
  const reversed = this.reverse();
  for (const vertex of reversed.adjList.keys()) {
    if (!visited.has(vertex)) {
      reversed.fillOrder(vertex, visited, order);
    }
  }
  
  // Second pass (original graph)
  visited.clear();
  const reversedOrder = order.reverse();
  for (const vertex of reversedOrder) {
    if (!visited.has(vertex)) {
      const component = [];
      this.DFSUtil(vertex, visited, component);
      components.push(component);
    }
  }
  return components;
}

Network Flow

Ford-Fulkerson method


function fordFulkerson(source, sink) {
  let maxFlow = 0;
  const residual = this.createResidualGraph();
  
  while (true) {
    const { parent, minCapacity } = residual.bfs(source, sink);
    if (minCapacity === 0) break;
    
    maxFlow += minCapacity;
    let v = sink;
    while (v !== source) {
      const u = parent[v];
      residual.updateFlow(u, v, minCapacity);
      v = u;
    }
  }
  return maxFlow;
}

Graph Problem-Solving Checklist

✓ Choose appropriate representation (matrix/list)

✓ Identify graph type (directed/weighted/cyclic)

✓ Select optimal algorithm based on constraints

✓ Consider space-time tradeoffs

✓ Handle edge cases (disconnected graphs, negative weights)

DSA Expert Insight: Graph problems appear in 40% of technical interviews, especially in pathfinding and optimization scenarios. Mastering both fundamental traversals and advanced algorithms is crucial for solving complex real-world problems efficiently.

0 Interaction

0 Views

0 Likes