Graphs

A graph is a non-linear data structure consisting of nodes (vertices) and edges that connect them. Graphs are fundamental in computer science, modeling relationships in social networks, transportation systems, computer networks, and countless other applications.

Interactive Graph Visualization

Explore graph traversal algorithms with our interactive visualizer. Create custom graphs, drag nodes around, and watch BFS and DFS algorithms traverse the graph step-by-step with color-coded animations.

Graph Operations & Traversal Algorithms

Add Node

Create a new vertex

Add Edge

Connect two vertices

Graph Traversal

Animate traversal algorithms

Animation Speed: 800ms

Interactive Graph Visualization

Default

Current

In Queue (BFS)

In Stack (DFS)

Backtracking

Visited

Drag nodes to reposition • Click to deselect • 4 nodes, 3 edges

Graph Traversal Algorithms

Breadth-First Search (BFS):

Explores all neighbors at the current depth before moving to nodes at the next depth level. Uses a queue data structure and guarantees the shortest path in unweighted graphs.

Time: O(V + E), Space: O(V)

Depth-First Search (DFS):

Explores as far as possible along each branch before backtracking. Uses recursion (or stack) and is useful for detecting cycles and finding connected components.

Time: O(V + E), Space: O(V)

Graph Fundamentals

Core Components

• Vertices (Nodes): Individual entities in the graph
• Edges (Links): Connections between vertices
• Degree: Number of edges connected to a vertex
• Path: Sequence of vertices connected by edges
• Cycle: Path that starts and ends at the same vertex

Graph Properties

• Connected: Path exists between any two vertices
• Sparse vs Dense: Few edges vs many edges
• Planar: Can be drawn without edge crossings
• Bipartite: Vertices can be divided into two disjoint sets
• Complete: Every vertex connected to every other vertex

Types of Graphs

Directed vs Undirected

Directed: Edges have direction (A → B)

Undirected: Edges are bidirectional (A ↔ B)

Weighted vs Unweighted

Weighted: Edges have associated costs/distances

Unweighted: All edges have equal value

Cyclic vs Acyclic

Cyclic: Contains at least one cycle

Acyclic: No cycles (e.g., trees, DAGs)

Connected vs Disconnected

Connected: Path exists between all vertices

Disconnected: Some vertices are unreachable

Graph Representation Methods

Adjacency Matrix

2D array where matrix[i][j] represents edge from vertex i to vertex j


   A B C

A [0 1 1]

B [1 0 1]

C [1 1 0]

• Space: O(V²) - always uses V² space
• Edge Check: O(1) - direct array access
• Add Edge: O(1) - set matrix value
• Get Neighbors: O(V) - scan entire row
• Best for: Dense graphs, frequent edge queries

Adjacency List ⭐

Array/Map of lists where each vertex stores its neighbors


A: [B, C]

B: [A, C]

C: [A, B]

• Space: O(V + E) - only stores existing edges
• Edge Check: O(degree) - search neighbor list
• Add Edge: O(1) - append to list
• Get Neighbors: O(degree) - return list
• Best for: Sparse graphs, traversal algorithms

💡 Recommendation: Adjacency List is often more efficient for sparse graphs (few edges relative to vertices), which describes most real-world graphs. It's the preferred choice for traversal algorithms like BFS and DFS.

Graph Traversal Algorithms

Breadth-First Search (BFS)

Algorithm:

Start with a queue containing the start vertex
Mark the start vertex as visited
While queue is not empty:
• Dequeue a vertex and process it
• Add all unvisited neighbors to queue
• Mark neighbors as visited

Time Complexity: O(V + E)

Space Complexity: O(V) for queue and visited set

Properties: Explores level by level, finds shortest path in unweighted graphs

Applications: Shortest path, social networks, web crawling

Depth-First Search (DFS)

Algorithm:

Start with a stack containing the start vertex
While stack is not empty:
• Pop a vertex from stack
• If not visited, mark as visited and process
• Add all unvisited neighbors to stack
Alternative: Use recursion (implicit stack)

Time Complexity: O(V + E)

Space Complexity: O(V) for stack and visited set

Properties: Explores as deep as possible before backtracking

Applications: Cycle detection, topological sorting, maze solving

Operation Complexity Analysis

