Welcome, aspiring algorithm architect! In our journey through data structures, we’ve explored linear arrangements like arrays and linked lists, and hierarchical ones like trees. Now, it’s time to tackle the ultimate structure for representing complex relationships: Graphs.

Graphs are everywhere in the real world, from the intricate web of social media connections to the sprawling networks of roads and the internet itself. Understanding graphs is crucial for solving problems in navigation, resource allocation, recommendation systems, and much more. This chapter will demystify graphs, teaching you their core concepts, how to represent them efficiently in TypeScript, and how to navigate their complex pathways using fundamental traversal algorithms like Breadth-First Search (BFS) and Depth-First Search (DFS).

To get the most out of this chapter, you should be comfortable with basic TypeScript syntax, object-oriented programming concepts, and have a foundational understanding of arrays, linked lists, and the concepts of queues and stacks (which we’ll use for graph traversal). Let’s dive in and learn how to connect the world, one node at a time!

Core Concepts: What Makes a Graph?

At its heart, a graph is a collection of two things: nodes (also called vertices) and edges (which are the connections between these nodes). Think of cities as nodes and the roads connecting them as edges. Simple, right? But this simple idea opens up a world of possibilities.

Nodes and Edges

  • Nodes (Vertices): These are the individual entities or points in your graph. In a social network, each person is a node. On a map, each intersection or landmark could be a node.
  • Edges: These are the links that connect two nodes. An edge signifies a relationship or connection between the nodes it joins. In a social network, an edge might represent a friendship. On a map, an edge is a road segment.

Let’s visualize a simple graph.

graph TD A[Alice] --> B[Bob] A --> C[Carol] B --> D[David] C --> D D --> E[Eve]

Figure 14.1: A simple graph showing connections between people.

In this graph:

  • Nodes are Alice, Bob, Carol, David, and Eve.
  • Edges are the connections between them, like Alice to Bob, Bob to David, etc.

Types of Graphs

Graphs come in several flavors, each suited for different problems:

  1. Directed vs. Undirected Graphs:
    • Undirected Graph: Edges have no direction. If Alice is friends with Bob, then Bob is also friends with Alice. The connection goes both ways. (Our example above is an undirected graph, even though the arrows are drawn for clarity, they imply a two-way connection).
    • Directed Graph (Digraph): Edges have a specific direction. If Alice follows Bob on social media, Bob doesn’t necessarily follow Alice back. The connection is one-way.
graph LR A_dir[Sender] --> B_dir[Receiver] C_dir[Task 1] --> D_dir[Task 2]
*Figure 14.2: Examples of directed edges.*
  1. Weighted vs. Unweighted Graphs:
    • Unweighted Graph: All edges are considered equal. The cost or distance of traversing an edge is the same for all.
    • Weighted Graph: Edges have a numerical value (a “weight” or “cost”) associated with them. On a map, this could be the distance of a road, the time it takes to travel, or the traffic congestion.
graph TD S[Start] -->|50km| A[City A] A -->|20km| B[City B] S -->|70km| B
*Figure 14.3: A weighted graph where edges have costs.*
  1. Cyclic vs. Acyclic Graphs:
    • Cyclic Graph: Contains at least one “cycle,” meaning you can start at a node, follow a path of edges, and return to the starting node without repeating any edges.
    • Acyclic Graph: Contains no cycles. A Directed Acyclic Graph (DAG) is particularly common and useful in scenarios like task scheduling or representing dependencies.

Graph Representation: How Do We Store Them?

How do we actually store these nodes and edges in our computer’s memory? There are two primary ways:

1. Adjacency Matrix

Imagine a square grid (a 2D array) where both rows and columns represent your nodes.

  • If you have N nodes, you’ll have an N x N matrix.
  • matrix[i][j] is 1 (or true) if there’s an edge from node i to node j, and 0 (or false) otherwise.
  • For weighted graphs, matrix[i][j] could store the weight of the edge instead of just 1.

Pros:

  • Fast edge lookup: Checking if an edge exists between two nodes (i and j) is O(1) – just look up matrix[i][j].
  • Simple to implement for dense graphs (graphs with many edges).

Cons:

  • Space inefficient: Requires O(V^2) space, where V is the number of vertices. For graphs with many nodes but few connections (sparse graphs), most of the matrix will be empty.
  • Slow to find neighbors: To find all neighbors of a node, you have to iterate through an entire row (O(V)).

2. Adjacency List

