14. Graphs

🧸 ELI5: A tree is like a family — no loops. A graph is like your group of friends — you can be friends with anyone, friendships can loop around (your friend's friend can also be your friend directly), and there's no single "boss" at the top.

🌍 Real life: A social network (people = dots/"nodes", friendships = lines/"edges"). A road map (cities = nodes, roads = edges). Flight routes between airports.

📝 Pseudocode:

graph = {
    "Alice": ["Bob", "Carol"],
    "Bob": ["Alice"],
    "Carol": ["Alice"]
}

🐹 Go:

package main

import "fmt"

type Graph struct {
	adjacency map[string][]string
}

func NewGraph() *Graph {
	return &Graph{adjacency: make(map[string][]string)}
}

func (g *Graph) AddFriendship(a, b string) {
	g.adjacency[a] = append(g.adjacency[a], b)
	g.adjacency[b] = append(g.adjacency[b], a)
}

func main() {
	social := NewGraph()
	social.AddFriendship("Alice", "Bob")
	social.AddFriendship("Alice", "Carol")
	fmt.Println(social.adjacency["Alice"]) // [Bob Carol]
}

🇨 C — without a built-in map, people become integer indices (0, 1, 2...) into a fixed-size names/adjacency table; this same integer-indexed shape is reused for BFS/DFS right below:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NODES 16

typedef struct {
    char names[MAX_NODES][32];
    int  adj[MAX_NODES][MAX_NODES];       // adj[i][j] = 1 if a friendship exists
    int  adj_list[MAX_NODES][MAX_NODES];  // neighbor indices, in insertion order
    int  adj_count[MAX_NODES];
    int  num_nodes;
} Graph;

int graph_add_node(Graph *g, const char *name) {
    strncpy(g->names[g->num_nodes], name, 31);
    return g->num_nodes++;
}

void graph_add_friendship(Graph *g, int a, int b) {
    if (!g->adj[a][b]) { g->adj[a][b] = 1; g->adj_list[a][g->adj_count[a]++] = b; }
    if (!g->adj[b][a]) { g->adj[b][a] = 1; g->adj_list[b][g->adj_count[b]++] = a; }
}

int main(void) {
    Graph social = {0};
    int alice = graph_add_node(&social, "Alice");
    int bob   = graph_add_node(&social, "Bob");
    int carol = graph_add_node(&social, "Carol");

    graph_add_friendship(&social, alice, bob);
    graph_add_friendship(&social, alice, carol);

    for (int i = 0; i < social.adj_count[alice]; i++) {
        printf("%s ", social.names[social.adj_list[alice][i]]); // Bob Carol
    }
    printf("\n");
    return 0;
}

⏱️ Complexity: Storage = O(V + E) (V = number of people/nodes, E = number of friendships/edges).