Operation	Adjacency Matrix	Adjacency List	Notes
Space	O(V²)	O(V + E)	List is better for sparse graphs
Add Vertex	O(V²)	O(1)	Matrix needs resizing
Add Edge	O(1)	O(1)	Both constant time
Check Edge	O(1)	O(degree)	Matrix has direct access
Get Neighbors	O(V)	O(degree)	List stores only actual neighbors
BFS/DFS	O(V²)	O(V + E)	List avoids checking non-edges

Graph Implementation & Traversal Algorithms

Complete graph implementations using adjacency lists with both BFS and DFS traversal algorithms. Study how the queue in BFS enables level-order traversal while the stack in DFS enables deep exploration.

 from collections import defaultdict, deque

class Graph:
    """
    Graph implementation using Adjacency List representation
    Supports both directed and undirected graphs
    """
    
    def __init__(self, directed=False):
        self.graph = defaultdict(list)  # Adjacency list
        self.directed = directed
        self.vertices = set()
    
    def add_vertex(self, vertex):
        """Add a vertex to the graph"""
        self.vertices.add(vertex)
        if vertex not in self.graph:
            self.graph[vertex] = []
    
    def add_edge(self, u, v, weight=1):
        """
        Add an edge between vertices u and v
        For undirected graphs, add edge in both directions
        """
        self.vertices.add(u)
        self.vertices.add(v)
        
        # Add edge from u to v
        self.graph[u].append((v, weight))
        
        # For undirected graphs, add reverse edge
        if not self.directed:
            self.graph[v].append((u, weight))
    
    def get_neighbors(self, vertex):
        """Get all neighbors of a vertex"""
        return [neighbor for neighbor, weight in self.graph[vertex]]
    
    def print_graph(self):
        """Print the adjacency list representation"""
        for vertex in self.vertices:
            neighbors = self.get_neighbors(vertex)
            print(f"{vertex}: {neighbors}")
    
    def bfs(self, start_vertex):
        """
        Breadth-First Search traversal
        Time Complexity: O(V + E)
        Space Complexity: O(V)
        """
        if start_vertex not in self.vertices:
            return []
        
        visited = set()
        queue = deque([start_vertex])
        traversal_order = []
        
        visited.add(start_vertex)
        
        while queue:
            # Dequeue a vertex from front of queue
            current = queue.popleft()
            traversal_order.append(current)
            
            # Visit all unvisited neighbors
            for neighbor in self.get_neighbors(current):
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
        
        return traversal_order
    
    def dfs(self, start_vertex):
        """
        Depth-First Search traversal (iterative)
        Time Complexity: O(V + E)
        Space Complexity: O(V)
        """
        if start_vertex not in self.vertices:
            return []
        
        visited = set()
        stack = [start_vertex]
        traversal_order = []
        
        while stack:
            # Pop a vertex from top of stack
            current = stack.pop()
            
            if current not in visited:
                visited.add(current)
                traversal_order.append(current)
                
                # Add all unvisited neighbors to stack
                # Add in reverse order to maintain left-to-right traversal
                neighbors = self.get_neighbors(current)
                for neighbor in reversed(neighbors):
                    if neighbor not in visited:
                        stack.append(neighbor)
        
        return traversal_order
    
    def dfs_recursive(self, start_vertex, visited=None):
        """
        Depth-First Search traversal (recursive)
        Time Complexity: O(V + E)
        Space Complexity: O(V) - due to recursion stack
        """
        if visited is None:
            visited = set()
        
        if start_vertex not in self.vertices:
            return []
        
        visited.add(start_vertex)
        traversal_order = [start_vertex]
        
        # Visit all unvisited neighbors recursively
        for neighbor in self.get_neighbors(start_vertex):
            if neighbor not in visited:
                traversal_order.extend(
                    self.dfs_recursive(neighbor, visited)
                )
        
        return traversal_order

# Example usage and testing
if __name__ == "__main__":
    # Create an undirected graph
    g = Graph(directed=False)
    
    # Add vertices and edges
    g.add_edge('A', 'B')
    g.add_edge('A', 'C')
    g.add_edge('B', 'D')
    g.add_edge('C', 'E')
    g.add_edge('D', 'E')
    g.add_edge('E', 'F')
    
    print("Graph representation:")
    g.print_graph()
    
    print(f"\nBFS from A: {g.bfs('A')}")
    print(f"DFS from A: {g.dfs('A')}")
    print(f"DFS Recursive from A: {g.dfs_recursive('A')}") 
 import java.util.*;

