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.