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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of adjacency list for an undirected weighted graph

What is the printed adjacency list after running this C++ code for an undirected weighted graph with 3 vertices and edges (0-1, weight 5), (1-2, weight 3)?

DSA C++

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int V = 3;
    vector<vector<pair<int,int>>> adj(V);
    adj[0].push_back({1, 5});
    adj[1].push_back({0, 5});
    adj[1].push_back({2, 3});
    adj[2].push_back({1, 3});

    for (int i = 0; i < V; i++) {
        cout << i << ": ";
        for (auto &edge : adj[i]) {
            cout << "(" << edge.first << "," << edge.second << ") ";
        }
        cout << "\n";
    }
    return 0;
}

A

0: (1,5) 
1: (0,5) (2,3) 
2: (1,3) 

B

0: (1,5) (2,3) 
1: (0,5) 
2: (1,3) 

C

0: (1,5) 
1: (2,3) 
2: (0,5) (1,3) 

D

0: (0,5) 
1: (1,3) 
2: (2,3) 

💡 Hint

Remember that undirected edges are added in both directions with the same weight.

The adjacency list stores neighbors and weights. For undirected edges, both vertices list each other with the same weight.

❓ Predict Output

intermediate

Output of adjacency matrix for a directed graph

What is the printed adjacency matrix after running this C++ code for a directed graph with 3 vertices and edges 0->1 and 1->2?

DSA C++

#include <iostream>
using namespace std;

int main() {
    int V = 3;
    int adj[3][3] = {0};
    adj[0][1] = 1;
    adj[1][2] = 1;

    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            cout << adj[i][j] << " ";
        }
        cout << "\n";
    }
    return 0;
}

A

0 1 0 
0 0 1 
0 0 0 

B

0 0 0 
1 0 0 
0 1 0 

C

1 0 0 
0 1 0 
0 0 1 

D

0 1 1 
0 0 1 
0 0 0 

💡 Hint

In adjacency matrix for directed graphs, adj[i][j] = 1 means edge from i to j.

Only edges 0->1 and 1->2 are set to 1, others remain 0.

🧠 Conceptual

advanced

Identify the graph type from description

Which of the following best describes a graph where edges have directions and weights?

A Undirected unweighted graph

B Directed weighted graph

C Undirected weighted graph

D Directed unweighted graph

💡 Hint

Edges have arrows and numbers representing cost or distance.

Directed weighted graph means edges have direction and weights.

❓ Predict Output

advanced

Output of BFS traversal on a directed graph

What is the order of vertices printed by this BFS traversal starting from vertex 0?

DSA C++

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void bfs(int start, vector<vector<int>> &adj) {
    vector<bool> visited(adj.size(), false);
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int v = q.front(); q.pop();
        cout << v << " ";
        for (int u : adj[v]) {
            if (!visited[u]) {
                visited[u] = true;
                q.push(u);
            }
        }
    }
}

int main() {
    vector<vector<int>> adj = {
        {1, 2},
        {2},
        {3},
        {}
    };
    bfs(0, adj);
    return 0;
}

A 0 2 1 3

B 0 1 3 2

C 0 1 2 3

D 0 3 2 1

💡 Hint

BFS visits neighbors level by level in order they appear.

Starting at 0, neighbors 1 and 2 are visited in order, then 3 from 2.

🧠 Conceptual

expert

Number of edges in a complete undirected weighted graph with 5 vertices

How many edges are there in a complete undirected weighted graph with 5 vertices?

A 25

B 20

C 5

D 10

💡 Hint

Complete undirected graph has edges between every pair of vertices without duplicates.

Number of edges = n*(n-1)/2 = 5*4/2 = 10.

Practice

1. In a graph, what do we call the points or nodes where edges meet?

easy

A. Edges

B. Vertices

C. Weights

D. Paths

Solution

1. Step 1: Understand graph components

   A graph consists of points called vertices and connections called edges.

2. Step 2: Identify the term for points

   The points or nodes where edges meet are called vertices.

3. Final Answer:

   Vertices -> Option B

4. Quick Check:

   Points in graph = Vertices [OK]

Hint: Vertices are the dots, edges are the lines connecting them [OK]

Common Mistakes:

