Eventually Bitwise

Graph

Overview

A Graph is a non-linear data structure consisting of a finite set of vertices (or nodes) and a set of edges that connect pairs of vertices. Graphs are used to represent networks of interconnected objects.

Core Concepts

  • Directed vs. Undirected:
    • Directed (Digraph): Edges have a direction (e.g., a Twitter follow).
    • Undirected: Edges have no direction (e.g., a Facebook friendship).
  • Weighted vs. Unweighted:
    • Weighted: Edges have a value/cost (e.g., distance between two cities).
    • Unweighted: All edges are equal.
  • Representation:
    • Adjacency Matrix: A 2D array where matrix[i][j] = 1 if there is an edge. Fast lookup, but takes $O(V^2)$ space.
    • Adjacency List: An array of lists. More space-efficient for “sparse” graphs.
  • Traversal:
    • Breadth-First Search (BFS): Visits all neighbors first (uses a Queue).
    • Depth-First Search (DFS): Goes as deep as possible down one branch before backtracking (uses a Stack/Recursion).

Code Examples

// Adjacency List representation
const graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"]
};

// Simple DFS implementation
function dfs(node: string, visited: Set<string>) {
    if (visited.has(node)) return;
    console.log(node);
    visited.add(node);
    graph[node].forEach(neighbor => dfs(neighbor, visited));
}
dfs("A", new Set());

Use Cases

  • Social Networks: Mapping friends, followers, and “people you may know”.
  • GPS / Google Maps: Finding the shortest path between two locations (e.g., using Dijkstra’s Algorithm).
  • Web Crawling: Search engines use graphs to represent links between pages on the internet.

Gotchas

  • Cycles: A path that starts and ends at the same node. If not handled (e.g., using a visited set), traversal algorithms will enter an infinite loop.
  • Connectivity: A graph may be “disconnected,” meaning some nodes cannot be reached from others.
  • Complexity: Graph algorithms can become computationally expensive quickly (e.g., the Traveling Salesperson Problem is NP-hard).

Related Notes

, ,