/**
 * Graph implementation using Adjacency List representation
 * Supports both directed and undirected graphs
 */
public class Graph {
    private Map<String, List<Edge>> adjacencyList;
    private boolean directed;
    private Set<String> vertices;
    
    /**
     * Edge class to represent weighted edges
     */
    static class Edge {
        String destination;
        int weight;
        
        public Edge(String destination, int weight) {
            this.destination = destination;
            this.weight = weight;
        }
        
        public Edge(String destination) {
            this(destination, 1);
        }
    }
    
    /**
     * Constructor
     * @param directed true for directed graph, false for undirected
     */
    public Graph(boolean directed) {
        this.adjacencyList = new HashMap<>();
        this.directed = directed;
        this.vertices = new HashSet<>();
    }
    
    /**
     * Add a vertex to the graph
     */
    public void addVertex(String vertex) {
        vertices.add(vertex);
        adjacencyList.putIfAbsent(vertex, new ArrayList<>());
    }
    
    /**
     * Add an edge between two vertices
     * @param source source vertex
     * @param destination destination vertex
     * @param weight edge weight (default 1)
     */
    public void addEdge(String source, String destination, int weight) {
        addVertex(source);
        addVertex(destination);
        
        // Add edge from source to destination
        adjacencyList.get(source).add(new Edge(destination, weight));
        
        // For undirected graphs, add reverse edge
        if (!directed) {
            adjacencyList.get(destination).add(new Edge(source, weight));
        }
    }
    
    public void addEdge(String source, String destination) {
        addEdge(source, destination, 1);
    }
    
    /**
     * Get neighbors of a vertex
     */
    public List<String> getNeighbors(String vertex) {
        List<String> neighbors = new ArrayList<>();
        if (adjacencyList.containsKey(vertex)) {
            for (Edge edge : adjacencyList.get(vertex)) {
                neighbors.add(edge.destination);
            }
        }
        return neighbors;
    }
    
    /**
     * Print the graph's adjacency list representation
     */
    public void printGraph() {
        for (String vertex : vertices) {
            System.out.print(vertex + ": ");
            List<String> neighbors = getNeighbors(vertex);
            System.out.println(neighbors);
        }
    }
    
    /**
     * Breadth-First Search traversal
     * Time Complexity: O(V + E)
     * Space Complexity: O(V)
     */
    public List<String> bfs(String startVertex) {
        if (!vertices.contains(startVertex)) {
            return new ArrayList<>();
        }
        
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        List<String> traversalOrder = new ArrayList<>();
        
        queue.offer(startVertex);
        visited.add(startVertex);
        
        while (!queue.isEmpty()) {
            String current = queue.poll();
            traversalOrder.add(current);
            
            // Visit all unvisited neighbors
            for (String neighbor : getNeighbors(current)) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
        
        return traversalOrder;
    }
    
    /**
     * Depth-First Search traversal (iterative)
     * Time Complexity: O(V + E)
     * Space Complexity: O(V)
     */
    public List<String> dfs(String startVertex) {
        if (!vertices.contains(startVertex)) {
            return new ArrayList<>();
        }
        
        Set<String> visited = new HashSet<>();
        Stack<String> stack = new Stack<>();
        List<String> traversalOrder = new ArrayList<>();
        
        stack.push(startVertex);
        
        while (!stack.isEmpty()) {
            String current = stack.pop();
            
            if (!visited.contains(current)) {
                visited.add(current);
                traversalOrder.add(current);
                
                // Add neighbors to stack in reverse order
                List<String> neighbors = getNeighbors(current);
                for (int i = neighbors.size() - 1; i >= 0; i--) {
                    String neighbor = neighbors.get(i);
                    if (!visited.contains(neighbor)) {
                        stack.push(neighbor);
                    }
                }
            }
        }
        
        return traversalOrder;
    }
    
    /**
     * Depth-First Search traversal (recursive)
     * Time Complexity: O(V + E)
     * Space Complexity: O(V) - due to recursion stack
     */
    public List<String> dfsRecursive(String startVertex) {
        Set<String> visited = new HashSet<>();
        List<String> traversalOrder = new ArrayList<>();
        dfsRecursiveHelper(startVertex, visited, traversalOrder);
        return traversalOrder;
    }
    
    private void dfsRecursiveHelper(String vertex, Set<String> visited, 
                                   List<String> traversalOrder) {
        if (!vertices.contains(vertex) || visited.contains(vertex)) {
            return;
        }
        
        visited.add(vertex);
        traversalOrder.add(vertex);
        
        // Visit all unvisited neighbors recursively
        for (String neighbor : getNeighbors(vertex)) {
            if (!visited.contains(neighbor)) {
                dfsRecursiveHelper(neighbor, visited, traversalOrder);
            }
        }
    }
    
    // Example usage
    public static void main(String[] args) {
        Graph g = new Graph(false); // Undirected graph
        
        // Add edges
        g.addEdge("A", "B");
        g.addEdge("A", "C");
        g.addEdge("B", "D");
        g.addEdge("C", "E");
        g.addEdge("D", "E");
        g.addEdge("E", "F");
        
        System.out.println("Graph representation:");
        g.printGraph();
        
        System.out.println("\nBFS from A: " + g.bfs("A"));
        System.out.println("DFS from A: " + g.dfs("A"));
        System.out.println("DFS Recursive from A: " + g.dfsRecursive("A"));
    }
} 
 #include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

/**
 * Graph implementation using Adjacency List representation
 * Supports both directed and undirected graphs
 */
class Graph {
private:
    unordered_map<string, vector<pair<string, int>>> adjacencyList;
    bool directed;
    unordered_set<string> vertices;
    
public:
    /**
     * Constructor
     * @param directed true for directed graph, false for undirected
     */
    Graph(bool directed = false) : directed(directed) {}
    
