Graph & Tree — Saidul Islam Rajib

1. Core Relationship

A tree is a connected acyclic graph.
For a tree with n vertices:

Edges = n - 1
Exactly one simple path exists between any two vertices.
Removing any edge disconnects it.
Adding any edge creates exactly one cycle.

flowchart TD
    A["Graph"] --> B["Directed"]
    A --> C["Undirected"]
    B --> D["Weighted / Unweighted"]
    C --> D
    A --> E["Tree"]
    E --> F["Binary Tree"]
    E --> G["BST"]
    E --> H["Heap"]
    E --> I["Trie"]
    E --> J["Segment Tree"]

2. Graph Representation

flowchart LR
    A["Graph"] --> B["Adjacency List"]
    A --> C["Adjacency Matrix"]
    A --> D["Edge List"]

    B --> B1["O(V + E) Space"]
    C --> C1["O(V²) Space"]
    D --> D1["O(E) Space"]

Representation Space Edge Lookup Traversal

Adjacency List O(V+E) O(deg(V)) O(V+E)
Matrix O(V²) O(1) O(V²)
Edge List O(E) O(E) O(E)

For sparse real-world systems, adjacency lists are usually the natural
representation.

3. Traversal

flowchart TD
    S["Start"] --> V["Mark visited"]
    V --> Q{"Traversal?"}
    Q -->|"BFS"| B["Queue"]
    Q -->|"DFS"| D["Stack / Recursion"]
    B --> N["Visit neighbors"]
    D --> N
    N --> X{"Unvisited neighbor?"}
    X -->|"Yes"| V
    X -->|"No"| E["Continue / Finish"]

BFS - Uses a queue. - Finds minimum number of edges in an
unweighted graph. - Time: O(V + E). - Space: O(V).

DFS - Uses recursion or an explicit stack. - Useful for cycle
detection, components, backtracking, topological ordering, and SCC
algorithms. - Time: O(V + E). - Space: O(V).

4. Shortest Paths

flowchart TD
    S["Shortest Path"] --> W{"Edge Weights"}
    W -->|"All equal / unweighted"| BFS["BFS"]
    W -->|"Non-negative"| D["Dijkstra"]
    W -->|"Negative allowed"| BF["Bellman-Ford"]
    W -->|"All-pairs"| FW["Floyd-Warshall"]

    D --> H["Min-Heap"]
    BF --> C["Relax edges V-1 times"]
    FW --> DP["Dynamic Programming"]

Algorithm Weights Typical Complexity

BFS Unweighted O(V+E)
Dijkstra + heap Non-negative O((V+E) log V)
Bellman-Ford Negative allowed O(VE)
Floyd-Warshall All pairs O(V³)

Important: Dijkstra is not valid when reachable negative-weight
edges can invalidate its greedy choice.

5. Minimum Spanning Tree

For a connected, undirected, weighted graph, an MST connects every
vertex with minimum total edge weight and contains exactly V-1 edges.

flowchart LR
    G["Weighted Graph"] --> K["Kruskal"]
    G --> P["Prim"]

    K --> S["Sort Edges"]
    S --> U["Union-Find"]
    U --> M["Add edge if no cycle"]

    P --> Q["Priority Queue"]
    Q --> N["Expand cheapest crossing edge"]

Kruskal: O(E log E) with Union-Find.
Prim: commonly O(E log V) with a binary heap.
MST is different from a shortest-path tree: MST minimizes total tree
weight, not distance from a source.

6. Connectivity & Union-Find

flowchart TD
    A["Edge (u,v)"] --> F["Find(u)"]
    A --> G["Find(v)"]
    F --> C{"Same Set?"}
    G --> C
    C -->|"Yes"| X["Cycle in this union"]
    C -->|"No"| U["Union(u,v)"]

Disjoint Set Union (DSU) supports:

find(x)
union(a,b)
Path compression
Union by rank/size

Amortized complexity: approximately O(α(V)) per operation, effectively
constant for practical input sizes.

7. Tree Traversal

flowchart TD
    R["Root"] --> L["Left"]
    R --> X["Right"]
    L --> LL["Left"]
    L --> LR["Right"]
    X --> RL["Left"]
    X --> RR["Right"]

For binary trees:

Preorder: Root → Left → Right
Inorder: Left → Root → Right
Postorder: Left → Right → Root
Level-order: BFS

For a BST, inorder traversal produces keys in sorted order.

8. Advanced Tree Patterns

LCA --- Lowest Common Ancestor

For repeated ancestor queries, binary lifting preprocesses:

up[v][j] = 2^j-th ancestor of v

Typical complexity:

Preprocessing: O(N log N)
Query: O(log N)

flowchart TD
    R["Root"] --> A["A"]
    R --> B["B"]
    A --> C["C"]
    A --> D["D"]
    B --> E["E"]
    B --> F["F"]
    C --> G["G"]
    C --> H["H"]

    G -. "LCA(G,H) = C" .-> H

9. High-Value Advanced Structures

Structure Main Use

BST Ordered search/update
AVL / Red-Black Tree Balanced ordered data
Heap Priority queue / top-K
Trie Prefix/string queries
Segment Tree Range query + update
Fenwick Tree Prefix/range aggregation
B-Tree / B+Tree Database/storage indexes
DAG Dependency modeling

10. DAG & Topological Sort

A DAG (Directed Acyclic Graph) supports dependency ordering.

flowchart LR
    A["Design"] --> B["Implementation"]
    B --> C["Testing"]
    A --> D["API Contract"]
    D --> B
    C --> E["Deployment"]

Topological sorting can be implemented with:

DFS + finishing times.
Kahn's algorithm using indegrees + queue.

If Kahn's algorithm cannot process all V vertices, the directed graph
contains a cycle.

11. Problem-Solving Flow

flowchart TD
    S["Problem"] --> G{"Graph or Tree?"}
    G -->|"Tree"| T{"Need path / levels?"}
    G -->|"Graph"| W{"Weighted?"}

    T -->|"No"| DFS["DFS / Recursion"]
    T -->|"Yes"| BFS["BFS / Level Order"]

    W -->|"No"| U["BFS / DFS / DSU"]
    W -->|"Yes"| N{"Negative Edge?"}

    N -->|"No"| D["Dijkstra / MST"]
    N -->|"Yes"| BF["Bellman-Ford"]

    U --> C{"DAG?"}
    C -->|"Yes"| TOP["Topological Sort"]
    C -->|"No"| CC["Components / Cycle Detection"]

12. Key Mental Models

BFS = minimum hops / levels
DFS = structure / reachability / backtracking
Dijkstra = shortest path with non-negative weights
Bellman-Ford = negative-edge support
Kruskal/Prim = minimum total connection cost
DSU = dynamic connectivity
Topological sort = dependency ordering
LCA = ancestor relationship
Trie = prefix structure
Segment Tree = range aggregation with updates

The main skill is not memorizing algorithms. Identify the graph
property first: direction, weight, cycles, connectivity, dependency,
or query/update pattern. Then select the algorithm whose invariant
matches that property.