Graphs: Representation, DFS & BFS

Links To Code:

// Graphs - Edge List, Adjacency Matrix, Adjacency List, DFS, BFS - Greg Hogg DSA Course Materials Lecture 11

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <unordered_map>
#include <unordered_set>

// Build Adjacency Matrix
std::vector<std::vector<int>> buildAdjacencyMatrix(int n, const std::vector<std::pair<int, int>>& edges) {
    std::vector<std::vector<int>> matrix(n, std::vector<int>(n, 0));
    for (const auto& edge : edges) {
        matrix[edge.first][edge.second] = 1;
    }
    return matrix;
}

// Build Adjacency List
std::unordered_map<int, std::vector<int>> buildAdjacencyList(const std::vector<std::pair<int, int>>& edges) {
    std::unordered_map<int, std::vector<int>> adjList;
    for (const auto& edge : edges) {
        adjList[edge.first].push_back(edge.second);
    }
    return adjList;
}

// Recursive DFS
void dfsRecursive(int node, const std::unordered_map<int, std::vector<int>>& adjList, std::unordered_set<int>& seen) {
    if (seen.count(node)) return;
    seen.insert(node);
    std::cout << node << " ";
    if (adjList.find(node) != adjList.end()) {
        for (int neighbor : adjList.at(node)) {
            dfsRecursive(neighbor, adjList, seen);
        }
    }
}

// Iterative DFS
void dfsIterative(int startNode, const std::unordered_map<int, std::vector<int>>& adjList) {
    std::unordered_set<int> seen;
    std::stack<int> stack;
    stack.push(startNode);
    seen.insert(startNode);

    while (!stack.empty()) {
        int node = stack.top();
        stack.pop();
        std::cout << node << " ";
        if (adjList.find(node) != adjList.end()) {
            for (int neighbor : adjList.at(node)) {
                if (!seen.count(neighbor)) {
                    seen.insert(neighbor);
                    stack.push(neighbor);
                }
            }
        }
    }
}

// BFS
void bfs(int startNode, const std::unordered_map<int, std::vector<int>>& adjList) {
    std::unordered_set<int> seen;
    std::queue<int> queue;
    queue.push(startNode);
    seen.insert(startNode);

    while (!queue.empty()) {
        int node = queue.front();
        queue.pop();
        std::cout << node << " ";
        if (adjList.find(node) != adjList.end()) {
            for (int neighbor : adjList.at(node)) {
                if (!seen.count(neighbor)) {
                    seen.insert(neighbor);
                    queue.push(neighbor);
                }
            }
        }
    }
}

// Print Matrix
void printMatrix(const std::vector<std::vector<int>>& matrix) {
    for (const auto& row : matrix) {
        for (int val : row) {
            std::cout << val << " ";
        }
        std::cout << std::endl;
    }
}

// Print Adjacency List
void printAdjacencyList(const std::unordered_map<int, std::vector<int>>& adjList) {
    for (const auto& entry : adjList) {
        std::cout << entry.first << " -> ";
        for (int neighbor : entry.second) {
            std::cout << neighbor << " ";
        }
        std::cout << std::endl;
    }
}

int main() {
    int n = 8;
    std::vector<std::pair<int, int>> edges = {{0, 1}, {1, 2}, {0, 3}, {3, 4}, {3, 6}, {3, 7}, {4, 2}, {4, 5}, {5, 2}};

    // Convert Array of Edges -> Adjacency Matrix
    auto adjacencyMatrix = buildAdjacencyMatrix(n, edges);
    std::cout << "Adjacency Matrix:" << std::endl;
    printMatrix(adjacencyMatrix);

    // Convert Array of Edges -> Adjacency List
    auto adjacencyList = buildAdjacencyList(edges);
    std::cout << "Adjacency List:" << std::endl;
    printAdjacencyList(adjacencyList);

    // Depth First Search (DFS) - Recursive
    std::cout << "DFS Recursive:" << std::endl;
    std::unordered_set<int> seen;
    dfsRecursive(0, adjacencyList, seen);
    std::cout << std::endl;

    // Depth First Search (DFS) - Iterative
    std::cout << "DFS Iterative:" << std::endl;
    dfsIterative(0, adjacencyList);
    std::cout << std::endl;

    // Breadth First Search (BFS)
    std::cout << "BFS:" << std::endl;
    bfs(0, adjacencyList);
    std::cout << std::endl;

    return 0;
}