This is often the preferred method for most real-world graphs, which tend to be sparse.

  • It uses an array or a hash map where each index (or key) represents a node.
  • The value at each index/key is a list (or array, or set) of all the nodes it’s connected to.

Pros:

  • Space efficient: Requires O(V + E) space, where V is the number of vertices and E is the number of edges. This is much better for sparse graphs.
  • Fast to find neighbors: To find all neighbors of a node, you just access its list of connections, which is O(degree of vertex).

Cons:

  • Slower edge lookup: Checking if an edge exists between two specific nodes requires iterating through one of the adjacency lists, which can be O(degree of vertex) in the worst case.

Which one to choose?

  • If your graph is dense (many edges, E is close to V^2) and you frequently need O(1) edge existence checks, an adjacency matrix might be suitable.
  • If your graph is sparse (few edges, E is much smaller than V^2) and you frequently need to find all neighbors of a node, an adjacency list is generally superior for both space and time efficiency. Most real-world graphs fall into this category.

For our implementation, we’ll use an adjacency list because it’s more versatile and efficient for the common scenarios you’ll encounter. We’ll represent it using a Map in TypeScript for flexibility, where keys are vertex names (strings) and values are arrays of connected vertex names.

Step-by-Step Implementation: Building a Graph in TypeScript

Let’s get our hands dirty and implement a basic undirected, unweighted graph using an adjacency list in TypeScript. We’ll be working in a Node.js environment. Make sure you have Node.js version 24.13.0 LTS (or newer) and TypeScript installed.

If you need a refresher on setting up your environment, refer back to Chapter 1. For a quick check, you can run node -v and tsc -v in your terminal.

1. Project Setup

First, let’s create a new project directory:

mkdir graph-dsa
cd graph-dsa
npm init -y
npm install typescript@latest @types/node@latest
npx tsc --init

Now, open tsconfig.json and ensure outDir is set to ./dist and rootDir to ./src. Create a src folder and an index.ts file inside it.

// src/index.ts
console.log("Graph implementation coming soon!");

You can compile and run this with:

npx tsc
node dist/index.js

2. The Graph Class Structure

Let’s define our Graph class. We’ll use a Map to store our adjacency list. Each key in the map will be a vertex (represented by a string), and its value will be an array of strings representing its neighbors.

// src/Graph.ts
class Graph {
    // The adjacency list will store vertex connections.
    // Key: string (vertex name), Value: string[] (array of connected vertices)
    adjacencyList: Map<string, string[]>;

    constructor() {
        this.adjacencyList = new Map();
    }

    /**
     * Adds a new vertex to the graph.
     * If the vertex already exists, it does nothing.
     * @param vertex The name of the vertex to add.
     */
    addVertex(vertex: string): void {
        if (!this.adjacencyList.has(vertex)) {
            this.adjacencyList.set(vertex, []);
            console.log(`Vertex '${vertex}' added.`);
        } else {
            console.log(`Vertex '${vertex}' already exists.`);
        }
    }

    /**
     * Adds an undirected edge between two vertices.
     * If either vertex does not exist, it logs an error.
     * @param vertex1 The first vertex.
     * @param vertex2 The second vertex.
     */
    addEdge(vertex1: string, vertex2: string): void {
        // Ensure both vertices exist before adding an edge
        if (!this.adjacencyList.has(vertex1)) {
            console.error(`Error: Vertex '${vertex1}' does not exist.`);
            return;
        }
        if (!this.adjacencyList.has(vertex2)) {
            console.error(`Error: Vertex '${vertex2}' does not exist.`);
            return;
        }

        // Add edge from vertex1 to vertex2
        // Check if the edge already exists to prevent duplicates
        if (!this.adjacencyList.get(vertex1)?.includes(vertex2)) {
            this.adjacencyList.get(vertex1)?.push(vertex2);
            console.log(`Edge added: ${vertex1} -- ${vertex2}`);
        }

        // Add edge from vertex2 to vertex1 (for undirected graph)
        if (!this.adjacencyList.get(vertex2)?.includes(vertex1)) {
            this.adjacencyList.get(vertex2)?.push(vertex1);
            console.log(`Edge added: ${vertex2} -- ${vertex1}`);
        }
    }

    /**
     * Displays the current adjacency list of the graph.
     */
    display(): void {
        console.log("\nGraph Adjacency List:");
        for (const [vertex, neighbors] of this.adjacencyList) {
            console.log(`${vertex} -> ${neighbors.join(', ')}`);
        }
    }
}

