Graph Terminology Vertices Edges Directed Undirected Weighted in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare a graph vertex as an integer variable named 'vertex'.

DSA C++

int [1] = 5;

Drag options to blanks, or click blank then click option'

Aedge

Bvertex

Cweight

Dnode

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'edge' or 'weight' as variable name for a vertex.

The variable representing a graph vertex is commonly named 'vertex'.

2fill in blank

medium

Complete the code to add an edge between two vertices u and v in an undirected graph using adjacency list.

DSA C++

adjacencyList[u].push_back([1]);

Drag options to blanks, or click blank then click option'

Aedge

Bu

Cweight

Dv

Attempts:

3 left

💡 Hint

Common Mistakes

Pushing u instead of v, or pushing weight instead of vertex.

To add an edge from vertex u to vertex v, we push v into u's adjacency list.

3fill in blank

hard

Fix the error in the code to correctly represent a weighted directed edge from u to v with weight w.

DSA C++

adjacencyList[u].push_back(std::make_pair([1], [2]));

Drag options to blanks, or click blank then click option'

Av

Bu

Cw

Dweight

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping u and v, or using u as destination vertex.

For a weighted directed graph, we add a pair of (vertex, weight) to adjacency list of u.

4fill in blank

hard

Fill both blanks to check if an edge from vertex u to vertex v exists in an undirected graph adjacency list.

DSA C++

for (auto [1] : adjacencyList[u]) {
    if ([2] == v) {
        return true;
    }
}

Drag options to blanks, or click blank then click option'

Aneighbor

Bvertex

Dedge

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variable names inconsistently.

We iterate over neighbors of u and check if any neighbor equals v.

5fill in blank

hard

Fill all three blanks to create a weighted undirected edge between u and v with weight w in adjacency list.

DSA C++

adjacencyList[u].push_back(std::make_pair([1], [2]));
adjacencyList[[3]].push_back(std::make_pair(u, w));

Drag options to blanks, or click blank then click option'

Av

Bw

Du

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong vertex in second push_back or missing weight.

For undirected weighted graphs, add edge (v, w) to u's list and (u, w) to v's list.

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