Why Graph Terminology Vertices Edges Directed Undirected Weighted in DSA C++?

The Big Idea

Discover how simple terms like vertices and edges unlock powerful ways to solve complex connection puzzles!

The Scenario

Imagine you want to map out all the roads connecting cities on a map by hand. You try to list every city and every road, but it quickly becomes confusing to track which cities connect and how.

The Problem

Manually keeping track of connections between many cities is slow and error-prone. You might forget a road or mix up directions, making it hard to answer questions like "Can I get from city A to city B?" or "Which roads are one-way?"

The Solution

Graphs use clear terms like vertices (cities) and edges (roads) to organize connections. Directed edges show one-way roads, undirected edges show two-way roads, and weighted edges add distances or costs. This structure helps computers quickly understand and work with complex connections.

Before vs After

✗ Before

string graph[100][100]; // manually fill connections
// hard to track direction and weights

✓ After

struct Edge { int to; int weight; };
vector<Edge> graph[100]; // clear, easy to manage directions and weights;

What It Enables

Graphs let us model and solve real-world connection problems like navigation, social networks, and resource flows efficiently.

Real Life Example

GPS apps use graphs to represent cities (vertices) and roads (edges), including one-way streets (directed edges) and distances (weights), to find the fastest route.

Key Takeaways

Vertices represent points or objects.

Edges represent connections, which can be directed or undirected.

Weights add extra info like distance or cost to edges.

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