Adjacency List Representation in DSA Python - Execution Trace

Concept Flow - Adjacency List Representation

Start: Empty Graph

↓

Add Vertex

↓

Add Edge

↓

Update Adjacency List

↓

Repeat for all vertices and edges

↓

Graph Ready for Traversal or Queries

Build graph by adding vertices and edges, updating adjacency list for each edge.

Execution Sample

DSA Python

graph = {}
# Add vertices
graph['A'] = []
graph['B'] = []
# Add edge A-B
graph['A'].append('B')
graph['B'].append('A')

Create an undirected graph with vertices A and B connected by an edge.

Execution Table

Step	Operation	Nodes in Graph	Adjacency List State	Visual State
1	Initialize empty graph	{}	{}	{}
2	Add vertex 'A'	{'A'}	{'A': []}	{A: []}
3	Add vertex 'B'	{'A', 'B'}	{'A': [], 'B': []}	{A: [], B: []}
4	Add edge A-B	{'A', 'B'}	{'A': ['B'], 'B': []}	{A: [B], B: []}
5	Add edge B-A	{'A', 'B'}	{'A': ['B'], 'B': ['A']}	{A: [B], B: [A]}
6	Graph construction complete	{'A', 'B'}	{'A': ['B'], 'B': ['A']}	{A: [B], B: [A]}

💡 All vertices and edges added, adjacency list fully represents the graph.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
graph	{}	{'A': []}	{'A': [], 'B': []}	{'A': ['B'], 'B': []}	{'A': ['B'], 'B': ['A']}	{'A': ['B'], 'B': ['A']}

Key Moments - 3 Insights

Why do we add 'B' to 'A's list and also 'A' to 'B's list?

Because the graph is undirected, each edge connects two nodes both ways. Step 4 adds 'B' to 'A's list, step 5 adds 'A' to 'B's list, ensuring bidirectional connection as shown in execution_table rows 4 and 5.

What does an empty list for a vertex mean in the adjacency list?

It means the vertex has no edges yet. For example, after step 2, 'A' has an empty list meaning no connections. This is shown in execution_table row 2.

Why do we use a dictionary with lists for adjacency representation?

The dictionary keys represent vertices, and the lists store connected vertices. This structure allows easy lookup and update of neighbors, as seen in the variable_tracker and adjacency list states.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the adjacency list for vertex 'A'?

A ['B']

B []

C ['A']

D ['B', 'A']

💡 Hint

Check the 'Adjacency List State' column at step 4 in execution_table.

At which step does vertex 'B' first appear in the graph?

A Step 1

B Step 3

C Step 2

D Step 4

💡 Hint

Look at the 'Nodes in Graph' column in execution_table to see when 'B' is added.

If we add a new vertex 'C' without edges, how would the adjacency list change after step 3?

A {'A': [], 'B': []}

B {'A': ['B'], 'B': ['A'], 'C': []}

C {'A': [], 'B': [], 'C': []}

D {'A': ['B'], 'B': ['A']}

💡 Hint

Adding a vertex without edges means adding a key with an empty list, similar to steps 2 and 3.

Concept Snapshot

Adjacency List Representation:
- Use a dictionary: keys are vertices
- Values are lists of connected vertices
- For undirected graphs, add edges both ways
- Efficient for sparse graphs
- Easy to add/remove edges and vertices

Full Transcript

Adjacency List Representation stores a graph as a dictionary where each vertex key maps to a list of its neighbors. We start with an empty graph, add vertices as keys with empty lists, then add edges by appending connected vertices to each other's lists. This representation is efficient and clear for graph operations.

Practice

1. What does an adjacency list represent in graph data structures?

easy

A. A list of all nodes without connections

B. A matrix showing distances between nodes

C. A list of nodes sorted by their values

D. A list where each node stores its connected neighbors

Solution

1. Step 1: Understand adjacency list concept

   An adjacency list stores each node with a list of nodes it connects to directly.

2. Step 2: Compare options with definition

   Only A list where each node stores its connected neighbors correctly describes this structure as neighbors stored per node.

