Graph Terminology Vertices Edges Directed Undirected Weighted in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of adjacency list for directed weighted graph

What is the printed adjacency list after running the code below for a directed weighted graph?

DSA C

typedef struct Edge {
    int dest;
    int weight;
    struct Edge* next;
} Edge;

typedef struct Vertex {
    int id;
    Edge* edges;
} Vertex;

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

void add_edge(Vertex* graph, int src, int dest, int weight) {
    Edge* new_edge = (Edge*)malloc(sizeof(Edge));
    new_edge->dest = dest;
    new_edge->weight = weight;
    new_edge->next = graph[src].edges;
    graph[src].edges = new_edge;
}

void print_graph(Vertex* graph, int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ->", graph[i].id);
        Edge* temp = graph[i].edges;
        while (temp) {
            printf(" %d(weight=%d)", temp->dest, temp->weight);
            temp = temp->next;
        }
        printf(" -> NULL\n");
    }
}

int main() {
    int n = 3;
    Vertex graph[3];
    for (int i = 0; i < n; i++) {
        graph[i].id = i;
        graph[i].edges = NULL;
    }
    add_edge(graph, 0, 1, 5);
    add_edge(graph, 0, 2, 3);
    add_edge(graph, 1, 2, 2);
    print_graph(graph, n);
    return 0;
}

A

0 -> NULL
1 -> 2(weight=2) -> NULL
2 -> 0(weight=3) 1(weight=5) -> NULL

B

0 -> 1(weight=5) 2(weight=3) -> NULL
1 -> 2(weight=2) -> NULL
2 -> NULL

C

0 -> 1(weight=5) -> NULL
1 -> 2(weight=2) 0(weight=3) -> NULL
2 -> NULL

D

0 -> 2(weight=3) 1(weight=5) -> NULL
1 -> 2(weight=2) -> NULL
2 -> NULL

💡 Hint

Remember edges are added at the head of the linked list, so the last added edge appears first.

Edges are added to the head of the adjacency list, so the last edge added from 0 is to 2 with weight 3, then to 1 with weight 5. Vertex 1 has one edge to 2 with weight 2. Vertex 2 has no edges.

🧠 Conceptual

intermediate

Number of edges in an undirected graph

If an undirected graph has 5 vertices and each vertex is connected to every other vertex, how many edges does the graph have?

A 20

B 10

C 5

D 15

💡 Hint

In an undirected graph, each edge connects two vertices and is counted once.

A complete undirected graph with n vertices has n*(n-1)/2 edges. For 5 vertices, edges = 5*4/2 = 10.

🔧 Debug

advanced

Identify error in directed graph edge addition

What error will occur when running the code below that tries to add an edge in a directed graph?

DSA C

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

typedef struct Vertex {
    int id;
    Edge* edges;
} Vertex;

void add_edge(Vertex* graph, int src, int dest) {
    Edge* new_edge = malloc(sizeof(Edge));
    new_edge->dest = dest;
    new_edge->next = graph[dest].edges;
    graph[src].edges = new_edge;
}

int main() {
    Vertex graph[2];
    graph[0].edges = NULL;
    graph[1].edges = NULL;
    add_edge(graph, 0, 1);
    return 0;
}

A No error, runs correctly

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

C Segmentation fault due to incorrect next pointer assignment

D Memory leak due to missing free()

💡 Hint

Check which vertex's edges list is used for the new edge's next pointer.

The new edge's next pointer is incorrectly set to graph[dest].edges instead of graph[src].edges, corrupting the adjacency list and likely causing a segmentation fault.

❓ Predict Output

advanced

Output of adjacency matrix for weighted undirected graph

What is the printed adjacency matrix after running the code below for a weighted undirected graph?

DSA C

#include <stdio.h>

int main() {
    int n = 3;
    int matrix[3][3] = {0};
    matrix[0][1] = 4;
    matrix[1][0] = 4;
    matrix[1][2] = 7;
    matrix[2][1] = 7;
    matrix[0][2] = 0;
    matrix[2][0] = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }
    return 0;
}

A

0 4 0 
4 0 7 
0 7 0 

B

0 0 0 
4 0 7 
0 7 0 

C

0 4 0 
0 0 7 
0 7 0 

D

0 4 7 
4 0 7 
7 7 0 

💡 Hint

Remember adjacency matrix for undirected graph is symmetric.

Edges between 0-1 and 1-2 have weights 4 and 7 respectively, symmetric in matrix. No edge between 0-2 means 0 entries.

🧠 Conceptual

expert

Minimum edges for strongly connected directed graph

What is the minimum number of edges required to make a directed graph with 4 vertices strongly connected?

A 4

B 6

C 3

D 12

💡 Hint

Strongly connected means every vertex reachable from every other vertex.

A directed cycle connecting all 4 vertices uses 4 edges and ensures strong connectivity. Fewer edges cannot connect all vertices strongly.