export default Graph; // Export the class for use in other files

Explanation:

  • adjacencyList: Map<string, string[]>: This is our core data structure. A Map is used because vertex names can be arbitrary strings, and Map provides O(1) average time complexity for adding and retrieving vertex lists.
  • constructor(): Initializes the adjacencyList to an empty Map.
  • addVertex(vertex: string):
    • Checks if the vertex already exists in the Map. If not, it adds the vertex as a key and initializes its value to an empty array ([]), indicating no connections yet.
    • This prevents duplicate vertices and ensures every vertex has an entry in the Map.
  • addEdge(vertex1: string, vertex2: string):
    • Crucially, it first checks if both vertex1 and vertex2 actually exist in our graph. An edge cannot exist without its endpoints!
    • It then adds vertex2 to vertex1’s list of neighbors, and vertex1 to vertex2’s list. This makes the edge undirected.
    • We also add a check to prevent adding the same edge multiple times.
  • display(): A helper method to print out the graph’s current structure, which is very useful for debugging and understanding.

3. Using Our Graph Class

Now, let’s create an instance of our Graph and add some vertices and edges in src/index.ts.

// src/index.ts
import Graph from './Graph'; // Import our Graph class

// Create a new graph instance
const myGraph = new Graph();

// Add some vertices
console.log("--- Adding Vertices ---");
myGraph.addVertex("A");
myGraph.addVertex("B");
myGraph.addVertex("C");
myGraph.addVertex("D");
myGraph.addVertex("E");
myGraph.addVertex("F"); // An isolated vertex for now

// Add some edges
console.log("\n--- Adding Edges ---");
myGraph.addEdge("A", "B");
myGraph.addEdge("A", "C");
myGraph.addEdge("B", "D");
myGraph.addEdge("C", "E");
myGraph.addEdge("D", "E");
myGraph.addEdge("D", "F"); // Connecting D to F

// Try adding an edge with a non-existent vertex
myGraph.addEdge("X", "Y");
myGraph.addEdge("A", "X");

// Display the graph
myGraph.display();

/*
Expected Output:
--- Adding Vertices ---
Vertex 'A' added.
Vertex 'B' added.
Vertex 'C' added.
Vertex 'D' added.
Vertex 'E' added.
Vertex 'F' added.

--- Adding Edges ---
Edge added: A -- B
Edge added: B -- A
Edge added: A -- C
Edge added: C -- A
Edge added: B -- D
Edge added: D -- B
Edge added: C -- E
Edge added: E -- C
Edge added: D -- E
Edge added: E -- D
Edge added: D -- F
Edge added: F -- D
Error: Vertex 'X' does not exist.
Error: Vertex 'Y' does not exist.
Error: Vertex 'X' does not exist.

Graph Adjacency List:
A -> B, C
B -> A, D
C -> A, E
D -> B, E, F
E -> C, D
F -> D
*/

Run your code:

npx tsc
node dist/index.js

Observe the output. You should see the vertices being added, edges created, and the display() method showing the connections. Notice how the error messages appear when you try to add an edge to a non-existent vertex.

4. Graph Traversal: Breadth-First Search (BFS)

Now that we have a graph, how do we explore it? Graph traversal algorithms are essential for visiting every node in a systematic way. Breadth-First Search (BFS) is one of the most common.

What is BFS?

Imagine you’re at a node, say “Home” on a map. BFS explores all of “Home’s” immediate neighbors first (all the places you can reach in one step). Then, it explores all of their unvisited neighbors (all the places you can reach in two steps from Home), and so on. It expands outwards, layer by layer, like ripples in a pond.

Why is BFS useful?

  • Finding the shortest path in an unweighted graph. Since it explores layer by layer, the first time you reach a target node, you’ve found the path with the fewest edges.
  • Finding all connected components in a graph.
  • Web crawlers (finding all pages linked from a starting page).
  • Social network analysis (finding “friends of friends”).

How does BFS work? (The Algorithm)

BFS uses a queue data structure to keep track of nodes to visit.

  1. Start: Pick a starting node.
  2. Initialize: Create a queue and a visited set. Add the starting node to both.
  3. Loop: While the queue is not empty: a. Dequeue a node from the front of the queue. b. “Process” this node (e.g., print it, add it to a result list). c. For each of its neighbors: i. If a neighbor has not been visited: * Mark the neighbor as visited. * Enqueue the neighbor.

