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

Mental Model

A graph is a way to connect points (called vertices) with lines (called edges) that can have directions and weights.

Analogy: Imagine a city map where intersections are vertices and roads are edges. Some roads go one way (directed), some go both ways (undirected), and some roads have distances or tolls (weights).

Vertices: A, B, C, D
Edges:
A -> B (directed)
B ↔ C (undirected)
C -> D (directed, weighted 5)

  A -> B
      ↘
       C ↔ D

Weights shown as numbers on edges if any.

Dry Run Walkthrough

Input: Graph with vertices A, B, C, D; edges: A->B (directed), B↔C (undirected), C->D (directed, weight 5)

Goal: Understand how vertices and edges connect, and how direction and weight affect the graph

Step 1: Identify vertices as points A, B, C, D

Vertices: [A] [B] [C] [D]

Why: Vertices are the main points or nodes in the graph

Step 2: Add directed edge from A to B

A -> B
Vertices: [A] [B] [C] [D]

Why: Directed edge means connection goes only from A to B

Step 3: Add undirected edge between B and C

A -> B ↔ C
Vertices: [A] [B] [C] [D]

Why: Undirected edge means connection goes both ways between B and C

Step 4: Add directed weighted edge from C to D with weight 5

A -> B ↔ C -> D (weight 5)
Vertices: [A] [B] [C] [D]

Why: Weighted edge shows cost or distance; direction means from C to D only

Result:

A -> B ↔ C -> D (weight 5)
Vertices: [A] [B] [C] [D]

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <list>

using namespace std;

// Edge structure to hold destination, direction, and weight
struct Edge {
    string dest;
    bool directed;
    int weight;
    Edge(string d, bool dir, int w = 0) : dest(d), directed(dir), weight(w) {}
};

// Graph class
class Graph {
public:
    unordered_map<string, list<Edge>> adjList;

    void addVertex(const string& vertex) {
        if (adjList.find(vertex) == adjList.end()) {
            adjList[vertex] = list<Edge>();
        }
    }

    void addEdge(const string& src, const string& dest, bool directed, int weight = 0) {
        addVertex(src);
        addVertex(dest);
        adjList[src].push_back(Edge(dest, directed, weight));
        if (!directed) {
            adjList[dest].push_back(Edge(src, directed, weight));
        }
    }

    void printGraph() {
        for (auto& pair : adjList) {
            cout << pair.first << " -> ";
            for (auto& edge : pair.second) {
                cout << edge.dest;
                if (edge.directed) cout << " (directed";
                else cout << " (undirected";
                if (edge.weight != 0) cout << ", weight " << edge.weight;
                cout << ") ";
            }
            cout << endl;
        }
    }
};

int main() {
    Graph g;
    g.addEdge("A", "B", true); // directed edge A->B
    g.addEdge("B", "C", false); // undirected edge B<->C
    g.addEdge("C", "D", true, 5); // directed weighted edge C->D weight 5

    g.printGraph();
    return 0;
}

adjList[src].push_back(Edge(dest, directed, weight));

Add edge from source to destination with direction and weight

if (!directed) { adjList[dest].push_back(Edge(src, directed, weight)); }

If edge is undirected, add reverse edge as well

for (auto& pair : adjList) { for (auto& edge : pair.second) { ... } }

Traverse adjacency list to print all edges with their properties

Output

A -> B (directed) 

B -> C (undirected) 

C -> B (undirected) D (directed, weight 5) 

D -> 

Complexity Analysis

Time: O(V + E) because we store and print each vertex and its edges once

Space: O(V + E) because adjacency list stores all vertices and edges

vs Alternative: Compared to adjacency matrix which uses O(V^2) space, adjacency list is more efficient for sparse graphs

Edge Cases

Graph with no vertices or edges

Prints nothing, no errors

DSA C++

for (auto& pair : adjList) { ... }

Adding edge where vertices do not exist yet

Vertices are automatically created before adding edges

DSA C++

addVertex(src); addVertex(dest);

Adding undirected edge

Edge added in both directions

DSA C++

if (!directed) { adjList[dest].push_back(Edge(src, directed, weight)); }

When to Use This Pattern

When a problem involves connecting points with lines that may have directions or costs, think of graph terminology and representation to model it.

Common Mistakes

Mistake: Forgetting to add the reverse edge for undirected edges
Fix: Add the edge in both directions when the edge is undirected

Mistake: Confusing directed and undirected edges in representation
Fix: Use a boolean flag to clearly mark edges as directed or undirected

Summary

Graphs connect points called vertices with lines called edges that can be directed or undirected and may have weights.

Use graph terminology to model relationships where direction and cost matter, like maps or networks.

Remember edges can go one way (directed) or both ways (undirected), and weights add extra information like distance or cost.

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