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.

Observe how the algorithm tracks 'visited' nodes to avoid cycles (red edges) and eventually covers the entire component. Click 'Randomize' to test on different graph structures.