Let’s implement a simple bfs method in our Graph class. We’ll need a basic Queue implementation. For simplicity, we can use a standard JavaScript array with shift() and push() methods acting as a queue.

// src/Graph.ts (add this inside the Graph class)

    /**
     * Performs a Breadth-First Search (BFS) starting from a given vertex.
     * @param startVertex The vertex to start the BFS from.
     * @returns An array of vertices in the order they were visited.
     */
    bfs(startVertex: string): string[] {
        if (!this.adjacencyList.has(startVertex)) {
            console.error(`Error: Start vertex '${startVertex}' not found.`);
            return [];
        }

        const result: string[] = [];
        const queue: string[] = []; // Using an array as a queue (first-in, first-out)
        const visited: Set<string> = new Set(); // To keep track of visited vertices

        // 1. Start: Add the start vertex to the queue and mark as visited
        queue.push(startVertex);
        visited.add(startVertex);

        // 2. Loop: While the queue is not empty
        while (queue.length > 0) {
            // a. Dequeue a vertex
            const currentVertex = queue.shift()!; // `!` asserts it won't be undefined

            // b. Process this vertex
            result.push(currentVertex);
            console.log(`Visiting: ${currentVertex}`); // For demonstration

            // c. For each of its neighbors
            const neighbors = this.adjacencyList.get(currentVertex) || [];
            for (const neighbor of neighbors) {
                // i. If a neighbor has not been visited
                if (!visited.has(neighbor)) {
                    visited.add(neighbor); // Mark as visited
                    queue.push(neighbor); // Enqueue the neighbor
                }
            }
        }
        console.log(`BFS traversal complete from '${startVertex}'.`);
        return result;
    }

Explanation:

  • result: An array to store the order of visited nodes.
  • queue: A standard array used as a queue. push() adds to the end, shift() removes from the beginning.
  • visited: A Set is perfect for keeping track of visited nodes because has() and add() operations are O(1) on average. This is crucial to prevent infinite loops in cyclic graphs and redundant processing.
  • The while (queue.length > 0) loop continues until all reachable nodes have been explored.

5. Graph Traversal: Depth-First Search (DFS)

Now for the other fundamental traversal: Depth-First Search (DFS).

What is DFS?

Instead of exploring layer by layer, DFS goes as deep as possible along each branch before backtracking. Imagine exploring a maze: you pick a path and keep going until you hit a dead end or a visited spot, then you backtrack and try another path.

Why is DFS useful?

  • Finding paths between two nodes.
  • Detecting cycles in a graph.
  • Topological sorting (for DAGs, used in task scheduling, build systems).
  • Finding connected components (similar to BFS).

How does DFS work? (The Algorithm)

DFS typically uses a stack (explicitly or implicitly via recursion) and a visited set. We’ll implement the recursive version, which is often more elegant.

  1. Start: Pick a starting node.
  2. Initialize: Create a visited set.
  3. Recursive Function: Define a helper function dfsRecursive(vertex): a. “Process” the vertex (e.g., print it, add it to a result list). b. Mark the vertex as visited. c. For each of its neighbors: i. If a neighbor has not been visited: * Recursively call dfsRecursive(neighbor).
// src/Graph.ts (add this inside the Graph class)

    /**
     * Performs a Depth-First Search (DFS) starting from a given vertex.
     * @param startVertex The vertex to start the DFS from.
     * @returns An array of vertices in the order they were visited.
     */
    dfs(startVertex: string): string[] {
        if (!this.adjacencyList.has(startVertex)) {
            console.error(`Error: Start vertex '${startVertex}' not found.`);
            return [];
        }

        const result: string[] = [];
        const visited: Set<string> = new Set(); // To keep track of visited vertices
        const adjacencyList = this.adjacencyList; // Capture `this` context

        // Recursive helper function for DFS
        function dfsRecursive(vertex: string) {
            visited.add(vertex); // Mark as visited
            result.push(vertex); // Process this vertex
            console.log(`Visiting: ${vertex}`); // For demonstration

            const neighbors = adjacencyList.get(vertex) || [];
            for (const neighbor of neighbors) {
                if (!visited.has(neighbor)) {
                    dfsRecursive(neighbor); // Recursively visit unvisited neighbors
                }
            }
        }

        // Start the DFS from the given vertex
        dfsRecursive(startVertex);
        console.log(`DFS traversal complete from '${startVertex}'.`);
        return result;
    }