// Graphs - Edge List, Adjacency Matrix, Adjacency List, DFS, BFS - Greg Hogg DSA Course Materials Lecture 11

// Graph Representation & Traversal
import java.util.*;

public class Main {
    public static void main(String[] args) {
        int n = 8;
        int[][] edges = {{0, 1}, {1, 2}, {0, 3}, {3, 4}, {3, 6}, {3, 7}, {4, 2}, {4, 5}, {5, 2}};

        // Convert Array of Edges -> Adjacency Matrix
        int[][] adjacencyMatrix = buildAdjacencyMatrix(n, edges);
        System.out.println("Adjacency Matrix:");
        printMatrix(adjacencyMatrix);

        // Convert Array of Edges -> Adjacency List
        Map<Integer, List<Integer>> adjacencyList = buildAdjacencyList(edges);
        System.out.println("Adjacency List:");
        printAdjacencyList(adjacencyList);

        // Depth First Search (DFS) - Recursive
        System.out.println("DFS Recursive:");
        Set<Integer> seen = new HashSet<>();
        dfsRecursive(0, adjacencyList, seen);

        // Depth First Search (DFS) - Iterative
        System.out.println("DFS Iterative:");
        dfsIterative(0, adjacencyList);

        // Breadth First Search (BFS)
        System.out.println("BFS:");
        bfs(0, adjacencyList);
    }

    // Build Adjacency Matrix
    public static int[][] buildAdjacencyMatrix(int n, int[][] edges) {
        int[][] matrix = new int[n][n];
        for (int[] edge : edges) {
            matrix[edge[0]][edge[1]] = 1;
        }
        return matrix;
    }

    // Build Adjacency List
    public static Map<Integer, List<Integer>> buildAdjacencyList(int[][] edges) {
        Map<Integer, List<Integer>> adjList = new HashMap<>();
        for (int[] edge : edges) {
            adjList.putIfAbsent(edge[0], new ArrayList<>());
            adjList.get(edge[0]).add(edge[1]);
        }
        return adjList;
    }

    // Recursive DFS
    public static void dfsRecursive(int node, Map<Integer, List<Integer>> adjList, Set<Integer> seen) {
        if (!seen.contains(node)) {
            seen.add(node);
            System.out.println(node);
            for (int neighbor : adjList.getOrDefault(node, new ArrayList<>())) {
                dfsRecursive(neighbor, adjList, seen);
            }
        }
    }

    // Iterative DFS
    public static void dfsIterative(int startNode, Map<Integer, List<Integer>> adjList) {
        Set<Integer> seen = new HashSet<>();
        Stack<Integer> stack = new Stack<>();
        stack.push(startNode);
        seen.add(startNode);

        while (!stack.isEmpty()) {
            int node = stack.pop();
            System.out.println(node);
            for (int neighbor : adjList.getOrDefault(node, new ArrayList<>())) {
                if (!seen.contains(neighbor)) {
                    seen.add(neighbor);
                    stack.push(neighbor);
                }
            }
        }
    }