3. Final Answer:

   A list where each node stores its connected neighbors -> Option D

4. Quick Check:

   Adjacency list = neighbors per node [OK]

Hint: Adjacency list = nodes with their direct neighbors [OK]

Common Mistakes:

• Confusing adjacency list with adjacency matrix
• Thinking it stores distances instead of neighbors
• Assuming it lists nodes without connections

2. Which of the following is the correct Python syntax to initialize an empty adjacency list for a graph with 3 nodes?

easy

A. graph = {0: [], 1: [], 2: []}

B. graph = [[], [], []]

C. graph = {0: None, 1: None, 2: None}

D. graph = [0, 1, 2]

Solution

1. Step 1: Understand adjacency list initialization

   An adjacency list is usually a dictionary with keys as nodes and values as lists of neighbors.

2. Step 2: Check each option

   graph = {0: [], 1: [], 2: []} correctly creates a dict with empty lists for each node. graph = [[], [], []] is a list of lists but lacks node keys. graph = {0: None, 1: None, 2: None} uses None instead of lists. graph = [0, 1, 2] is just a list of nodes, not adjacency lists.

3. Final Answer:

   graph = {0: [], 1: [], 2: []} -> Option A

4. Quick Check:

   Dict with empty lists = adjacency list init [OK]

Hint: Use dict with nodes as keys and empty lists as values [OK]

Common Mistakes:

• Using None instead of empty lists for neighbors
• Using list without node keys
• Confusing adjacency list with simple node list

3. What is the output of the following code?

graph = {0: [1, 2], 1: [2], 2: [0, 3], 3: []}
print(graph[2])

medium

A. [1, 2]

B. [0, 3]

C. [2]

D. []

Solution

1. Step 1: Identify the adjacency list for node 2

   In the dictionary, key 2 maps to the list [0, 3].

2. Step 2: Print the value for key 2

   Printing graph[2] outputs [0, 3].

3. Final Answer:

   [0, 3] -> Option B

4. Quick Check:

   graph[2] = [0, 3] [OK]

Hint: Look up the key in dict to get neighbors list [OK]

Common Mistakes:

• Confusing keys and values
• Printing wrong node's neighbors
• Misreading list contents

4. The following code tries to add an edge from node 1 to node 3 in the adjacency list but causes an error. What is the error?

graph = {0: [1], 1: [2], 2: [0]}
graph[1].append(3)
print(graph)

medium

A. KeyError because node 3 does not exist in graph

B. IndexError because list index out of range

C. No error, code runs correctly

D. TypeError because append is used on a dict

Solution

1. Step 1: Check if node 1 exists in graph

   Node 1 is a key in graph with value [2], so graph[1] is a list.

2. Step 2: Append 3 to graph[1]

   Appending 3 to the list [2] is valid and updates graph[1] to [2, 3].

3. Final Answer:

   No error, code runs correctly -> Option C

4. Quick Check:

   Appending to list in dict value works [OK]

Hint: Appending to existing list key is valid, no error [OK]

Common Mistakes:

• Thinking node 3 must exist as key before adding
• Confusing append on list vs dict
• Expecting error when adding new neighbor

5. Given a graph represented by the adjacency list:

graph = {0: [1, 2], 1: [2], 2: [0], 3: [2]}

Which node(s) have no outgoing edges?

hard

A. None, all have outgoing edges

B. Node 1

C. Node 2

D. Node 3

Solution

1. Step 1: Check neighbors list for each node

   Node 0 connects to [1, 2], node 1 to [2], node 2 to [0], node 3 to [2].

2. Step 2: Identify nodes with empty neighbor lists

   Node 3 has neighbors [2], so it has outgoing edges. No node has an empty list, so none have no outgoing edges.

3. Final Answer:

   None, all have outgoing edges -> Option A

4. Quick Check:

   All adjacency lists non-empty = no node without edges [OK]

Hint: Check for empty neighbor lists to find no outgoing edges [OK]

Common Mistakes:

• Assuming node 3 has no edges because it appears last
• Confusing incoming edges with outgoing edges
• Ignoring non-empty lists