Graph Basics

Why graphs matter

Now that you've covered Introduction to Data Structures, Mastering Recursion, Sorting Algorithms, and Understanding Hash Tables, you're ready for one of the most common interview and real-world models: graphs.

A graph represents connections:

• friends in a social network
• roads between cities
• links between web pages
• prerequisites between courses
• dependencies between tasks

In this crash course, graphs are where earlier tools combine:

dict/set  -> store connections quickly
queue     -> explore level by level
recursion -> explore deeply

Today, focus on representation and traversal. Later lessons will use these foundations in more advanced strategies.

The basic parts

A graph is made of:

• Vertices / nodes: the things
• Edges: the relationships between things

Example:

A --- B
|     |
C --- D

Here, A, B, C, and D are nodes. The lines are edges.

Useful questions to ask when reading a graph problem:

1. What are the nodes? People? Cells? Words? Cities?
2. What are the edges? Friendship? Movement? One-letter difference? Road?
3. Is direction important? Can you travel both ways?
4. Do edges have weights? Distance, cost, time?

Most beginner graph mistakes happen because the programmer starts coding before answering these four questions.

Store connections with a dictionary

The most common graph representation for interviews is an adjacency list.

Since you just learned hash tables, this should feel familiar:

node -> collection of connected nodes

In Python, this is usually a dict where each key is a node and each value is a list or set of connected nodes.

Use a list when order or duplicates are not a concern. Use a set when you want fast membership checks and no duplicate edges.

```python
# Undirected graph using an adjacency list

graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C"]
}

print("Graph:")
for node, neighbors in graph.items():
    print(node, "->", neighbors)

print("\nNeighbors of A:", graph["A"])
print("Is D connected to B?", "D" in graph["B"])
```

Not all graphs behave the same

Before solving, identify the graph type.

Undirected graph

Edges go both ways:

A --- B

If A is connected to B, then B is connected to A.

Directed graph

Edges have arrows:

A --> B

This could mean A depends on B, or there is a one-way route.

Weighted graph

Edges have costs:

A --5-- B

The 5 might represent distance, time, or price.

For this lesson, we mostly use unweighted graphs so you can master representation and traversal first.

You need to store a sparse graph and quickly list all nodes directly connected to a given node.

Which representation is usually the best beginner-friendly choice?

Explore level by level

Breadth First Search, usually called BFS, explores a graph outward in layers.

It uses the queue idea from Introduction to Data Structures:

start
then all distance-1 nodes
then all distance-2 nodes
then all distance-3 nodes

BFS is useful when you care about the fewest number of edges in an unweighted graph, such as:

• minimum moves in a puzzle
• shortest path in an unweighted maze
• people within 2 friendships

The key rule: keep a visited set so you do not loop forever in cycles.

```python
from collections import deque

graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"]
}

def bfs(start):
    visited = set([start])
    queue = deque([start])
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return order

print("BFS from A:", bfs("A"))
```

True or false?

In an undirected graph represented as an adjacency list, adding an edge between A and B usually means storing B under A and also storing A under B.

Explore one path deeply

Depth First Search, or DFS, follows one path as far as it can before backing up.

This connects directly to Mastering Recursion: recursive DFS uses the call stack to remember where to return.

DFS is useful for questions like:

• Can I reach this target?
• How many connected groups exist?
• Is every node reachable from the start?

Again, visited is essential. Graphs can contain cycles, and cycles can trap naive recursion.

```python
graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"]
}

def dfs(node, visited=None, order=None):
    if visited is None:
        visited = set()
    if order is None:
        order = []

    visited.add(node)
    order.append(node)

    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(neighbor, visited, order)

    return order

print("DFS from A:", dfs("A"))
```

In an adjacency list implemented with a Python dictionary, each key is a node and each value is a collection of directly connected nodes.

Those directly connected nodes are called ____.

Lock in graph basics

Graphs can feel unfamiliar at first because they are less linear than lists, stacks, queues, and sorted arrays. Your job this week is to make the mental model automatic.

Review these every 2 days:

1. Build an adjacency list from a list of edges.
2. Run BFS from a start node and print visit order.
3. Run DFS recursively and explain the role of visited.
4. Count connected components in a small undirected graph.

Decision checklist:

Need relationships?       -> graph
Need fast node lookup?    -> dict
Need avoid repeats?       -> visited set
Need level by level?      -> BFS + queue
Need deep exploration?    -> DFS + recursion/stack

Next, we shift into Divide and Conquer Strategies, where the focus returns to breaking problems into smaller pieces.