Explanation:

  • dfsRecursive(vertex: string): This inner function is the heart of our recursive DFS.
  • visited.add(vertex): Marks the current node as visited before exploring its neighbors.
  • result.push(vertex): Adds the node to our result list.
  • The for...of loop iterates through neighbors. If a neighbor hasn’t been visited, dfsRecursive is called on it, effectively going deeper into that branch. The function will only return (backtrack) once all reachable nodes from that branch have been visited.

6. Putting BFS and DFS to the Test

Let’s modify src/index.ts to use our new traversal methods.

// src/index.ts
import Graph from './Graph';

const myGraph = new Graph();

// Add vertices for a more complex graph
myGraph.addVertex("A");
myGraph.addVertex("B");
myGraph.addVertex("C");
myGraph.addVertex("D");
myGraph.addVertex("E");
myGraph.addVertex("F");

// Add edges to create a graph with multiple paths
myGraph.addEdge("A", "B");
myGraph.addEdge("A", "C");
myGraph.addEdge("B", "D");
myGraph.addEdge("C", "E");
myGraph.addEdge("D", "E");
myGraph.addEdge("D", "F");
myGraph.addEdge("E", "F"); // Add another edge to create a cycle

myGraph.display();

console.log("\n--- BFS Traversal (Starting from A) ---");
const bfsResult = myGraph.bfs("A");
console.log("BFS Result Order:", bfsResult);

console.log("\n--- DFS Traversal (Starting from A) ---");
const dfsResult = myGraph.dfs("A");
console.log("DFS Result Order:", dfsResult);

/*
Expected Output (order might vary slightly for BFS/DFS depending on neighbor iteration order in Map/Set, but general structure should be similar):

Graph Adjacency List:
A -> B, C
B -> A, D
C -> A, E
D -> B, E, F
E -> C, D, F
F -> D, E

--- BFS Traversal (Starting from A) ---
Visiting: A
Visiting: B
Visiting: C
Visiting: D
Visiting: E
Visiting: F
BFS traversal complete from 'A'.
BFS Result Order: [ 'A', 'B', 'C', 'D', 'E', 'F' ]

--- DFS Traversal (Starting from A) ---
Visiting: A
Visiting: B
Visiting: D
Visiting: E
Visiting: C
Visiting: F
DFS traversal complete from 'A'.
DFS Result Order: [ 'A', 'B', 'D', 'E', 'C', 'F' ]
*/

Run your code again:

npx tsc
node dist/index.js

Compare the BFS and DFS output. Notice how BFS explores “A”, then “B” and “C” (level 1), then “D”, “E”, “F” (level 2), while DFS dives into “A”, then “B”, then “D”, then “E”, then “C”, then “F” (the order of processing neighbors can influence the exact DFS path, but it will always go “deep” before “wide”). This demonstrates their distinct exploration patterns.

Mini-Challenge: Counting Connected Components

A graph might not be fully connected; it could consist of several independent “sub-graphs” or connected components. For example, in a social network, if two groups of people have no friends in common, they form separate connected components.

Challenge: Add a new method countConnectedComponents() to your Graph class. This method should return the number of distinct connected components in the graph. You’ll need to leverage your BFS or DFS traversal logic.

Hint: To count components, you need to iterate through all vertices. If a vertex hasn’t been visited yet, it means you’ve found a new component. Start a traversal (BFS or DFS) from that unvisited vertex, and all nodes reachable from it will be part of that same component. Mark them all as visited during the traversal. Repeat until all vertices have been visited.

// Add this method inside your Graph class in src/Graph.ts

    /**
     * Counts the number of connected components in the graph.
     * Leverages either BFS or DFS to explore components.
     * @returns The total number of connected components.
     */
    countConnectedComponents(): number {
        let count = 0;
        const visited: Set<string> = new Set();
        const allVertices = Array.from(this.adjacencyList.keys()); // Get all vertices

        // Iterate over all vertices in the graph
        for (const vertex of allVertices) {
            // If a vertex has not been visited, it means it's part of a new component
            if (!visited.has(vertex)) {
                count++; // Increment component count
                console.log(`Starting traversal for component ${count} from vertex: ${vertex}`);

                // Perform a traversal (BFS or DFS) to mark all nodes in this component as visited
                // We'll use BFS here, but DFS would work just as well
                const queue: string[] = [vertex];
                visited.add(vertex);

                while (queue.length > 0) {
                    const current = queue.shift()!;
                    const neighbors = this.adjacencyList.get(current) || [];
                    for (const neighbor of neighbors) {
                        if (!visited.has(neighbor)) {
                            visited.add(neighbor);
                            queue.push(neighbor);
                        }
                    }
                }
            }
        }
        return count;
    }

