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

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare a graph using adjacency list representation.

DSA C++

std::vector<std::vector<int>> graph([1]);

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

Avector

B5

Cint

Dmap

Attempts:

3 left

💡 Hint

Common Mistakes

Using data types instead of size

Confusing vector with map

The number 5 initializes the graph with 5 nodes, creating an adjacency list for each node.

2fill in blank

medium

Complete the code to add an edge from node 1 to node 2 in the graph.

DSA C++

graph[[1]].push_back(2);

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

A1

B3

C2

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 instead of 1

Adding edge to wrong node

Index 1 represents node 1, so adding 2 to its adjacency list creates an edge from node 1 to node 2.

3fill in blank

hard

Fix the error in the code to correctly check if a graph has a cycle using DFS.

DSA C++

if (visited[node] == [1]) return true;

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

A0

B2

C1

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Checking for 0 instead of 1

Using -1 which is invalid

Visited state 1 means the node is currently in the recursion stack, indicating a cycle if revisited.

4fill in blank

hard

Fill both blanks to complete the code that distinguishes a tree from a graph.

DSA C++

bool isTree = (edges == nodes - 1) && !graph.[1]();

bool hasCycle = graph.[2]();

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

AhasCycle

BisConnected

CdetectCycle

DisEmpty

Attempts:

3 left

💡 Hint

Common Mistakes

Confusing cycle detection with connectivity

Using wrong method names

A tree must be connected (isConnected) and have no cycles (detectCycle).

5fill in blank

hard

Fill all three blanks to complete the code that models a graph with cycles and multiple parents.

DSA C++

graph[[1]].push_back([2]);

if (graph[[3]].size() > 1) {
    // Node has multiple parents
}

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

A1

B2

C3

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing source and destination nodes

Checking wrong node for multiple parents

Adding an edge from node 1 to 2, then checking if node 2 has multiple parents by size of adjacency list.

Practice

1. Why do we need graphs when trees already exist as data structures?

easy

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

B. Because trees are faster to traverse than graphs.

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

D. Because graphs use less memory than trees.

Solution

1. Step 1: Understand tree limitations

   Trees are hierarchical and cannot have cycles or multiple parents for a node.

2. Step 2: Understand graph capabilities

   Graphs allow cycles and multiple connections between nodes, modeling complex relationships.

3. Final Answer:

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

4. Quick Check:

   Graphs model cycles and complex links = B [OK]

Hint: Graphs allow cycles; trees do not. Remember this difference [OK]

Common Mistakes:

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

2. Which of the following is the correct way to declare an undirected graph using adjacency list in C++?

easy

A. int graph[n][n];

B. std::vector<int> graph[n];

C. std::map graph;

D. std::vector graph(n);

Solution

1. Step 1: Identify adjacency list declaration

   Adjacency list uses vector of vectors or array of vectors to store neighbors.

2. Step 2: Check options

   std::vector graph(n); uses vector of vectors with size n, suitable for adjacency list.

3. Final Answer:

   std::vector graph(n); -> Option D

4. Quick Check:

   Adjacency list = vector of vectors [OK]

Hint: Use vector of vectors for adjacency list in modern C++ [OK]

Common Mistakes:

• Using map which is not adjacency list
• Using 2D array which is adjacency matrix
• Using vector<int> graph[n]; which is legacy C++

3. Consider the following C++ code snippet for an undirected graph:

std::vector graph(3);
graph[0].push_back(1);
graph[1].push_back(0);
graph[1].push_back(2);
graph[2].push_back(1);

for (int i = 0; i < 3; i++) {
    std::cout << i << ": ";
    for (int neighbor : graph[i]) {
        std::cout << neighbor << " ";
    }
    std::cout << std::endl;
}

What is the output?

medium

A. 0: 1
1: 0
2: 1 2

B. 0: 1
1: 2
2: 1 0

C. 0: 1
1: 0 2
2: 1

D. 0: 0 1
1: 0 2
2: 1

Solution

1. Step 1: Trace graph construction

   graph[0] has 1, graph[1] has 0 and 2, graph[2] has 1.

2. Step 2: Trace output loop

   Print neighbors for each node: 0->1, 1->0 2, 2->1.

3. Final Answer:

   0: 1 1: 0 2 2: 1 -> Option C

4. Quick Check:

   Adjacency list print matches 0: 1 1: 0 2 2: 1 [OK]

Hint: Follow push_back calls to build adjacency list [OK]

Common Mistakes:

• Mixing order of neighbors
• Confusing adjacency list with matrix output
• Missing symmetric edges in undirected graph

4. The following code attempts to add an edge in an undirected graph but has a bug:

void addEdge(std::vector& graph, int u, int v) {
    graph[u].push_back(v);
}

What is the bug and how to fix it?

medium

A. It should clear graph[u] before adding; fix by calling clear() first.

B. It adds edge only one way; fix by adding graph[v].push_back(u);

C. It uses push_back incorrectly; fix by using insert instead.

D. It should use graph[u][v] = 1; fix by using adjacency matrix.

Solution

1. Step 1: Identify undirected graph edge addition

   Undirected edges must be added both ways: u->v and v->u.

2. Step 2: Find missing edge addition

   Code adds only u->v, missing v->u, so add graph[v].push_back(u); to fix.

3. Final Answer:

   It adds edge only one way; fix by adding graph[v].push_back(u); -> Option B

4. Quick Check:

   Undirected edge needs both directions = C [OK]

Hint: Add edges both ways for undirected graphs [OK]

Common Mistakes:

• Adding edge only one way
• Using wrong vector method
• Confusing adjacency list with matrix

5. Which of the following real-world problems cannot be modeled by a tree but can be modeled by a graph?

medium

A. A social network where people can be friends with multiple others, including mutual friendships.

B. A company's organizational chart with one CEO and clear hierarchy.

C. A family tree showing parent-child relationships.

D. A file directory structure on a computer.

Solution

1. Step 1: Analyze tree model examples

   Family trees, org charts, and file directories are hierarchical with no cycles.

2. Step 2: Analyze social network structure

   Social networks have cycles and multiple connections, not fitting tree structure.

3. Final Answer:

   A social network where people can be friends with multiple others, including mutual friendships. -> Option A

4. Quick Check:

   Cycles and multiple links need graphs = A [OK]

Hint: Cycles and multiple parents mean graph, not tree [OK]

Common Mistakes:

• Thinking family trees have cycles
• Confusing hierarchy with network connections
• Assuming all relationships are one-to-one