Adjacency List Representation in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of adjacency list after adding edges

What is the printed adjacency list after running the following C code that adds edges to an undirected graph?

DSA C

#include <stdio.h>
#include <stdlib.h>

#define V 4

typedef struct Node {
    int dest;
    struct Node* next;
} Node;

Node* createNode(int dest) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

void addEdge(Node* adjList[], int src, int dest) {
    Node* newNode = createNode(dest);
    newNode->next = adjList[src];
    adjList[src] = newNode;

    newNode = createNode(src);
    newNode->next = adjList[dest];
    adjList[dest] = newNode;
}

void printGraph(Node* adjList[]) {
    for (int i = 0; i < V; i++) {
        printf("%d: ", i);
        Node* temp = adjList[i];
        while (temp) {
            printf("%d -> ", temp->dest);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

int main() {
    Node* adjList[V] = {NULL};
    addEdge(adjList, 0, 1);
    addEdge(adjList, 0, 2);
    addEdge(adjList, 1, 2);
    addEdge(adjList, 2, 3);
    printGraph(adjList);
    return 0;
}

A

0: 2 -> 1 -> NULL
1: 2 -> 0 -> NULL
2: 3 -> 1 -> 0 -> NULL
3: 2 -> NULL

B

0: 1 -> 2 -> NULL
1: 0 -> 2 -> NULL
2: 1 -> 0 -> 3 -> NULL
3: 2 -> NULL

C

0: 2 -> 1 -> NULL
1: 0 -> 2 -> NULL
2: 3 -> 1 -> 0 -> NULL
3: 2 -> NULL

D

0: 1 -> 2 -> NULL
1: 2 -> 0 -> NULL
2: 3 -> 0 -> 1 -> NULL
3: 2 -> NULL

💡 Hint

Remember that new nodes are added at the head of the adjacency list for each vertex.

Each addEdge call inserts the new node at the front of the linked list for both source and destination vertices. So the adjacency list for vertex 0 will have 2 first, then 1, and so on.

🧠 Conceptual

intermediate

Number of edges in adjacency list

Given an undirected graph represented by an adjacency list with 5 vertices, the total number of nodes in all adjacency lists combined is 8. How many edges does the graph have?

A 5

B 8

C 16

D 4

💡 Hint

Each edge in an undirected graph appears twice in the adjacency list.

In an undirected graph, each edge is stored twice (once for each vertex it connects). So total nodes in adjacency lists = 2 * number_of_edges. Here, 8 = 2 * edges, so edges = 4.

🔧 Debug

advanced

Identify the error in adjacency list insertion

What error will occur when running this C code snippet that tries to add an edge to an adjacency list?

DSA C

typedef struct Node {
    int dest;
    struct Node* next;
} Node;

void addEdge(Node* adjList[], int src, int dest) {
    Node* newNode = malloc(sizeof(Node));
    newNode->dest = dest;
    newNode->next = adjList[src];
    adjList[src] = newNode;

    newNode->dest = src;
    newNode->next = adjList[dest];
    adjList[dest] = newNode;
}

A No error, code runs correctly

B Segmentation fault due to using the same node twice

C Compilation error: missing #include <stdlib.h>

D Memory leak due to not freeing nodes

💡 Hint

Look at how newNode is reused for both adjacency lists.

The code reuses the same node pointer newNode for both adjacency lists, overwriting its fields and causing both lists to point to the same node. This leads to undefined behavior and likely a segmentation fault.

❓ Predict Output

advanced

Output after removing an edge from adjacency list

What is the adjacency list printed after removing the edge between vertices 1 and 2 from the graph below?

DSA C

#include <stdio.h>
#include <stdlib.h>

#define V 3

typedef struct Node {
    int dest;
    struct Node* next;
} Node;

Node* createNode(int dest) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

void addEdge(Node* adjList[], int src, int dest) {
    Node* newNode = createNode(dest);
    newNode->next = adjList[src];
    adjList[src] = newNode;

    newNode = createNode(src);
    newNode->next = adjList[dest];
    adjList[dest] = newNode;
}

void removeEdge(Node* adjList[], int src, int dest) {
    Node **curr = &adjList[src];
    while (*curr && (*curr)->dest != dest) {
        curr = &(*curr)->next;
    }
    if (*curr) {
        Node* temp = *curr;
        *curr = temp->next;
        free(temp);
    }

    curr = &adjList[dest];
    while (*curr && (*curr)->dest != src) {
        curr = &(*curr)->next;
    }
    if (*curr) {
        Node* temp = *curr;
        *curr = temp->next;
        free(temp);
    }
}

void printGraph(Node* adjList[]) {
    for (int i = 0; i < V; i++) {
        printf("%d: ", i);
        Node* temp = adjList[i];
        while (temp) {
            printf("%d -> ", temp->dest);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

int main() {
    Node* adjList[V] = {NULL};
    addEdge(adjList, 0, 1);
    addEdge(adjList, 1, 2);
    addEdge(adjList, 0, 2);
    removeEdge(adjList, 1, 2);
    printGraph(adjList);
    return 0;
}

A

0: 2 -> 1 -> NULL
1: 0 -> NULL
2: 0 -> NULL

B

0: 1 -> 2 -> NULL
1: 2 -> NULL
2: 1 -> 0 -> NULL

C

0: 2 -> 1 -> NULL
1: 2 -> 0 -> NULL
2: 1 -> 0 -> NULL

D

0: 1 -> 2 -> NULL
1: 0 -> NULL
2: 0 -> NULL

💡 Hint

Removing edge 1-2 means removing 2 from 1's list and 1 from 2's list.

After removing edge 1-2, vertex 1's adjacency list only has 0, and vertex 2's adjacency list only has 0. Vertex 0 still has both 2 and 1 in its list.

🧠 Conceptual

expert

Memory complexity of adjacency list vs adjacency matrix

For a graph with V vertices and E edges, which statement about memory usage is correct?

A Adjacency list uses O(V^2) memory; adjacency matrix uses O(V + E) memory

B Both adjacency list and adjacency matrix use O(V + E) memory

C Adjacency list uses O(V + E) memory; adjacency matrix uses O(V^2) memory

D Both adjacency list and adjacency matrix use O(V^2) memory

💡 Hint

Adjacency matrix stores all possible edges, adjacency list stores only existing edges.

Adjacency matrix always uses memory proportional to V squared because it stores all possible edges. Adjacency list stores only existing edges plus vertices, so it uses memory proportional to V plus E.

Practice

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

easy

A. A list where each vertex stores its adjacent vertices

B. A matrix showing connections between vertices

C. A list of all vertices without edges

D. A list of edges only without vertices

Solution

1. Step 1: Understand adjacency list concept

   An adjacency list stores each vertex and the vertices it connects to directly.

2. Step 2: Compare with other representations

   Unlike adjacency matrix, adjacency list focuses on neighbors per vertex, not a full matrix.

3. Final Answer:

   A list where each vertex stores its adjacent vertices -> Option A

4. Quick Check:

   Adjacency list = vertex with neighbors [OK]

Hint: Adjacency list stores neighbors per vertex, not full matrix [OK]

Common Mistakes:

• Confusing adjacency list with adjacency matrix
• Thinking it stores only edges without vertices
• Assuming it lists vertices without connections

2. Which of the following is the correct C syntax to declare an adjacency list for a graph with 5 vertices using an array of pointers to linked lists?

easy

A. int* adjList[5];

B. int adjList[5][5];

C. struct Node adjList[5];

D. struct Node* adjList[5];

Solution

1. Step 1: Understand adjacency list declaration

   Adjacency list uses array of pointers to linked list nodes, so 'struct Node* adjList[5];' is correct.

2. Step 2: Check other options

   int adjList[5][5]; is adjacency matrix, C is array of structs (not pointers), A is array of int pointers (not nodes).

3. Final Answer:

   struct Node* adjList[5]; -> Option D

4. Quick Check:

   Array of pointers to nodes = correct adjacency list declaration [OK]

Hint: Adjacency list uses array of pointers to node structs [OK]

Common Mistakes:

• Using 2D array instead of array of pointers
• Declaring array of structs instead of pointers
• Using int pointers instead of node pointers

3. Given the following adjacency list representation code snippet for a graph with 3 vertices (0,1,2):

struct Node {
  int vertex;
  struct Node* next;
};

struct Node* adjList[3] = {NULL, NULL, NULL};

// Adding edge 0->1
struct Node* newNode = malloc(sizeof(struct Node));
newNode->vertex = 1;
newNode->next = adjList[0];
adjList[0] = newNode;

// Adding edge 0->2
newNode = malloc(sizeof(struct Node));
newNode->vertex = 2;
newNode->next = adjList[0];
adjList[0] = newNode;

// Adding edge 1->2
newNode = malloc(sizeof(struct Node));
newNode->vertex = 2;
newNode->next = adjList[1];
adjList[1] = newNode;

// Print adjacency list for vertex 0
struct Node* temp = adjList[0];
while(temp != NULL) {
  printf("%d -> ", temp->vertex);
  temp = temp->next;
}
printf("NULL\n");

What is the printed output?

medium

A. 1 -> 2 -> NULL

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

C. 2 -> 1 -> NULL

D. NULL

Solution

1. Step 1: Trace insertion order for vertex 0

   Edges 0->1 then 0->2 are added at head, so list is 2 -> 1 -> NULL.

2. Step 2: Understand print loop

   Prints vertices in order from head: 2 then 1, then NULL.

3. Final Answer:

   2 -> 1 -> NULL -> Option C

4. Quick Check:

   Last inserted edge appears first in adjacency list [OK]

Hint: New nodes added at head, so last added appears first [OK]

Common Mistakes:

• Assuming order is insertion order instead of reversed
• Printing vertex 0 itself in adjacency list
• Confusing NULL print format

4. Consider this buggy code snippet to add an edge from vertex u to v in an adjacency list:

void addEdge(struct Node* adjList[], int u, int v) {
  struct Node* newNode = malloc(sizeof(struct Node));
  newNode->vertex = v;
  newNode->next = NULL;
  adjList[u] = newNode;
}

What is the main problem with this code?

medium

A. It overwrites existing adjacency list for vertex u, losing previous edges

B. It does not allocate memory for newNode

C. It sets newNode->next incorrectly to itself

D. It does not assign vertex v to newNode

Solution

1. Step 1: Analyze pointer assignment

   Setting adjList[u] = newNode overwrites old list head, losing previous edges.

2. Step 2: Check linked list linking

   newNode->next is NULL, so no link to old list; old edges lost.

3. Final Answer:

   It overwrites existing adjacency list for vertex u, losing previous edges -> Option A

4. Quick Check:

   Overwriting head pointer loses old adjacency list [OK]

Hint: Always link new node to old head to keep edges [OK]

Common Mistakes:

• Not linking new node to existing list
• Forgetting to allocate memory
• Incorrectly setting next pointer

5. You have a directed graph with 4 vertices (0 to 3). You want to represent it using adjacency lists and add edges:
- 0 -> 1
- 0 -> 2
- 1 -> 2
- 2 -> 0
- 2 -> 3
- 3 -> 3

Which data structure and insertion method correctly represents this graph in C?

hard

A. Use 2D int array; set 1 for edges and 0 otherwise

B. Use array of pointers to Node structs; insert new nodes at head linking to old list

C. Use array of Node structs; overwrite each vertex's list on insertion

D. Use array of int pointers; store vertex numbers without linking

Solution

1. Step 1: Choose correct data structure

   Adjacency list uses array of pointers to linked nodes for each vertex.

2. Step 2: Insert edges properly

   Insert new nodes at head, linking to previous list to keep all edges.

3. Step 3: Check other options

   Use 2D int array; set 1 for edges and 0 otherwise is adjacency matrix, C overwrites lists losing edges, D lacks linking.

4. Final Answer:

   Use array of pointers to Node structs; insert new nodes at head linking to old list -> Option B

5. Quick Check:

   Array of pointers + head insertion = correct adjacency list [OK]

Hint: Use pointers array and link new nodes at head to keep edges [OK]

Common Mistakes:

• Using adjacency matrix instead of list
• Overwriting adjacency list on insertion
• Not linking nodes properly