Graphs

If Trees are hierarchical (parents and children), Graphs are relational (neighbors and friends).

In the real world, almost everything interesting is a Graph. The Internet is a graph of computers. Google Maps is a graph of intersections and roads. Social Media is a graph of people.

The Definitions:

• Vertex (Node): The entity (e.g., "City", "Person", "Webpage").

• Edge: The connection between two vertices.

• Weight: (Optional) The cost or distance of the edge.

• Direction:

  • Undirected: Two-way street (e.g., Facebook Friends). If A is friends with B, B is friends with A.

  • Directed (Digraph): One-way street (e.g., Twitter Follows). A follows B, but B might not follow A.

The Mechanics: Matrix vs. List

The biggest architectural decision when using a graph is how to store it in memory. There are two standard approaches:

1. Adjacency Matrix

A 2D array (grid) of size V \times V (where V is the number of vertices).

• matrix[i][j] = 1 means there is an edge from i to j.

• Pros: Instant O(1)$lookup to check if an edge exists.

• Cons: Consumes O(V^2) memory. If you have 10,000 users, you need a grid of size 100,000,000, even if they only have 2 friends each. Terrible for "Sparse" graphs.

2. Adjacency List (The Industry Standard)

A Hash Map (or Array) where every Key is a Vertex, and the Value is a list of its neighbors.

• { "A": ["B", "C"], "B": ["A"] }

• Pros: Memory efficient. Uses O(V + E) space.

• Cons: Checking if an edge exists takes O(K) where K is the number of neighbors.

Operations & Complexity Analysis (Adjacency List)

Operation	Time Complexity	Notes
Add Vertex	O(1)	Simply add a key to the Map.
Add Edge	O(1)	Append to the neighbor list of the vertex.
Remove Vertex	O(V + E)	You must remove the vertex and iterate all other lists to remove connections to it.
BFS / DFS	O(V + E)	You visit every vertex (V) and traverse every edge (E).

JavaScript Implementation

We will implement an Undirected, Unweighted Graph using an Adjacency List (via a JavaScript Map).

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

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

    // Add a Connection
    addEdge(v1, v2) {
        // Ensure vertices exist
        this.addVertex(v1);
        this.addVertex(v2);

        // Undirected: Connection goes both ways
        this.adjacencyList.get(v1).push(v2);
        this.adjacencyList.get(v2).push(v1);
    }

    // 1. Breadth First Search (BFS)
    // Explore neighbors, then neighbors' neighbors.
    // Use a QUEUE. Good for finding shortest path in unweighted graphs.
    bfs(start) {
        const queue = [start];
        const result = [];
        const visited = new Set();
        visited.add(start);

        while (queue.length > 0) {
            const currentVertex = queue.shift(); // Dequeue
            result.push(currentVertex);

            const neighbors = this.adjacencyList.get(currentVertex);
            for (const neighbor of neighbors) {
                if (!visited.has(neighbor)) {
                    visited.add(neighbor);
                    queue.push(neighbor);
                }
            }
        }
        return result;
    }

    // 2. Depth First Search (DFS)
    // Explore as deep as possible before backtracking.
    // Use Recursion (Stack). Good for mazes, puzzles, and analyzing structure.
    dfsRecursive(start) {
        const result = [];
        const visited = new Set();
        const adjacencyList = this.adjacencyList; // Capture scope

        (function dfs(vertex) {
            if (!vertex) return;
            visited.add(vertex);
            result.push(vertex);

            const neighbors = adjacencyList.get(vertex);
            for (const neighbor of neighbors) {
                if (!visited.has(neighbor)) {
                    dfs(neighbor);
                }
            }
        })(start);

        return result;
    }
}

// Usage
const network = new Graph();
network.addEdge("Tokyo", "Dallas");
network.addEdge("Dallas", "Aspen");
network.addEdge("Aspen", "Tokyo"); // Creates a cycle
network.addEdge("Dallas", "Los Angeles");

console.log(network.bfs("Tokyo")); 
// Output: ["Tokyo", "Dallas", "Aspen", "Los Angeles"] (Order may vary based on insertion)

Expert Insight: The Relational Limit

Why do we have Graph Databases like Neo4j if we can just use SQL?

The Join Problem:

In a SQL database (Relational), modeling "Friends of Friends of Friends" requires recursive JOIN operations.

• 1 Hop: Fast.

• 2 Hops: Slower.

• 3+ Hops: The database grinds to a halt.

The Graph Solution:

In a Graph Data Structure (or Database), "hopping" from one node to another is a pointer dereference. It is O(1) per hop. Whether you are 1 step away or 100 steps away, the cost of the next step is constant. This is why LinkedIn can instantly show you "3rd-degree connections" while a SQL database would struggle.

Algorithm Choice:

• BFS (Queue): Use this for "Shortest Path" in unweighted graphs (e.g., fewest hops to Kevin Bacon).

• Dijkstra's Algorithm (Priority Queue): Use this for "Shortest Path" in weighted graphs (e.g., fastest route on Google Maps).

• DFS (Stack): Use this for topological sorting (dependencies) or detecting cycles.

Conclusion

Graphs are the most versatile data structure but also the most complex to implement correctly.

1. Always use Adjacency Lists unless you have a specific mathematical reason to use a Matrix.

2. Watch out for Cycles (A -> B -> A). Infinite loops are common in graph traversal; always use a visited Set.

3. Real-world power: If your data involves connections, dependencies, or routes, do not try to force it into a Tree or a List. Use a Graph.