Graph-Algorithms

Graph Traversals (BFS, DFS)

Content

Graph-Traversal
- BFS
- DFS
Shortest Path Algorithms
- Dijkstra’s Algorithm
- Bellman–Ford Algorithm
- Floyd–Warshall Algorithm
- A* Search
Minimum Spanning Tree Algorithms
- Prim’s Algorithm
- Kruskal’s Algorithm
Other Graph Problems
- Topological Sort (DAGs)
- Connectivity (Union-Find / DSU)
- Cycle Detection

Documentation | Guide & Areas of Study

The following two are the most commonly used representations of a graph:

Adjacency Matrix
Adjacency List
Incidence Matrix
Incidence List

Adjacency Matrix

Adjacency Matrix

Adjacency matrix WIKI

Adjacency Matrix is a 2D array of size V x V where V is the number of vertices in a graph. Adjacency matrix for undirected graph is always symmetric.

Graph node represented with adj
Edge = adj[i][j] = 1 | Edge / Path from i to j.
Weigthted Graph = adj[i][j] = w (n)

Graph = [
    [0, 1, 0, 0, 1],  # Node 1
    [1, 0, 1, 1, 1],  # Node 2
    [0, 1, 0, 1, 0],  # Node 3
    [0, 1, 1, 0, 1],  # Node 4
    [1, 1, 0, 1, 0],  # Node 5
    # 1  2  3  4  5
]

Adjacency List
Adjacency list WIKI

adjacency list is a collection of unordered lists used to represent a finite graph.

graph = {
    'A': {'B', 'C'},
    'B': {'A', 'D', 'E'},
    'C': {'A', 'F'},
    'D': {'B'},
    'E': {'B', 'F'},
    'F': {'C', 'E'}
}

Spanning Tree & Minimum Spanning Tree

Undirected graph

The edges do not point in any direction (ie. the edges are bidirectional), hence if there is a path between V a and V b you can go (a, b) or reverse (b, a).

Connected graph

Paths are one direction, V a and V b, if only path (a, b) is set then you can't go (b, a).

Spanning tree

A spanning tree is a sub-graph of an undirected or connected graph, which includes all the vertices of the graph with a minimum possible number of edges.

If a vertex is missed, then it is not a spanning tree.

The edges may or may not have weights assigned to them.

The total number of spanning trees with n vertices that can be created from a complete graph is equal to n(n-2).

If we have n = 4, the maximum number of possible spanning trees is equal to 44-2 = 16. Thus, 16 spanning trees can be formed from a complete graph with 4 vertices.

Minimum Spanning Tree

A minimum spanning tree is a spanning tree in which the sum of the weight of the edges is as minimum as possible.

Prim's Algorithm
Kruskal's Algorithm
Dijkstra's Algorithm

1. Understand What a Graph Is

✅ Order of study:

Representation → Adjacency list vs matrix
Traversals → DFS, BFS
Shortest path → BFS (unweighted), Dijkstra (weighted)
MST → Kruskal, Prim
Topological sort & SCC
Network flow & advanced stuff

A graph is made of:

Vertices (nodes) → the “things”
Edges (links) → the “relationships”

👉 Graphs can be:

Directed vs *Undirected
Weighted (edge has a cost) vs Unweighted
Sparse (few edges) vs Dense (many edges)
Can contain cycles or be acyclic

Start by learning representations:

Adjacency List → efficient for sparse graphs
Adjacency Matrix → easy but heavy on memory

2. Basic Traversals

Before anything else, master how to “walk” a graph:

DFS (Depth First Search) → go as deep as possible first
BFS (Breadth First Search) → visit neighbours level by level

👉 These form the foundation for almost everything else.
Practice detecting:

Reachability (is node A connected to node B?)
Connected components
Cycle detection (directed vs undirected)

3. Shortest Path Algorithms

After traversals, move to paths:

Unweighted graphs → BFS finds shortest path
Weighted graphs:
- Dijkstra’s Algorithm → non-negative weights
- Bellman–Ford → handles negative weights
- Floyd–Warshall → all-pairs shortest paths
- A* → heuristic-based (used in GPS, games)

4. Minimum Spanning Trees (MST)

For connecting all nodes with minimal cost:

Kruskal’s Algorithm
Prim’s Algorithm

5. Advanced Topics

Topological Sort (ordering tasks with dependencies)
Strongly Connected Components (Tarjan’s or Kosaraju’s)
Network Flow / Max Flow (Ford-Fulkerson, Edmonds-Karp) → scheduling, matching problems
Graph coloring, bipartite graphs
Union-Find (Disjoint Set Union - DSU) → useful for Kruskal’s, connectivity checks

Terms & Keywords

Graph theory
Bipartite graph
Set or ordered Pair (u, v) != (v, u)
directed graph | di-graph
weight | value | cost | Distance
Sparse Graph (containing less n of Edges)
Undirected Graph WIKI
Directed graphs

Algorithms

alpha–beta pruning

alpha–beta pruning

A* algorithm

A* algorithm

The A* algorithm is a generalization of Dijkstra's algorithm that cuts down on the size of the subgraph that must be explored,

B*

Backtracking

Backtracking

Beam search

Beam search

Bellman–Ford algorithm

Unlike Dijkstra's algorithm, the Bellman–Ford algorithm can be used on graphs with negative edge weights, as long as the graph contains no negative cycle reachable from the source vertex s.