Why Graphs Exist and What Trees Cannot Model in DSA Python - Test Your Knowledge

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a graph using an adjacency list.

DSA Python

graph = {}
graph['A'] = ['B', 'C']
graph['B'] = ['A', [1]]
graph['C'] = ['A']
print(graph)

Drag options to blanks, or click blank then click option'

A'B'

B'D'

C'E'

D'C'

Attempts:

3 left

💡 Hint

Common Mistakes

Adding a node that is not connected to 'B'.

Using the wrong syntax for list elements.

The adjacency list for node 'B' should include 'C' to represent the edge between B and C.

2fill in blank

medium

Complete the code to check if an edge exists between two nodes in a graph.

DSA Python

def has_edge(graph, node1, node2):
    return [1] in graph.get(node1, [])

Drag options to blanks, or click blank then click option'

Anode1

Bnode2

Cgraph

Dnode3

Attempts:

3 left

💡 Hint

Common Mistakes

Checking if node1 is in its own adjacency list.

Using a variable not defined in the function.

To check if an edge exists from node1 to node2, we check if node2 is in the adjacency list of node1.

3fill in blank

hard

Fix the error in the code that tries to add an edge between two nodes in an undirected graph.

DSA Python

def add_edge(graph, node1, node2):
    if node1 not in graph:
        graph[node1] = []
    if node2 not in graph:
        graph[node2] = []
    graph[node1].append(node2)
    [1].append(node1)

Drag options to blanks, or click blank then click option'

Anode2

Bgraph[node1]

Cgraph[node2]

Dnode1

Attempts:

3 left

💡 Hint

Common Mistakes

Appending to the wrong adjacency list.

Appending the wrong node.

To add an undirected edge, we add node1 to node2's adjacency list and node2 to node1's adjacency list. The second append should be to graph[node2].

4fill in blank

hard

Fill both blanks to create a function that counts the number of edges connected to a node in a graph.

DSA Python

def count_edges(graph, node):
    if node not in graph:
        return 0
    return len(graph[1])

Drag options to blanks, or click blank then click option'

A[node]

B{node}

C(node)

D<node>

Attempts:

3 left

💡 Hint

Common Mistakes

Using parentheses or braces instead of square brackets.

Using angle brackets which are invalid syntax.

The adjacency list is accessed using square brackets with the node as the key: graph[node].

5fill in blank

hard

Fill all three blanks to create a function that returns all neighbors of a node that have a value greater than a threshold.

DSA Python

def neighbors_above_threshold(graph, node, threshold):
    return [neighbor for neighbor in graph[1] if neighbor [2] threshold]

result = neighbors_above_threshold(graph, 'A', [3])
print(result)

Drag options to blanks, or click blank then click option'

A[node]

B>

C5

D(node)

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong brackets for dictionary access.

Using incorrect comparison operators.

Passing threshold as a string instead of a number.

The function accesses neighbors with graph[node], filters neighbors greater than threshold using >, and calls the function with threshold 5.

Practice

1. Why do we need graphs when we already have trees in data structures?

easy

A. Because graphs use less memory than trees.

B. Because trees are faster to traverse than graphs.

C. Because graphs can represent connections between nodes in any pattern, including cycles and multiple parents.

D. Because trees can only store numbers, but graphs can store any data.

Solution

1. Step 1: Understand tree limitations

   Trees have a strict hierarchy: each node has only one parent and no cycles.

2. Step 2: Understand graph capabilities

   Graphs allow nodes to connect in any way, including cycles and multiple parents.

3. Final Answer:

   Because graphs can represent connections between nodes in any pattern, including cycles and multiple parents. -> Option C

4. Quick Check:

   Graphs model complex connections unlike trees [OK]

Hint: Graphs allow cycles and multiple parents; trees do not [OK]

Common Mistakes:

• Thinking trees can have cycles
• Confusing data types stored with structure type
• Assuming graphs always use less memory

2. Which of the following is the correct way to represent an undirected graph using adjacency lists in Python?

easy

A. graph = [[1, 2], [2, 3], [3, 1]]

B. graph = {1: (2, 3), 2: (1), 3: (1)}

C. graph = {1: 2, 2: 3, 3: 1}

D. graph = {1: [2, 3], 2: [1], 3: [1]}

Solution

1. Step 1: Understand adjacency list format

   Adjacency lists use a dictionary with keys as nodes and values as lists of connected nodes.

2. Step 2: Check each option

   graph = {1: [2, 3], 2: [1], 3: [1]} uses dictionary with lists correctly; others use tuples, lists of pairs, or single values incorrectly.

3. Final Answer:

   graph = {1: [2, 3], 2: [1], 3: [1]} -> Option D

4. Quick Check:

   Adjacency list = dict with lists [OK]

Hint: Adjacency lists use dict keys with list values [OK]

Common Mistakes:

• Using tuples instead of lists for adjacency
• Using list of pairs instead of dict
• Assigning single node instead of list

3. What will be the output of the following Python code that models a graph?

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

medium

A. 2

B. 1

C. 3

D. Error

Solution

1. Step 1: Analyze graph dictionary

   Node 2 connects to nodes 1 and 3, so graph[2] = [1, 3].

2. Step 2: Calculate length of adjacency list

   Length of graph[2] is 2 because it has two connected nodes.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   len([1, 3]) = 2 [OK]

Hint: Count connected nodes in adjacency list [OK]

Common Mistakes:

• Counting total nodes instead of neighbors
• Confusing keys with values
• Expecting error due to syntax

4. The following code tries to add an edge between nodes in an undirected graph but has a bug. What is the bug?

graph = {1: [2], 2: [1]}
def add_edge(u, v):
    graph[u].append(v)
    graph[v].append(u)

add_edge(2, 3)
print(graph)

medium

A. Node 3 is not initialized in the graph before adding edges.

B. The append method is used incorrectly.

C. The graph dictionary should use sets instead of lists.

D. The function add_edge should return the graph.

Solution

1. Step 1: Check graph initialization

   Node 3 does not exist in graph keys before add_edge is called.

2. Step 2: Understand append behavior

   Appending to graph[v] fails because graph[3] key is missing, causing KeyError.

3. Final Answer:

   Node 3 is not initialized in the graph before adding edges. -> Option A

4. Quick Check:

   Missing key causes error [OK]

Hint: Initialize nodes before adding edges [OK]

Common Mistakes:

• Assuming append works without key
• Thinking return needed in add_edge
• Confusing list vs set usage

5. Given a tree structure, which of the following scenarios can only be correctly modeled by converting it into a graph?

hard

A. Representing a family tree where each child has exactly one parent.

B. Modeling a social network where users can follow each other mutually or one-way.

C. Storing a file directory where each folder has a single parent folder.

D. Organizing a company's hierarchy with clear reporting lines.

Solution

1. Step 1: Analyze tree modeling scenarios

   Family trees, file directories, and company hierarchies have strict parent-child relations, fitting trees.

2. Step 2: Analyze graph necessity

   Social networks have complex connections, including cycles and mutual or one-way links, needing graphs.

3. Final Answer:

   Modeling a social network where users can follow each other mutually or one-way. -> Option B

4. Quick Check:

   Complex connections need graphs [OK]

Hint: Use graphs for mutual or cyclic connections [OK]

Common Mistakes:

• Thinking family trees need graphs
• Confusing hierarchy with network
• Assuming all parent-child fit graphs only