Graph Terminology Vertices Edges Directed Undirected Weighted in DSA C++ - Build from Scratch

Graph Terminology: Vertices, Edges, Directed, Undirected, Weighted

📖 Scenario: Imagine you are creating a simple map of cities connected by roads. Each city is a point (vertex), and each road is a connection (edge) between cities. Some roads have directions (one-way), and some have distances (weights).

🎯 Goal: You will build a graph using C++ that shows cities as vertices and roads as edges. You will mark if roads are one-way (directed) or two-way (undirected), and add distances (weights) to roads.

📋 What You'll Learn

Create a list of city names as vertices

Create a list of edges connecting cities with direction and weight

Use a struct to represent edges with source, destination, and weight

Print the graph showing each edge with its direction and weight

💡 Why This Matters

🌍 Real World

Graphs are used to model maps, social networks, and many connections in real life.

💼 Career

Understanding graph basics is essential for software roles involving networking, route planning, and data relationships.

1

Create the list of cities (vertices)

Create a std::vector<std::string> called cities with these exact city names: "A", "B", "C", "D"

DSA C++

#include 
#include 
#include 

int main() {
    // Create vector cities with "A", "B", "C", "D"
    // Your code here

    return 0;
}

Hint

Use std::vector<std::string> and initialize it with the city names inside curly braces.

2

Define the edge structure and create edges

Define a struct Edge with int source, int destination, and int weight. Then create a std::vector<Edge> called edges with these exact edges: from city 0 to 1 with weight 5, from city 1 to 2 with weight 3, from city 2 to 3 with weight 4, and from city 3 to 0 with weight 2

DSA C++

#include 
#include 
#include 

int main() {
    std::vector cities = {"A", "B", "C", "D"};

    // Define struct Edge with source, destination, weight
    // Create vector edges with given edges
    // Your code here

    return 0;
}

Hint

Define the struct before main(). Then create the vector of edges with the exact values inside curly braces.

3

Add a boolean to mark directed edges and update edges

Add a bool directed field to the Edge struct. Update the edges vector so that the edge from city 0 to 1 is directed (true), the edge from city 1 to 2 is undirected (false), the edge from city 2 to 3 is directed (true), and the edge from city 3 to 0 is undirected (false)

DSA C++

#include 
#include 
#include 

// Add bool directed to Edge struct
struct Edge {
    int source;
    int destination;
    int weight;
    // Your code here
};

int main() {
    std::vector cities = {"A", "B", "C", "D"};

    // Update edges vector with directed values
    // Your code here

    return 0;
}

Hint

Add bool directed to the struct and update each edge initializer with true or false as specified.

4

Print the graph edges with direction and weight

Use a for loop with variable edge to iterate over edges. For each edge, print the source city name, an arrow "->" if directed is true, or a double arrow "<->" if directed is false, then the destination city name, and the weight in parentheses. Use std::cout to print each edge on its own line.

DSA C++

#include 
#include 
#include 

struct Edge {
    int source;
    int destination;
    int weight;
    bool directed;
};

int main() {
    std::vector cities = {"A", "B", "C", "D"};

    std::vector edges = {
        {0, 1, 5, true},
        {1, 2, 3, false},
        {2, 3, 4, true},
        {3, 0, 2, false}
    };

    // Use for loop with edge to print each edge
    // Your code here

    return 0;
}

Hint

Use a range-based for loop and std::cout. Check edge.directed to decide which arrow to print.

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