Graph Algorithms

A graph is a data structure consisting of a set of vertices (or nodes) and a set of edges connecting these vertices. Graphs are used to model relationships between objects and are fundamental in computer science.

Graph Representation

The choice of representation is crucial for efficiency.

Adjacency Matrix: An M x M matrix where matrix[i][j] = 1 if there is an edge from vertex i to j. Uses O(M²) space. Fast for checking edges (O(1)), slow for iterating neighbors (O(M)). Best for dense graphs.
Adjacency List: An array of lists. adj[i] contains a list of neighbors for vertex i. Uses O(M + E) space. This is the most common representation.

Graph Traversal

Traversal is the process of visiting every node and edge in a graph. The two main algorithms are Breadth-First Search (BFS) and Depth-First Search (DFS).

Breadth-First Search (BFS): Explores the graph layer by layer from a source node. It uses a Queue. BFS is guaranteed to find the shortest path in an unweighted graph.
Depth-First Search (DFS): Explores by going as deep as possible down one path before backtracking. It uses a Stack (often implicitly via recursion). DFS is used for cycle detection, topological sorting, and finding connected components.

Interactive Demo

To see how these traversal algorithms work, check out the interactive simulation below. You can visualize both BFS and DFS step-by-step and see how the underlying data structure (Queue vs. Stack) changes during the traversal.

Interactive Graph Traversal

Visualize Breadth-First Search (BFS) and Depth-First Search (DFS) on a sample graph.

Data Structure (Stack)

Traversal Path

Select a traversal method to begin.