    /**
     * Add a vertex to the graph
     */
    void addVertex(const string& vertex) {
        vertices.insert(vertex);
        if (adjacencyList.find(vertex) == adjacencyList.end()) {
            adjacencyList[vertex] = vector<pair<string, int>>();
        }
    }
    
    /**
     * Add an edge between two vertices
     * @param source source vertex
     * @param destination destination vertex
     * @param weight edge weight (default 1)
     */
    void addEdge(const string& source, const string& destination, int weight = 1) {
        addVertex(source);
        addVertex(destination);
        
        // Add edge from source to destination
        adjacencyList[source].push_back({destination, weight});
        
        // For undirected graphs, add reverse edge
        if (!directed) {
            adjacencyList[destination].push_back({source, weight});
        }
    }
    
    /**
     * Get neighbors of a vertex
     */
    vector<string> getNeighbors(const string& vertex) {
        vector<string> neighbors;
        if (adjacencyList.find(vertex) != adjacencyList.end()) {
            for (const auto& edge : adjacencyList[vertex]) {
                neighbors.push_back(edge.first);
            }
        }
        return neighbors;
    }
    
    /**
     * Print the graph's adjacency list representation
     */
    void printGraph() {
        for (const string& vertex : vertices) {
            cout << vertex << ": ";
            vector<string> neighbors = getNeighbors(vertex);
            cout << "[";
            for (size_t i = 0; i < neighbors.size(); ++i) {
                cout << neighbors[i];
                if (i < neighbors.size() - 1) cout << ", ";
            }
            cout << "]" << endl;
        }
    }
    
    /**
     * Breadth-First Search traversal
     * Time Complexity: O(V + E)
     * Space Complexity: O(V)
     */
    vector<string> bfs(const string& startVertex) {
        if (vertices.find(startVertex) == vertices.end()) {
            return vector<string>();
        }
        
        unordered_set<string> visited;
        queue<string> q;
        vector<string> traversalOrder;
        
        q.push(startVertex);
        visited.insert(startVertex);
        
        while (!q.empty()) {
            string current = q.front();
            q.pop();
            traversalOrder.push_back(current);
            
            // Visit all unvisited neighbors
            vector<string> neighbors = getNeighbors(current);
            for (const string& neighbor : neighbors) {
                if (visited.find(neighbor) == visited.end()) {
                    visited.insert(neighbor);
                    q.push(neighbor);
                }
            }
        }
        
        return traversalOrder;
    }
    