    // BFS
    public static void bfs(int startNode, Map<Integer, List<Integer>> adjList) {
        Set<Integer> seen = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(startNode);
        seen.add(startNode);

        while (!queue.isEmpty()) {
            int node = queue.poll();
            System.out.println(node);
            for (int neighbor : adjList.getOrDefault(node, new ArrayList<>())) {
                if (!seen.contains(neighbor)) {
                    seen.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
    }

    // Helper methods to print matrices and adjacency lists
    public static void printMatrix(int[][] matrix) {
        for (int[] row : matrix) {
            System.out.println(Arrays.toString(row));
        }
    }

    public static void printAdjacencyList(Map<Integer, List<Integer>> adjList) {
        for (Map.Entry<Integer, List<Integer>> entry : adjList.entrySet()) {
            System.out.println(entry.getKey() + " -> " + entry.getValue());
        }
    }
}

// Custom Node Class for Graphs:
public class Main {
    String value;
    List<Node> neighbors;

    public Node(String value) {
        this.value = value;
        this.neighbors = new ArrayList<>();
    }

    @Override
    public String toString() {
        return "Node(" + value + ")";
    }

    public String display() {
        List<String> connections = new ArrayList<>();
        for (Node neighbor : neighbors) {
            connections.add(neighbor.value);
        }
        return value + " is connected to: " + connections;
    }

    public static void main(String[] args) {
        Node A = new Node("A");
        Node B = new Node("B");
        Node C = new Node("C");
        Node D = new Node("D");

        A.neighbors.add(B);
        B.neighbors.add(A);
        C.neighbors.add(D);
        D.neighbors.add(C);

        System.out.println(B.display());
    }
}

// Custom Node Class for Graphs
import java.util.*;

public class Main {
    // Node class to represent a graph node
    static class Node {
        String value;
        List<Node> neighbors;

        public Node(String value) {
            this.value = value;
            this.neighbors = new ArrayList<>();
        }

        @Override
        public String toString() {
            return "Node(" + value + ")";
        }

        public String display() {
            List<String> connections = new ArrayList<>();
            for (Node neighbor : neighbors) {
                connections.add(neighbor.value);
            }
            return value + " is connected to: " + connections;
        }
    }

    public static void main(String[] args) {
        Node A = new Node("A");
        Node B = new Node("B");
        Node C = new Node("C");
        Node D = new Node("D");

        A.neighbors.add(B);
        B.neighbors.add(A);
        C.neighbors.add(D);
        D.neighbors.add(C);

        System.out.println(B.display());
    }
}

// Graphs - Edge List, Adjacency Matrix, Adjacency List, DFS, BFS - Greg Hogg DSA Course Materials Lecture 11

// Graph Representation & Traversal

// Convert Array of Edges -> Adjacency Matrix
function buildAdjacencyMatrix(n, edges) {
    let matrix = Array.from({ length: n }, () => Array(n).fill(0));
    edges.forEach(([u, v]) => {
        matrix[u][v] = 1;
    });
    return matrix;
}

// Convert Array of Edges -> Adjacency List
function buildAdjacencyList(edges) {
    let adjList = new Map();
    edges.forEach(([u, v]) => {
        if (!adjList.has(u)) adjList.set(u, []);
        adjList.get(u).push(v);
    });
    return adjList;
}

// Recursive DFS
function dfsRecursive(node, adjList, seen = new Set()) {
    if (!seen.has(node)) {
        seen.add(node);
        console.log(node);
        (adjList.get(node) || []).forEach(neighbor => {
            dfsRecursive(neighbor, adjList, seen);
        });
    }
}

// Iterative DFS
function dfsIterative(startNode, adjList) {
    let seen = new Set();
    let stack = [startNode];
    seen.add(startNode);

while (stack.length) {
        let node = stack.pop();
        console.log(node);
        (adjList.get(node) || []).forEach(neighbor => {
            if (!seen.has(neighbor)) {
                seen.add(neighbor);
                stack.push(neighbor);
            }
        });
    }
}

// BFS
function bfs(startNode, adjList) {
    let seen = new Set();
    let queue = [startNode];
    seen.add(startNode);

while (queue.length) {
        let node = queue.shift();
        console.log(node);
        (adjList.get(node) || []).forEach(neighbor => {
            if (!seen.has(neighbor)) {
                seen.add(neighbor);
                queue.push(neighbor);
            }
        });
    }
}

// Helper methods to print matrices and adjacency lists
function printMatrix(matrix) {
    matrix.forEach(row => console.log(row));
}

function printAdjacencyList(adjList) {
    adjList.forEach((value, key) => {
        console.log(`${key} -> ${value}`);
    });
}

// Example usage
const n = 8;
const edges = [[0, 1], [1, 2], [0, 3], [3, 4], [3, 6], [3, 7], [4, 2], [4, 5], [5, 2]];

const adjacencyMatrix = buildAdjacencyMatrix(n, edges);
console.log("Adjacency Matrix:");
printMatrix(adjacencyMatrix);

const adjacencyList = buildAdjacencyList(edges);
console.log("Adjacency List:");
printAdjacencyList(adjacencyList);

console.log("DFS Recursive:");
dfsRecursive(0, adjacencyList);

console.log("DFS Iterative:");
dfsIterative(0, adjacencyList);

console.log("BFS:");
bfs(0, adjacencyList);

// Custom Node Class for Graphs
class Node {
    constructor(value) {
        this.value = value;
        this.neighbors = [];
    }

toString() {
        return `Node(${this.value})`;
    }

display() {
        let connections = this.neighbors.map(neighbor => neighbor.value);
        return `${this.value} is connected to: ${connections}`;
    }
}

// Example usage for Node Class
let A = new Node("A");
let B = new Node("B");
let C = new Node("C");
let D = new Node("D");

A.neighbors.push(B);
B.neighbors.push(A);
C.neighbors.push(D);
D.neighbors.push(C);

console.log(B.display());

Summary ▼

Graphs are data structures made up of nodes (vertices) and connections (edges). They can be represented using adjacency lists or matrices. Traversal algorithms like DFS (Depth-First Search) and BFS (Breadth-First Search) help explore graph structures efficiently, which is essential in networking, scheduling, and optimization problems.

Graphs: Representation, DFS & BFS

A graph is a collection of nodes (called vertices) connected by edges. Graphs are used to model relationships in a wide range of applications including social networks, maps, web crawlers, and scheduling systems.

Graph Representations

Adjacency Matrix: A 2D array that indicates direct connections between vertices. Efficient for dense graphs, but uses O(n²) space.
Adjacency List: A map where each vertex points to a list of connected vertices. Efficient for sparse graphs and widely used in practice.

Depth-First Search (DFS)

DFS explores a graph by diving deep into each branch before backtracking. It can be implemented recursively or iteratively using a stack. DFS is useful for topological sorting, cycle detection, and connected components.

Breadth-First Search (BFS)

BFS explores neighbors layer by layer using a queue. It’s ideal for finding the shortest path in unweighted graphs and for level-order traversal in trees.

Example Applications

Shortest path finding (e.g., BFS in unweighted graphs)
Cycle detection and topological sort (DFS)
Friend suggestions in social networks
Network routing algorithms

Conclusion

Graphs are a cornerstone of computer science. Understanding their structure and traversal methods opens the door to solving real-world problems involving connectivity, optimization, and flow.

Introduction to Graphs: Structure, Representation, and Traversal

Graphs are a foundational data structure in computer science used to model relationships between elements. A graph is made up of nodes (also called vertices) and edges, which are the connections between these nodes. They are highly versatile and appear in various real-world applications such as transportation networks, social media graphs, and computer networks.

Examples like cities connected by direct flights help illustrate the concept of graphs. Each city is a node, and each direct flight is an edge connecting two nodes. While simple, this visualization captures the essence of what graphs represent: relationships between entities.

Graph Types and Properties

Graphs can be categorized based on how edges behave. In a directed graph, edges have a direction—meaning you can go from node A to node B, but not necessarily from B back to A. These are typically visualized with arrowheads to show direction.

In contrast, undirected graphs allow edges to be traversed in both directions. If node A is connected to node B, then node B is also connected to node A by default.

Another important property of graphs is the presence or absence of cycles. A cycle is a path that starts and ends at the same node. Cycles can make algorithm design more complex, especially in recursive algorithms, due to the potential for infinite loops.

A tree is a special kind of graph. It is connected (you can reach any node from any other) and acyclic (it has no cycles). Trees with V nodes always have exactly V - 1 edges. Linked lists and trees are thus specialized forms of graphs.

How Graphs Are Represented

There are several common ways to represent graphs in a program. The choice of representation can greatly affect the efficiency of graph algorithms.

Edge List

An edge list stores the graph as a list of edge pairs. Each edge is represented as a pair [u, v], indicating a connection from node u to node v. This format is simple and space-efficient, especially for sparse graphs, but it can be inefficient for finding neighbors of a specific node.

Adjacency Matrix

An adjacency matrix is a two-dimensional array of size N × N, where N is the number of nodes. Each entry matrix[i][j] is set to 1 if there's an edge from node i to node j, and 0 otherwise.

This format is good for quickly checking whether an edge exists between two nodes, but it consumes a lot of memory and is inefficient for sparse graphs. For undirected graphs, the matrix is symmetric: both matrix[u][v] and matrix[v][u] are set to 1.

Adjacency List

The adjacency list is the most commonly used and efficient representation for graphs, especially when the graph is sparse. It uses a dictionary (or hashmap) where each key is a node, and the value is a list of its neighboring nodes.

To represent an undirected edge, both nodes reference each other in their respective neighbor lists. In Python, the defaultdict from the collections module is often used to simplify this construction.

Node Class with Object References

Another approach is to define a Node class, where each node stores a value and a list of references to its neighbors. This object-oriented structure is useful in custom implementations and problems where more complex behavior is required, but it's less practical for standard graph algorithms.

Graph Traversal Algorithms

Traversing a graph means visiting all its nodes in a specific order. Two fundamental traversal algorithms are Depth-First Search (DFS) and Breadth-First Search (BFS).

Depth-First Search (DFS)

DFS explores as deep as possible along a branch before backtracking. It can be implemented in two ways: recursively or iteratively using a stack.

Recursive DFS involves a function that calls itself. Starting from a node, it marks the node as seen, processes it, and recursively explores each of its unseen neighbors. A seen set (or visited set) is crucial to prevent infinite recursion in graphs with cycles.

Iterative DFS uses a stack explicitly. You push the starting node onto the stack, mark it as seen, and then repeat: pop a node, process it, and push its unseen neighbors. The traversal order can differ slightly depending on the order in which neighbors are added to the stack.

Breadth-First Search (BFS)

BFS visits all nodes at the current "level" before moving to the next. It uses a queue data structure. The algorithm begins by enqueuing the source node and marking it as seen. Then, while the queue isn't empty, it dequeues a node, processes it, and enqueues all of its unseen neighbors.

BFS is ideal for finding the shortest path in unweighted graphs because it explores neighbors in the order of their distance from the starting node. Like DFS, it requires a seen set to avoid visiting the same node more than once.

Time and Space Complexity

The time and space complexity of graph traversal algorithms are typically measured in terms of V (the number of vertices) and E (the number of edges).

Assuming the graph is represented using an adjacency list:

Time Complexity: O(V + E). Every vertex is visited once, and each edge is explored once when checking neighbors.

Space Complexity: O(V + E). This includes the space needed for the adjacency list, the seen set, and the call stack (in recursive DFS) or queue/stack (in BFS/iterative DFS).

If the graph structure itself is provided and not counted toward space usage, the space complexity for just the traversal mechanism is O(V), representing the worst-case usage of the seen set and recursion/stack space.

Relationship to Other Data Structures

Graphs are a generalization of other familiar data structures. A linked list is essentially a directed graph with one edge per node and no cycles. A tree is a connected graph with no cycles and a hierarchical parent-child relationship.

Understanding graphs as a superset of these structures helps in applying graph algorithms to a wider range of problems, especially those involving networked or relational data.

Conclusion

Graphs are a powerful and flexible data structure essential for solving many real-world problems. Understanding their types, representations, and traversal techniques is foundational for mastering more advanced topics in algorithms and data structures.

Whether you're analyzing social networks, routing paths, or modeling dependencies, a strong grasp of graphs will serve as a critical asset in your problem-solving toolkit.

Get Personalized Lessons at AlgoMap Bootcamp 💡