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.

Practice

1. Which of the following best describes a vertex in a graph?

easy

A. A point or node representing an entity in the graph

B. A connection between two nodes

C. A path that starts and ends at the same node

D. A graph with no edges

Solution

1. Step 1: Understand the definition of vertex

   A vertex is a fundamental unit in a graph representing an entity or point.

2. Step 2: Differentiate vertex from edges and other terms

   Edges connect vertices; paths and graph types are different concepts.

3. Final Answer:

   A point or node representing an entity in the graph -> Option A

4. Quick Check:

   Vertex = node/entity [OK]

Hint: Vertices are the points or nodes in a graph [OK]

Common Mistakes:

• Confusing vertices with edges
• Thinking vertices are paths
• Mixing vertex with graph types

2. Which of the following is the correct way to represent a weighted edge from vertex u to vertex v with weight 5 in C struct?

easy

A. struct Edge { int u, v; }; struct Weight { int w; };

B. struct Edge { int u; int v; }; int weight = 5;

C. struct Edge { int u; int v; int weight; };

D. struct Edge { int u; int v; };

Solution

1. Step 1: Identify the correct struct fields for weighted edge

   A weighted edge needs source vertex, destination vertex, and weight as fields.

2. Step 2: Check struct syntax correctness

   struct Edge { int u; int v; int weight; }; correctly declares all three fields in one struct.

3. Final Answer:

   struct Edge { int u; int v; int weight; }; -> Option C

4. Quick Check:

   Weighted edge struct = u, v, weight [OK]

Hint: Weighted edges need u, v, and weight fields in one struct [OK]

Common Mistakes:

• Separating weight outside the edge struct
• Incorrect field order causing confusion
• Missing weight field

3. What is the output of the following code snippet that prints edges of a directed weighted graph?

typedef struct { int u; int v; int weight; } Edge;
Edge edges[] = { {0, 1, 10}, {1, 2, 20}, {2, 0, 30} };
int n = 3;
for (int i = 0; i < n; i++) {
    printf("%d -> %d (weight %d)\n", edges[i].u, edges[i].v, edges[i].weight);
}

medium

A. 0 -> 1 (weight 10)
1 -> 2 (weight 30)
2 -> 0 (weight 20)

B. 0 -> 1 (weight 10)
1 -> 2 (weight 20)
2 -> 0 (weight 30)

C. 0 -> 1 (weight 30)
1 -> 2 (weight 20)
2 -> 0 (weight 10)

D. 1 -> 0 (weight 10)
2 -> 1 (weight 20)
0 -> 2 (weight 30)

Solution

1. Step 1: Read the edges array values

   Edges are: (0,1,10), (1,2,20), (2,0,30).

2. Step 2: Trace the loop printing each edge

   Loop prints each edge in order with format "u -> v (weight w)".

3. Final Answer:

   0 -> 1 (weight 10) 1 -> 2 (weight 20) 2 -> 0 (weight 30) -> Option B

4. Quick Check:

   Print edges as stored = 0 -> 1 (weight 10) 1 -> 2 (weight 20) 2 -> 0 (weight 30) [OK]

Hint: Print edges in array order with their weights [OK]

Common Mistakes:

• Reversing u and v in print
• Mixing up weights between edges
• Printing edges in wrong order

4. Identify the error in this code snippet that tries to create an undirected graph edge list:

typedef struct { int u; int v; } Edge;
Edge edges[2];
edges[0].u = 0; edges[0].v = 1;
edges[1].u = 1; edges[1].v = 0;
// Print edges
for (int i = 0; i <= 2; i++) {
    printf("Edge from %d to %d\n", edges[i].u, edges[i].v);
}

medium

A. Edge direction is incorrect for undirected graph

B. Edges should have weight field

C. Edges array size should be 1, not 2

D. Loop condition should be i < 2, not i <= 2

Solution

1. Step 1: Check array size and loop bounds

   Edges array has size 2, valid indices are 0 and 1.

2. Step 2: Identify loop error

   Loop runs from i=0 to i=2 inclusive, which accesses edges[2] (out of bounds).

3. Final Answer:

   Loop condition should be i < 2, not i <= 2 -> Option D

4. Quick Check:

   Array size 2 means max index 1 [OK]

Hint: Loop index must be less than array size [OK]

Common Mistakes:

• Using <= instead of < in loop
• Assuming edges need weight for undirected
• Confusing edge direction in undirected graphs

5. You have a weighted undirected graph with vertices 0, 1, 2 and edges:
(0,1,4), (1,2,6), (0,2,5)
How many edges will be stored if you represent this graph using an edge list storing each edge only once?

medium

A. 3

B. 6

C. 2

D. 1

Solution

1. Step 1: Understand undirected edge storage

   In undirected graphs, each edge connects two vertices without direction, so store only one entry per edge.

2. Step 2: Count unique edges given

   Edges are (0,1), (1,2), (0,2) -- total 3 unique edges.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Undirected edges stored once = 3 [OK]

Hint: Undirected edges stored once, count unique pairs [OK]

Common Mistakes:

• Counting each edge twice
• Confusing directed with undirected storage
• Ignoring weights when counting edges