Introduction to Graphs

Graphs are one of the most versatile data structures, modeling relationships between objects. From social networks to road maps to the internet itself, graphs are everywhere.

What is a Graph?

A graph G = (V, E) consists of:

• V: A set of vertices (nodes)
• E: A set of edges connecting vertices

Simple Graph:

    A --- B
    |   / |
    |  /  |
    | /   |
    C --- D

Vertices: {A, B, C, D}
Edges: {(A,B), (A,C), (B,C), (B,D), (C,D)}

Types of Graphs

Directed vs Undirected

Undirected:              Directed:
A --- B                  A --> B
  |                        |
  |                        v
  C                        C

Edge (A,B) = (B,A)       Edge (A,B) ≠ (B,A)
Friendship               Twitter follows

Weighted vs Unweighted

Unweighted:              Weighted:
A --- B                  A --5-- B
|     |                  |       |
C --- D                  3       2
                         |       |
                         C --4-- D

All edges equal          Edges have costs

Cyclic vs Acyclic

Cyclic:                  Acyclic (DAG):
A --> B                  A --> B
^     |                        |
|     v                        v
D <-- C                  C --> D

Has cycle A→B→C→D→A      No cycles (Directed Acyclic Graph)

Graph Terminology

| Term | Definition | |------|------------| | Adjacent | Two vertices connected by an edge | | Degree | Number of edges connected to a vertex | | In-degree | Number of incoming edges (directed) | | Out-degree | Number of outgoing edges (directed) | | Path | Sequence of vertices connected by edges | | Cycle | Path that starts and ends at same vertex | | Connected | Path exists between every pair of vertices | | Component | Maximal connected subgraph |

Graph Representations

1. Adjacency Matrix

2D array where matrix[i][j] = 1 if edge exists:

// For graph: 0 -- 1, 0 -- 2, 1 -- 2

//     0  1  2
// 0 [[0, 1, 1],
// 1  [1, 0, 1],
// 2  [1, 1, 0]]

struct GraphMatrix {
    v: usize,
    adj: Vec<Vec<i32>>,
}

impl GraphMatrix {
    fn new(num_vertices: usize) -> Self {
        GraphMatrix {
            v: num_vertices,
            adj: vec![vec![0; num_vertices]; num_vertices],
        }
    }

    fn add_edge(&mut self, u: usize, v: usize, weight: i32) {
        self.adj[u][v] = weight;
        self.adj[v][u] = weight;  // Remove for directed graph
    }

    fn has_edge(&self, u: usize, v: usize) -> bool {
        self.adj[u][v] != 0
    }

    fn neighbors(&self, u: usize) -> Vec<usize> {
        (0..self.v).filter(|&v| self.adj[u][v] != 0).collect()
    }
}

Complexity:

• Space: O(V²)
• Add edge: O(1)
• Check edge: O(1)
• Find neighbors: O(V)

2. Adjacency List

Each vertex stores a list of its neighbors:

// For graph: 0 -- 1, 0 -- 2, 1 -- 2

// 0: [1, 2]
// 1: [0, 2]
// 2: [0, 1]

struct GraphList {
    v: usize,
    adj: Vec<Vec<(usize, i32)>>,
}

impl GraphList {
    fn new(num_vertices: usize) -> Self {
        GraphList {
            v: num_vertices,
            adj: vec![Vec::new(); num_vertices],
        }
    }

    fn add_edge(&mut self, u: usize, v: usize, weight: i32) {
        self.adj[u].push((v, weight));
        self.adj[v].push((u, weight));  // Remove for directed
    }

    fn has_edge(&self, u: usize, v: usize) -> bool {
        self.adj[u].iter().any(|&(neighbor, _)| neighbor == v)
    }

    fn neighbors(&self, u: usize) -> Vec<usize> {
        self.adj[u].iter().map(|&(v, _)| v).collect()
    }
}

Complexity:

• Space: O(V + E)
• Add edge: O(1)
• Check edge: O(degree)
• Find neighbors: O(degree)

3. Edge List

Simply list all edges:

edges = [(0, 1), (0, 2), (1, 2)]

# Good for algorithms that process edges (Kruskal's)
# Not good for querying neighbors

Choosing a Representation

| Criteria | Matrix | Adjacency List | |----------|--------|----------------| | Space | O(V²) | O(V + E) | | Check edge | O(1) | O(degree) | | Iterate neighbors | O(V) | O(degree) | | Add edge | O(1) | O(1) | | Dense graph | Better | - | | Sparse graph | - | Better |

Building Graphs in Practice

From Edge List

fn build_graph(num_vertices: usize, edges: &[(usize, usize)]) -> Vec<Vec<usize>> {
    let mut graph = vec![Vec::new(); num_vertices];

    for &(u, v) in edges {
        graph[u].push(v);
        graph[v].push(u);  // Undirected
    }

    graph
}

fn main() {
    let edges = vec![(0, 1), (0, 2), (1, 2), (2, 3)];
    let graph = build_graph(4, &edges);
    // graph[0] = [1, 2]
    // graph[1] = [0, 2]
    // graph[2] = [0, 1, 3]
    // graph[3] = [2]
}

Using HashMap (Flexible)

use std::collections::HashMap;

struct Graph<T> {
    graph: HashMap<T, Vec<(T, i32)>>,
    directed: bool,
}

impl<T: Eq + std::hash::Hash + Clone> Graph<T> {
    fn new(directed: bool) -> Self {
        Graph {
            graph: HashMap::new(),
            directed,
        }
    }

    fn add_edge(&mut self, u: T, v: T, weight: i32) {
        self.graph.entry(u.clone())
            .or_insert_with(Vec::new)
            .push((v.clone(), weight));

        if !self.directed {
            self.graph.entry(v)
                .or_insert_with(Vec::new)
                .push((u, weight));
        }
    }

    fn neighbors(&self, u: &T) -> Vec<&(T, i32)> {
        self.graph.get(u).map(|v| v.iter().collect()).unwrap_or_default()
    }

    fn vertices(&self) -> Vec<&T> {
        self.graph.keys().collect()
    }
}

// Usage
fn main() {
    let mut g = Graph::new(false);
    g.add_edge("A", "B", 1);
    g.add_edge("A", "C", 1);
    g.add_edge("B", "C", 1);

    println!("{:?}", g.neighbors(&"A"));  // [("B", 1), ("C", 1)]
}

Common Graph Problems

| Problem | Algorithm | Time | |---------|-----------|------| | Traversal | BFS, DFS | O(V + E) | | Shortest path (unweighted) | BFS | O(V + E) | | Shortest path (weighted) | Dijkstra | O((V + E) log V) | | Cycle detection | DFS | O(V + E) | | Topological sort | DFS / Kahn's | O(V + E) | | Connected components | DFS/BFS | O(V + E) | | Minimum spanning tree | Prim's, Kruskal's | O(E log V) |

Real-World Graph Examples

1. Social Networks: People are vertices, friendships are edges
2. Web: Pages are vertices, links are directed edges
3. Road Maps: Intersections are vertices, roads are weighted edges
4. Dependencies: Tasks are vertices, prerequisites are edges
5. Circuits: Components are vertices, connections are edges

Key Takeaways

1. Graphs model relationships between objects
2. Directed vs undirected, weighted vs unweighted
3. Adjacency list is best for sparse graphs (most real-world graphs)
4. Adjacency matrix is best for dense graphs or O(1) edge lookup
5. Many important algorithms operate on graphs
6. Understanding representation is key to efficient graph algorithms

Graphs are fundamental to computer science. The next lessons cover graph traversal algorithms (DFS, BFS) and their applications to solving practical problems.