Graphs Overview

A Graph is a non-linear data structure consisting of vertices (nodes) and edges (lines connecting nodes). Unlike specific tree structures, graphs have no strict hierarchy-any node can be connected to any other node.

Key Terminology

• Vertex (Node): The fundamental unit (e.g., a City, User, Webpage).
• Edge: The connection between two vertices (e.g., Road, Follow, Hyperlink).
• Degree: The number of edges connected to a vertex. In directed graphs, this splits into in-degree (incoming) and out-degree (outgoing).
• Path: A sequence of edges connecting a sequence of vertices.

Real-World Examples

1. Social Networks: Users are nodes, friendships are edges.
2. Google Maps: Intersections are nodes, roads are edges.
3. The Internet: Webpages are nodes, hyperlinks are edges.

How do we store a graph in code? There are two primary ways:

1. Adjacency Matrix: A 2D array where grid[i][j] = 1 if there is an edge from i to j.

   • Pros: O(1) edge lookup.
   • Cons: O(V²) space, even if the graph is sparse.

2. Adjacency List (Most Common): A Map or Array of Lists where each key is a node and the value is a list of its neighbors.

   • Pros: O(V + E) space. Efficient for sparse graphs.
   • Cons: O(Degree) to check if a specific edge exists.

We will focus primarily on the Adjacency List as it is the most common representation in technical interviews.

DFS on a graph works just like on a tree: we explore as deep as possible before backtracking. However, there is one critical difference:

Cycles and Revisited Nodes

In a tree, we always move down from parent to child, guaranteeing we never visit the same node twice. In a graph, edges can point anywhere. A node can point back to its ancestor (cycle) or two nodes can point to the same neighbor.

Without tracking where we've been, our DFS would recurse infinitely in a cycle (A → B → A → ...).

The Solution: The visited Set
We strictly enforce a rule: "Never process a node more than once."
We maintain a HashSet (or boolean array) called visited.

1. Before traversing to a neighbor, check if it's in visited.
2. If yes, skip it.
3. If no, mark it as visited and recurse.

A single DFS starting from node 0 might not reach all nodes if the graph is disconnected (has "islands").

To handle this, we wrap our DFS in a loop over all nodes:

for i in range(num_nodes):
    if i not in visited:
        dfs(i)

This ensures every Connected Component is visited.