What is a Graph?

A graph is a non-linear data structure consisting of nodes (vertices) and edges connecting these nodes. Think of it as a network of interconnected points, like social networks, road maps, or web pages linked together.

Real-world Analogy

Imagine a social network like Facebook. Each person is a vertex, and friendships are edges connecting them. You can navigate from one friend to another through mutual connections - that's graph traversal in action!

Key Characteristics

Directed vs Undirected

Directed graphs have edges with direction (like one-way streets), while undirected graphs have bidirectional edges (like two-way roads).

Weighted vs Unweighted

Edges can have weights representing cost, distance, or capacity. Unweighted graphs treat all edges equally.

Cyclic vs Acyclic

Cyclic graphs contain cycles (paths that start and end at same vertex), while acyclic graphs have no cycles (like trees).

Connected vs Disconnected

Connected graphs have paths between all vertex pairs, while disconnected graphs have isolated components.

Graph Representations

Adjacency Matrix

2D array where matrix[i][j] = 1 if edge exists between i and j.
Space: O(V²)

Adjacency List

Array of lists where each vertex has list of its neighbors.
Space: O(V+E)

Edge List

Simple list of edges (u, v, weight).
Space: O(E)

Interactive Graph Visualization

Create vertices and edges, then visualize BFS, DFS, and other algorithms. Experiment with directed/undirected and weighted/unweighted graphs.

Graph Algorithm Visualizer

Loading interactive visualization...

Common Graph Algorithms

Algorithm	Time Complexity	Purpose	Use Case
BFS	O(V+E)	Level-order traversal, shortest path (unweighted)	Social network degrees, web crawling
DFS	O(V+E)	Path finding, cycle detection, topological sort	Maze solving, dependency resolution
Dijkstra	O(E log V)	Shortest path (weighted, no negative edges)	GPS navigation, network routing
Kruskal	O(E log V)	Minimum Spanning Tree (MST)	Network design, clustering
Prim	O(E log V)	Minimum Spanning Tree (MST)	Network cabling, approximation algorithms
Topological Sort	O(V+E)	Linear ordering of vertices in DAG	Task scheduling, build systems

Space Complexity: Typically O(V) for most graph algorithms

Code Examples

# Adjacency List Implementation
from collections import defaultdict, deque

class Graph:
    def __init__(self):
        self.graph = defaultdict(list)
    
    def add_edge(self, u, v, directed=False):
        self.graph[u].append(v)
        if not directed:
            self.graph[v].append(u)
    
    def bfs(self, start):
        visited = set()
        queue = deque([start])
        visited.add(start)
        
        while queue:
            vertex = queue.popleft()
            print(vertex, end=" ")
            
            for neighbor in self.graph[vertex]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
    
    def dfs(self, start):
        visited = set()
        stack = [start]
        
        while stack:
            vertex = stack.pop()
            if vertex not in visited:
                print(vertex, end=" ")
                visited.add(vertex)
                stack.extend(self.graph[vertex])

# Usage
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 3)

print("BFS starting from vertex 0:")
g.bfs(0)  # Output: 0 1 2 3

Common Mistakes to Avoid

Forgetting to Track Visited Nodes

In graph traversal (BFS/DFS), always maintain a visited set to avoid infinite loops and reprocessing nodes.

Choosing Wrong Data Structure

Using adjacency matrix for sparse graphs wastes space. Use adjacency lists for graphs where E << V².

Assuming Graph is Connected

Always consider disconnected graphs. You may need to run BFS/DFS from multiple starting points to cover all components.

Using DFS for Shortest Path

DFS doesn't guarantee shortest path in unweighted graphs. Use BFS for unweighted graphs and Dijkstra for weighted graphs.

Interview Patterns

Graph Traversal

BFS for level-order problems, shortest path (unweighted). DFS for path existence, cycle detection, backtracking problems.

Union-Find (Disjoint Set)

Detect cycles in undirected graphs, connected components, Kruskal's MST algorithm. Great for dynamic connectivity problems.

Topological Sort

Course scheduling, build system dependencies, task ordering. Works only on Directed Acyclic Graphs (DAGs).

Shortest Path Algorithms

BFS for unweighted, Dijkstra for non-negative weights, Bellman-Ford for negative weights, A* for heuristic search.

Real-world Applications

Social Networks

Friend suggestions (BFS degrees), community detection, influence propagation, shortest connection path.

Navigation Systems

GPS routing (Dijkstra, A*), traffic optimization, public transportation planning, delivery logistics.

Web Crawling

BFS for systematic crawling, PageRank algorithm, link analysis, sitemap generation.

Network Design

Minimum spanning trees (Kruskal, Prim) for network cables, internet backbone design, circuit layout.

Test Your Knowledge

Graphs Quiz

Question 1 of 5

What is the main difference between BFS and DFS?