Graph Terminology Vertices Edges Directed Undirected Weighted in DSA C++ - Execution Trace

Concept Flow - Graph Terminology Vertices Edges Directed Undirected Weighted

Start: Define Graph

↓

Identify Vertices (Nodes)

↓

Identify Edges (Connections)

↓

Check Edge Type

↓

Edges have direction

↓

Check if Edges have Weights

↓

Weighted Edges

↓

Graph Representation Ready

This flow shows how a graph is built from vertices and edges, then classified by edge direction and weights.

Execution Sample

DSA C++

struct Graph {
  int V; // vertices
  vector<pair<int,int>> edges; // edges
};

Defines a simple graph structure with vertices and edges.

Execution Table

Step	Operation	Vertices	Edges	Edge Type	Weighted	Visual State
1	Create graph	{}	{}	N/A	N/A	Graph is empty
2	Add vertices 1,2,3	{1,2,3}	{}	N/A	N/A	Vertices: 1 2 3; No edges yet
3	Add edge 1->2	{1,2,3}	{(1->2)}	Directed	No	1 -> 2
4	Add edge 2->3	{1,2,3}	{(1->2), (2->3)}	Directed	No	1 -> 2 -> 3
5	Add edge 3->1	{1,2,3}	{(1->2), (2->3), (3->1)}	Directed	No	Cycle: 1 -> 2 -> 3 -> 1
6	Change edges to undirected	{1,2,3}	{(1--2), (2--3), (3--1)}	Undirected	No	Triangle: 1--2--3--1
7	Add weights to edges	{1,2,3}	{(1--2,5), (2--3,3), (3--1,4)}	Undirected	Yes	Weighted triangle with edges 5,3,4
8	End	{1,2,3}	{(1--2,5), (2--3,3), (3--1,4)}	Undirected	Yes	Final weighted undirected graph

💡 Graph construction complete with vertices, edges, direction, and weights defined.

Variable Tracker

Variable	Start	After 2	After 3	After 4	After 5	After 6	After 7	Final
Vertices	{}	{1,2,3}	{1,2,3}	{1,2,3}	{1,2,3}	{1,2,3}	{1,2,3}	{1,2,3}
Edges	{}	{}	{(1->2)}	{(1->2),(2->3)}	{(1->2),(2->3),(3->1)}	{(1--2),(2--3),(3--1)}	{(1--2,5),(2--3,3),(3--1,4)}	{(1--2,5),(2--3,3),(3--1,4)}
Edge Type	N/A	N/A	Directed	Directed	Directed	Undirected	Undirected	Undirected
Weighted	N/A	N/A	No	No	No	No	Yes	Yes

Key Moments - 3 Insights

Why do edges have direction in a directed graph?

Edges have direction to show one-way relationships, as seen in steps 3-5 where edges are (1->2), (2->3), (3->1). This means you can go from 1 to 2 but not necessarily back.

What changes when edges become undirected?

In step 6, edges change from directed (arrows) to undirected (lines), meaning connections go both ways, like (1--2). This affects traversal and connectivity.

How do weights affect the graph?

Weights add values to edges (step 7), representing cost or distance. This is important for algorithms like shortest path.

Visual Quiz - 3 Questions

Look at the execution table, what is the edge type at step 4?

A Weighted

B Undirected

C Directed

D No edges yet

💡 Hint

Check the 'Edge Type' column at step 4 in the execution table.

At which step do edges become weighted?

A Step 5

B Step 7

C Step 6

D Step 8

💡 Hint

Look at the 'Weighted' column and 'Edges' column in the execution table.

If we remove the direction from edges at step 5, what will the visual state be at step 6?

A Edges become undirected lines connecting vertices

B Edges disappear

C Edges remain directed

D Vertices are removed

💡 Hint

See step 6 in the execution table for the change from arrows to lines.

Concept Snapshot

Graph = vertices (nodes) + edges (connections)
Edges can be directed (one-way) or undirected (two-way)
Edges may have weights (numbers) representing cost or distance
Directed graphs show arrows; undirected graphs show lines
Weighted graphs store values on edges for algorithms
Understanding these basics helps build and use graphs effectively

Full Transcript

A graph is made of vertices, which are points or nodes, and edges, which connect these points. Edges can be directed, meaning they go one way, or undirected, meaning they connect both ways. Sometimes edges have weights, which are numbers that show cost or distance. We start by creating vertices, then add edges. We decide if edges have direction or not, and if they have weights. This helps us understand how to represent and use graphs in programming and algorithms.

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