Now, modify src/index.ts to test this new method. First, create a graph with two separate components.

// src/index.ts
import Graph from './Graph';

const myGraph = new Graph();

// Component 1
myGraph.addVertex("A");
myGraph.addVertex("B");
myGraph.addVertex("C");
myGraph.addEdge("A", "B");
myGraph.addEdge("B", "C");

// Component 2 (isolated from Component 1)
myGraph.addVertex("X");
myGraph.addVertex("Y");
myGraph.addEdge("X", "Y");

myGraph.display();

console.log("\n--- Counting Connected Components ---");
const components = myGraph.countConnectedComponents();
console.log(`Total connected components: ${components}`);

/*
Expected Output:

Graph Adjacency List:
A -> B
B -> A, C
C -> B
X -> Y
Y -> X

--- Counting Connected Components ---
Starting traversal for component 1 from vertex: A
Starting traversal for component 2 from vertex: X
Total connected components: 2
*/

Run your code and verify the output. You should see Total connected components: 2. This demonstrates how traversal algorithms can be adapted for various graph problems.

Common Pitfalls & Troubleshooting

  1. Forgetting to Track Visited Nodes: This is the most common mistake in graph traversal. If you don’t use a visited set (or array), your BFS/DFS will fall into an infinite loop if the graph contains cycles, or it will reprocess nodes unnecessarily, leading to incorrect results and poor performance. Always initialize visited and mark nodes as you enqueue/process them.
  2. Handling Disconnected Graphs: Your BFS/DFS functions, when called once, will only explore the component reachable from the startVertex. If your graph has multiple components (like in our countConnectedComponents challenge), a single traversal won’t visit all nodes. You need an outer loop that iterates through all vertices and starts a new traversal whenever it finds an unvisited vertex.
  3. Edge Cases for addEdge:
    • Non-existent Vertices: Make sure your addEdge method checks if the vertices it’s trying to connect actually exist in the graph. Our implementation does this, preventing runtime errors.
    • Self-loops: An edge from a vertex to itself. Our current addEdge doesn’t explicitly prevent this, but it’s generally handled by ensuring vertex1 !== vertex2 if self-loops are not desired.
    • Duplicate Edges: Our addEdge checks includes() to prevent adding the same edge multiple times for undirected graphs, which is good practice.
  4. Performance of queue.shift(): In JavaScript, Array.prototype.shift() has O(N) time complexity because it re-indexes all subsequent elements. For very large graphs, this can become a bottleneck for BFS. A more performant queue implementation (e.g., a custom Queue class using a LinkedList or two stacks) would be O(1). For typical interview problems and moderate graph sizes, the array shift() is often acceptable for simplicity.

Summary

Phew! You’ve just taken a significant step into the world of graphs, a truly powerful data structure. Here’s a quick recap of what we covered:

  • Graphs model connections: They consist of nodes (vertices) and edges.
  • Graph types: We learned about directed vs. undirected, weighted vs. unweighted, and cyclic vs. acyclic graphs.
  • Representations:
    • Adjacency Matrix: O(V^2) space, O(1) edge lookup, O(V) to find neighbors. Best for dense graphs.
    • Adjacency List: O(V + E) space, O(degree) to find neighbors, O(degree) edge lookup. Generally preferred for sparse graphs (most real-world scenarios).
  • Implementation: We built a Graph class in TypeScript using an adjacency list (implemented with a Map<string, string[]>) and methods to addVertex and addEdge.
  • Graph Traversal Algorithms:
    • Breadth-First Search (BFS): Explores layer by layer, uses a queue, finds shortest paths in unweighted graphs.
    • Depth-First Search (DFS): Explores as deep as possible, uses a stack (or recursion), useful for path finding, cycle detection, and topological sort.
  • Practical Application: We implemented a countConnectedComponents method, showcasing how traversal algorithms solve real-world problems.

Graphs are a cornerstone of computer science, and mastering their fundamentals opens the door to understanding complex systems and advanced algorithms. In upcoming chapters, we’ll delve deeper into more sophisticated graph algorithms like shortest path algorithms (Dijkstra’s, Bellman-Ford), minimum spanning trees (Prim’s, Kruskal’s), and topological sorting. Keep exploring!

References

This page is AI-assisted and reviewed. It references official documentation and recognized resources where relevant.