Graphs & BFS/DFS

A Graph is a data structure made up of vertices (also called nodes) connected by edges (also called links). Graphs model relationships — friendships in social networks, roads between cities, links between web pages, and much more.

Types of Graphs:

• Directed vs Undirected — In a directed graph, edges have a direction (A → B is different from B → A). In an undirected graph, edges go both ways.
• Weighted vs Unweighted — Weighted graphs assign a cost or distance to each edge. Unweighted graphs treat all edges equally.
• Cyclic vs Acyclic — A cyclic graph contains at least one cycle (a path that starts and ends at the same vertex). A DAG (Directed Acyclic Graph) has no cycles.

Key Terms:

• Vertex (Node) — A point in the graph
• Edge — A connection between two vertices
• Adjacent — Two vertices connected by an edge
• Degree — The number of edges connected to a vertex
• Path — A sequence of vertices connected by edges
• Cycle — A path that starts and ends at the same vertex

Below is an example undirected graph with 6 nodes (A–F):

There are two common ways to store a graph in memory:

• Adjacency Matrix — A 2D grid where cell (i, j) is 1 if there is an edge from vertex i to vertex j, and 0 otherwise.
• Adjacency List — Each vertex stores a list of its neighbors. More memory-efficient for sparse graphs.

Click edges in the graph below to toggle them on or off. Watch both representations update in real time. Toggle between directed and undirected modes to see how the representations change.

Click two nodes to add or remove an edge between them. The first click selects the source node (highlighted), and the second click selects the destination — toggling the edge between them.

Adjacency List

BFS explores a graph level by level. Starting from a source node, it visits all immediate neighbors first, then their neighbors, and so on. BFS uses a queue (FIFO) to track which node to visit next.

BFS(start):
  queue = [start]
  visited = {start}
  while queue is not empty:
    node = queue.dequeue()
    for each neighbor of node:
      if neighbor not in visited:
        visited.add(neighbor)
        queue.enqueue(neighbor)

Click a node to select the start vertex, then click Run BFS.

DFS explores a graph by going as deep as possible along each branch before backtracking. It uses a stack (LIFO) — either explicitly or via recursion's call stack.

DFS(start):
  stack = [start]
  visited = {}
  while stack is not empty:
    node = stack.pop()
    if node not in visited:
      visited.add(node)
      for each neighbor of node (reversed):
        if neighbor not in visited:
          stack.push(neighbor)

Click a node to select the start vertex, then click Run DFS. Compare with the BFS order from the same start node!

1. Which data structure does BFS use to determine the next node to visit?

2. In an undirected graph, if vertex A is adjacent to vertex B, which of the following is true?

3. DFS explores the graph by: