Adjacency List Representation in DSA Python - Build from Scratch

Adjacency List Representation

📖 Scenario: You are helping a friend organize their social network connections. Each person is a node, and their friendships are edges. You will represent this network using an adjacency list.

🎯 Goal: Build an adjacency list to represent a small social network graph. Then, add a new person with their connections, and finally print the adjacency list.

📋 What You'll Learn

Create a dictionary called graph with exact keys and list values

Add a new key-value pair to graph representing a new person and their friends

Use the adjacency list format where each key is a node and the value is a list of connected nodes

Print the final graph dictionary

💡 Why This Matters

🌍 Real World

Adjacency lists are used to represent networks like social connections, road maps, or computer networks efficiently.

💼 Career

Understanding adjacency lists is essential for roles in software development, data analysis, and network engineering where graph data structures are common.

1

Create the initial adjacency list

Create a dictionary called graph with these exact entries: 'Alice': ['Bob', 'Charlie'], 'Bob': ['Alice'], 'Charlie': ['Alice']

DSA Python

# Create the initial adjacency list dictionary called graph
# Your code here

Hint

Use curly braces {} to create a dictionary. Each key is a person's name, and the value is a list of their friends.

2

Add a new person with connections

Add a new key 'David' to the graph dictionary with the value ['Alice', 'Charlie']

DSA Python

graph = {
    'Alice': ['Bob', 'Charlie'],
    'Bob': ['Alice'],
    'Charlie': ['Alice']
}
# Add 'David' with friends ['Alice', 'Charlie'] to graph
# Your code here

Hint

Use graph['David'] = ['Alice', 'Charlie'] to add a new entry to the dictionary.

3

Update connections for existing nodes

Add 'David' to the friend lists of 'Alice' and 'Charlie' in the graph dictionary

DSA Python

graph = {
    'Alice': ['Bob', 'Charlie'],
    'Bob': ['Alice'],
    'Charlie': ['Alice']
}
graph['David'] = ['Alice', 'Charlie']
# Add 'David' to Alice's and Charlie's friend lists
# Your code here

Hint

Use the append method to add 'David' to the lists of 'Alice' and 'Charlie'.

4

Print the final adjacency list

Print the graph dictionary to show the final adjacency list

DSA Python

graph = {
    'Alice': ['Bob', 'Charlie'],
    'Bob': ['Alice'],
    'Charlie': ['Alice']
}
graph['David'] = ['Alice', 'Charlie']
graph['Alice'].append('David')
graph['Charlie'].append('David')
# Print the graph dictionary
# Your code here

Hint

Use print(graph) to display the adjacency list.

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