    /**
     * Depth-First Search traversal (iterative)
     * Time Complexity: O(V + E)
     * Space Complexity: O(V)
     */
    vector<string> dfs(const string& startVertex) {
        if (vertices.find(startVertex) == vertices.end()) {
            return vector<string>();
        }
        
        unordered_set<string> visited;
        stack<string> stk;
        vector<string> traversalOrder;
        
        stk.push(startVertex);
        
        while (!stk.empty()) {
            string current = stk.top();
            stk.pop();
            
            if (visited.find(current) == visited.end()) {
                visited.insert(current);
                traversalOrder.push_back(current);
                
                // Add neighbors to stack in reverse order
                vector<string> neighbors = getNeighbors(current);
                reverse(neighbors.begin(), neighbors.end());
                for (const string& neighbor : neighbors) {
                    if (visited.find(neighbor) == visited.end()) {
                        stk.push(neighbor);
                    }
                }
            }
        }
        
        return traversalOrder;
    }
    
    /**
     * Depth-First Search traversal (recursive)
     * Time Complexity: O(V + E)
     * Space Complexity: O(V) - due to recursion stack
     */
    vector<string> dfsRecursive(const string& startVertex) {
        unordered_set<string> visited;
        vector<string> traversalOrder;
        dfsRecursiveHelper(startVertex, visited, traversalOrder);
        return traversalOrder;
    }
    
private:
    void dfsRecursiveHelper(const string& vertex, 
                           unordered_set<string>& visited,
                           vector<string>& traversalOrder) {
        if (vertices.find(vertex) == vertices.end() || 
            visited.find(vertex) != visited.end()) {
            return;
        }
        
        visited.insert(vertex);
        traversalOrder.push_back(vertex);
        
        // Visit all unvisited neighbors recursively
        vector<string> neighbors = getNeighbors(vertex);
        for (const string& neighbor : neighbors) {
            if (visited.find(neighbor) == visited.end()) {
                dfsRecursiveHelper(neighbor, visited, traversalOrder);
            }
        }
    }
};

// Example usage
int main() {
    Graph g(false); // Undirected graph
    
    // Add edges
    g.addEdge("A", "B");
    g.addEdge("A", "C");
    g.addEdge("B", "D");
    g.addEdge("C", "E");
    g.addEdge("D", "E");
    g.addEdge("E", "F");
    
    cout << "Graph representation:" << endl;
    g.printGraph();
    
    cout << "\nBFS from A: ";
    vector<string> bfsResult = g.bfs("A");
    for (size_t i = 0; i < bfsResult.size(); ++i) {
        cout << bfsResult[i];
        if (i < bfsResult.size() - 1) cout << " -> ";
    }
    cout << endl;
    
    cout << "DFS from A: ";
    vector<string> dfsResult = g.dfs("A");
    for (size_t i = 0; i < dfsResult.size(); ++i) {
        cout << dfsResult[i];
        if (i < dfsResult.size() - 1) cout << " -> ";
    }
    cout << endl;
    
    cout << "DFS Recursive from A: ";
    vector<string> dfsRecResult = g.dfsRecursive("A");
    for (size_t i = 0; i < dfsRecResult.size(); ++i) {
        cout << dfsRecResult[i];
        if (i < dfsRecResult.size() - 1) cout << " -> ";
    }
    cout << endl;
    
    return 0;
} 

Real-World Applications

Social Networks

Model friendships, connections, and information spread. BFS finds shortest social distance.

Transportation

GPS navigation, flight routes, public transit. Weighted graphs represent distances or travel time.

Computer Networks

Internet topology, routing protocols, network analysis. DFS detects network loops.

Web Crawling

Search engines use BFS to discover web pages level by level from seed URLs.

Game Development

Pathfinding in games, decision trees, state machines. A* algorithm extends BFS.

Dependency Resolution

Package managers, build systems, task scheduling. DFS enables topological sorting.

Advanced Graph Algorithms

• Dijkstra's Algorithm: Shortest path in weighted graphs

• Minimum Spanning Tree: Kruskal's and Prim's algorithms

• Topological Sort: Ordering vertices in directed acyclic graphs

• Strongly Connected Components: Finding cycles in directed graphs

• Maximum Flow: Ford-Fulkerson algorithm for network flow problems