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 adjacency list in C.

DSA C

int [1][MAX_NODES][MAX_NODES];

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

Atree

Bgraph

CadjacencyList

DadjacencyMatrix

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'tree' as the variable name which is misleading.

Using a 1D array instead of 2D for adjacency matrix.

The adjacency matrix is a 2D array representing edges between nodes in a graph.

2fill in blank

medium

Complete the code to add an edge between two nodes in an undirected graph.

DSA C

graph[u][v] = 1;
graph[[1]][[2]] = 1;

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

Au

Bv

Cw

Dx

Attempts:

3 left

💡 Hint

Common Mistakes

Using the same node 'u' for both indices in the second line.

Using an unrelated variable like 'w' or 'x'.

For undirected graphs, edges are bidirectional, so we mark both graph[u][v] and graph[v][u] as 1.

3fill in blank

hard

Fix the error in the code that tries to detect cycles in a graph using DFS.

DSA C

if (visited[[1]] && parent != [1]) {
    return 1;
}

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

Anode

Bparent

Cneighbor

Dcurrent

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'parent' inside visited[] which is incorrect.

Using 'current' instead of the neighbor node.

The condition checks if the neighbor is visited and is not the parent to detect a cycle.

4fill in blank

hard

Fill the blank to complete the function that prints all neighbors of a node in an adjacency matrix.

DSA C

for (int [1] = 0; [1] < numNodes; [1]++) {
    if (adjList[node][[1]] == 1) {
        printf("%d ", [1]);
    }
}

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

AnumNodes

Bi

Cnode

Dj

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'node' or 'numNodes' as loop variables.

The loop variable 'i' is used to iterate over possible neighbors, check if adjList[node][i] == 1, and print i if connected.

5fill in blank

hard

Fill all three blanks to complete the code that initializes a graph with no edges.

DSA C

for (int [1] = 0; [1] < [2]; [1]++) {
    for (int [3] = 0; [3] < numNodes; [3]++) {
        graph[i][j] = 0;
    }
}

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

Ai

BnumNodes

Cj

Dnode

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'node' as a loop variable which is confusing.

Using inconsistent variable names for loops.

We use 'i' and 'j' as loop variables and 'numNodes' as the limit to initialize all edges to 0.

Practice

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

easy

A. Because trees are faster to traverse than graphs.

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

C. Because trees can only store numbers, not connections.

D. Because graphs use less memory than trees.

Solution

1. Step 1: Understand tree limitations

   Trees are hierarchical structures with no cycles and only one path between nodes.

2. Step 2: Understand graph capabilities

   Graphs can represent any connections including cycles, multiple edges, and complex relationships.

3. Final Answer:

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

4. Quick Check:

   Graphs model complex connections, trees cannot [OK]

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

Common Mistakes:

• Thinking trees can have cycles
• Believing graphs use less memory always
• Confusing data storage with structure

2. Which of the following is the correct syntax to declare an adjacency list for a graph in C?

easy

A. int graph(5,5);

B. int graph[5][5];

C. int graph[] = {5};

D. int* graph[5];

Solution

1. Step 1: Understand adjacency list representation

   An adjacency list uses an array of pointers to lists (or arrays) of neighbors.

2. Step 2: Match syntax to adjacency list

   "int* graph[5];" declares an array of 5 pointers to int, suitable for adjacency lists.

3. Final Answer:

   int* graph[5]; -> Option D

4. Quick Check:

   Adjacency list uses array of pointers [OK]

Hint: Adjacency list uses array of pointers in C [OK]

Common Mistakes:

• Using 2D array for adjacency list (it's adjacency matrix)
• Incorrect array declaration syntax
• Confusing arrays with function calls

3. Consider the following C code snippet representing a graph adjacency matrix. What will be the output?

int graph[3][3] = {
  {0, 1, 0},
  {1, 0, 1},
  {0, 1, 0}
};

for(int i = 0; i < 3; i++) {
  for(int j = 0; j < 3; j++) {
    if(graph[i][j] == 1) {
      printf("%d -> %d\n", i, j);
    }
  }
}

medium

A. No output

B. 0 -> 1
1 -> 2
2 -> 0

C. 0 -> 1
1 -> 0
1 -> 2
2 -> 1

D. 0 -> 0
1 -> 1
2 -> 2

Solution

1. Step 1: Analyze adjacency matrix values

   Positions with 1 indicate edges: (0,1), (1,0), (1,2), (2,1).

2. Step 2: Trace nested loops printing edges

   Loops print edges where graph[i][j] == 1, so output lines are 0->1, 1->0, 1->2, 2->1.

3. Final Answer:

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

4. Quick Check:

   Edges printed match adjacency matrix 1s [OK]

Hint: Print edges where adjacency matrix value is 1 [OK]

Common Mistakes:

• Ignoring symmetric edges
• Printing zeros as edges
• Confusing indices i and j

4. The following code attempts to create a graph with cycles using a tree structure. What is the main issue?

struct Node {
  int val;
  struct Node* left;
  struct Node* right;
};

// Trying to link nodes to form a cycle
node1->left = node2;
node2->left = node3;
node3->left = node1; // cycle created here

medium

A. Trees cannot have cycles, so this creates an invalid structure.

B. The pointers are not initialized properly causing segmentation fault.

C. The code will compile but not run because of missing return statements.

D. There is no issue; trees can have cycles.

Solution

1. Step 1: Understand tree structure rules

   Trees must not have cycles; each node has exactly one parent except root.

2. Step 2: Identify cycle creation in code

   Linking node3 back to node1 creates a cycle, violating tree properties.

3. Final Answer:

   Trees cannot have cycles, so this creates an invalid structure. -> Option A

4. Quick Check:

   Cycle in tree structure is invalid [OK]

Hint: Trees cannot contain cycles; cycles break tree rules [OK]

Common Mistakes:

• Thinking cycles are allowed in trees
• Confusing compile errors with logical errors
• Ignoring pointer initialization

5. You want to model a social network where users can be friends with multiple users, including mutual friendships and groups. Which data structure best models this, and why can't a tree be used here?

hard

A. Graph, because it supports cycles and multiple connections between nodes.

B. Tree, because it is simpler and faster for all connections.

C. Array, because it stores all users in order.

D. Linked list, because it can represent multiple friendships easily.

Solution

1. Step 1: Identify social network connection needs

   Users can have multiple friends, mutual connections, and cycles (friend loops).

2. Step 2: Match data structure capabilities

   Graphs support cycles and multiple edges; trees cannot have cycles or multiple parents.

3. Final Answer:

   Graph, because it supports cycles and multiple connections between nodes. -> Option A

4. Quick Check:

   Social networks need graphs, not trees [OK]

Hint: Use graphs for mutual and multiple connections [OK]

Common Mistakes:

• Choosing tree for cyclic relationships
• Confusing arrays or lists with graph structures
• Ignoring mutual friendship cycles