• Confusing edges with vertices
• Thinking weights are points
• Mixing paths with vertices

2. Which of the following is the correct way to declare an undirected graph using adjacency list in C++?

easy

A. vector graph; graph.resize(5); // Undirected graph

B. vector> graph[5]; // Weighted graph

C. int graph[5][5]; // Undirected graph

D. vector<int> graph(5); // Undirected graph

Solution

1. Step 1: Understand adjacency list declaration

   An adjacency list for a graph with 5 vertices can be declared as a vector of vectors and resized to 5.

2. Step 2: Check options for correct syntax

   vector graph; graph.resize(5); // Undirected graph uses vector graph; graph.resize(5); which is correct for undirected graph adjacency list.

3. Final Answer:

   vector graph; graph.resize(5); // Undirected graph -> Option A

4. Quick Check:

   Correct adjacency list syntax = vector graph; graph.resize(5); // Undirected graph [OK]

Hint: Use vector of vectors and resize for adjacency list [OK]

Common Mistakes:

• Using fixed size array without resize
• Confusing weighted graph syntax
• Using vector<int> graph(5) which is vector of ints, not list

3. What is the output of the following C++ code snippet that creates a weighted directed graph and prints the weight of edge from vertex 1 to 2?

vector> graph[3];
graph[1].push_back({2, 10});
graph[2].push_back({1, 5});
for(auto &edge : graph[1]) {
    if(edge.first == 2) {
        cout << edge.second << endl;
    }
}

medium

A. 0

B. 5

C. 10

D. Compilation error

Solution

1. Step 1: Understand graph construction

   graph[1] has an edge to vertex 2 with weight 10; graph[2] has edge to 1 with weight 5.

2. Step 2: Trace the loop output

   The loop checks edges from vertex 1; finds edge to 2 and prints weight 10.

3. Final Answer:

   10 -> Option C

4. Quick Check:

   Weight from 1 to 2 = 10 [OK]

Hint: Check which vertex's edges are printed and their weights [OK]

Common Mistakes:

• Confusing edge direction
• Printing weight from wrong vertex
• Assuming undirected graph

4. Identify the error in the following code snippet that tries to add an edge to an undirected weighted graph:

vector> graph[3];
graph[0].push_back({1, 4});
graph[1].push_back(0, 4);

medium

A. Using vector instead of list

B. Graph size is too small

C. Edge weight missing

D. Incorrect syntax in push_back for second edge

Solution

1. Step 1: Check push_back usage

   push_back expects a single argument; graph[1].push_back(0, 4) is invalid syntax.

2. Step 2: Identify correct syntax

   It should be graph[1].push_back({0, 4}); to add a pair.

3. Final Answer:

   Incorrect syntax in push_back for second edge -> Option D

4. Quick Check:

   push_back needs one argument (pair) [OK]

Hint: push_back takes one argument; use braces for pairs [OK]

Common Mistakes:

• Passing multiple arguments to push_back
• Not using braces for pair
• Confusing vector size with error

5. You have a weighted undirected graph represented as an adjacency list:

vector> graph[4];
graph[0].push_back({1, 3});
graph[1].push_back({0, 3});
graph[1].push_back({2, 5});
graph[2].push_back({1, 5});
graph[2].push_back({3, 7});
graph[3].push_back({2, 7});

How would you add an edge between vertex 0 and vertex 3 with weight 2 correctly?

hard

A. graph[0].push_back({3, 2}); graph[3].push_back({0, 2});

B. graph[0].push_back({3, 2});

C. graph[3].push_back({0, 2});

D. graph.push_back({0, 3, 2});

Solution

1. Step 1: Understand undirected edge addition

   In undirected graphs, edges must be added in both directions to represent connection.

2. Step 2: Add edge in both adjacency lists

   Add {3, 2} to graph[0] and {0, 2} to graph[3] to represent the edge with weight 2.

3. Final Answer:

   graph[0].push_back({3, 2}); graph[3].push_back({0, 2}); -> Option A

4. Quick Check:

   Undirected edge = add both directions [OK]

Hint: Add edges both ways for undirected weighted graph [OK]

Common Mistakes:

• Adding edge only one way
• Wrong syntax for push_back
• Trying to push triple instead of pair