🕸️ Graphs

The Social Network Analogy

Think of a social network:

• People are nodes (vertices)
• Friendships are edges (connections)
• Some connections are mutual (undirected)
• Some are one-way like Twitter follows (directed)

Graphs model these complex relationships - entities connected in arbitrary ways, unlike trees which have strict hierarchies.

Graph Structure

Social Network:
    Alice ---- Bob
| \ |
| \ |
    Carol --- Dave

Nodes: Alice, Bob, Carol, Dave
Edges: Alice-Bob, Alice-Carol, Alice-Dave, Bob-Dave, Carol-Dave

Key Terminology

Vertex (Node):    An entity (Alice)
Edge:             Connection between vertices
Degree:           Number of edges connected to a vertex
Path:             Sequence of vertices connected by edges
Cycle:            Path that starts and ends at same vertex
Connected:        Path exists between all pairs of vertices

Directed vs Undirected

Undirected Graph

Edges go both ways (like Facebook friendships):

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

A-B means: A knows B AND B knows A

Directed Graph (Digraph)

Edges have direction (like Twitter follows):

    A → B
    ↓   ↓
    C → D

A→B means: A follows B (B may not follow A back)

Weighted vs Unweighted

Unweighted

All edges are equal:

    A --- B --- C

A to C: 2 edges (A→B→C)

Weighted

Edges have costs (distance, time, price):

    A --5-- B --3-- C
     \            /
      ----10----

A to C:
  via B: 5 + 3 = 8
  direct: 10

Shorter path via B!

How to Store Graphs

Adjacency List

Each vertex stores its list of neighbors:

Graph:    A --- B
          |     |
          C --- D

List:
  A: [B, C]
  B: [A, D]
  C: [A, D]
  D: [B, C]

Space: O(V + E) Often used for: Sparse graphs (few edges)

Adjacency Matrix

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

    A  B  C  D
A [ 0  1  1  0 ]
B [ 1  0  0  1 ]
C [ 1  0  0  1 ]
D [ 0  1  1  0 ]

Space: O(V²) Often used for: Dense graphs, fast edge lookups

Comparison

Graph Traversals

BFS (Breadth-First Search)

Explore level by level using a queue:

    A --- B --- E
    |     |
    C --- D

BFS from A: A → B → C → D → E

Visits in order of distance from start.

DFS (Depth-First Search)

Go deep first using stack/recursion:

DFS from A: A → B → D → C → E
           (or A → B → E → D → C)

Explores one path completely before backtracking.

Common Graph Types

Connected Graph

Path exists between every pair of vertices:

    A --- B
     \   /
      \ /
       C
All connected!

Disconnected Graph

Some vertices can't reach each other:

    A --- B     D --- E

    |           |
Component 1   Component 2

Cyclic vs Acyclic

Cyclic (has a cycle):
    A → B
    ↑   ↓
    D ← C

Acyclic (no cycles):
    A → B → C → D

DAG (Directed Acyclic Graph)

Directed + no cycles. Used for:

• Task dependencies
• Build systems
• Data pipelines

   A → B → D
    ↘   ↗
      C

No way to go in circles!

Classic Graph Problems

1. Find Path Between Two Nodes

Is there a path from A to E?

BFS or DFS from A, check if E is visited.

2. Connected Components

How many separate groups exist?

Run BFS/DFS from each unvisited node.
Each run finds one component.

3. Cycle Detection

Does the graph have a cycle?

DFS with visited tracking.
If you reach an already-in-progress node, cycle found!

4. Shortest Path

Unweighted: BFS
Weighted (no negative): Dijkstra
Weighted (with negative): Bellman-Ford

5. Topological Sort

Order tasks so dependencies come first.

Works when the graph is a DAG (directed acyclic graph).
Result: A, B, C, D (if A→B, A→C, B→D, C→D)

Real-World Applications

Social Networks

Nodes: Users
Edges: Friendships/Follows
Algorithms: "People you may know", shortest connection

Maps/Navigation

Nodes: Intersections
Edges: Roads (weighted by distance/time)
Algorithms: Shortest path (Dijkstra, A*)

Web

Nodes: Web pages
Edges: Links
Algorithms: PageRank, web crawling

Dependencies

Nodes: Tasks/Packages
Edges: Dependencies
Algorithms: Topological sort, cycle detection

Graph vs Tree

A tree is a special graph: connected, acyclic, with one root.

Common Mistakes

1. Forgetting Visited Tracking

Without it, you'll loop forever on cyclic graphs!

2. Assuming Connectivity

Not all graphs are connected. Handle multiple components.

3. Directed vs Undirected Confusion

A→B doesn't mean B→A in directed graphs.

4. Wrong Data Structure

Use adjacency list for sparse, matrix for dense graphs.

FAQ

Q: Graph vs tree - when to use which?

Tree: hierarchical data, one parent per node. Graph: complex relationships, arbitrary connections.

Q: How to represent weighted edges?

Adjacency list: store (neighbor, weight) pairs. Matrix: store weight instead of 1/0.

Q: What's the most common graph representation?

Adjacency list - most graphs are sparse.

Q: BFS or DFS?

BFS: shortest path (unweighted), level-order. DFS: path finding, cycle detection, topological sort.

Summary

A graph represents entities (vertices) connected by relationships (edges).

Key Takeaways:

• Vertices (nodes) + edges (connections)
• Directed vs undirected, weighted vs unweighted
• Store with adjacency list or matrix
• Traverse with BFS (level-order) or DFS (deep-first)
• Common problems: path finding, cycles, connectivity
• Used in: social networks, maps, the web, dependencies

Graphs model the connected world around us!