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

Concept Flow - Graph Terminology Vertices Edges Directed Undirected Weighted

Start: Define Graph

↓

Add Vertices (Nodes)

↓

Add Edges (Connections)

↓

Check Edge Type

↓

Directed Edge

↓

Assign Direction

↓

Assign Weight?

↓

Weighted or Unweighted

↓

Graph Complete

This flow shows how a graph is built step-by-step: first vertices, then edges, deciding if edges are directed or undirected, and if they have weights.

Execution Sample

DSA Java

Graph g = new Graph();
g.addVertex("A");
g.addVertex("B");
g.addEdge("A", "B", true, 5);

This code creates a graph, adds two vertices A and B, then adds a directed weighted edge from A to B with weight 5.

Execution Table

Step	Operation	Vertices	Edges	Edge Type	Weight	Visual State
1	Create Graph	{}	{}	N/A	N/A	{}
2	Add Vertex A	{"A"}	{}	N/A	N/A	A
3	Add Vertex B	{"A", "B"}	{}	N/A	N/A	A, B
4	Add Edge A->B	{"A", "B"}	{"A"->"B"}	Directed	5	A --5--> B
5	Graph Complete	{"A", "B"}	{"A"->"B"}	Directed	5	A --5--> B

💡 All vertices and edges added; graph construction finished.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
Vertices	{}	{"A"}	{"A", "B"}	{"A", "B"}	{"A", "B"}
Edges	{}	{}	{}	{"A"->"B"}	{"A"->"B"}
Edge Type	N/A	N/A	N/A	Directed	Directed
Weight	N/A	N/A	N/A	5	5

Key Moments - 3 Insights

Why do we add vertices before edges?

Vertices must exist first because edges connect these vertices. As shown in execution_table steps 2 and 3, vertices A and B are added before the edge in step 4.

What is the difference between directed and undirected edges?

Directed edges have a direction from one vertex to another (step 4 shows A->B), while undirected edges connect vertices both ways without direction.

How does weight affect the edge?

Weight assigns a value to the edge, like cost or distance. In step 4, the edge from A to B has weight 5, shown visually as A --5--> B.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, how many vertices are in the graph?

A 2

B 0

C 1

D 3

💡 Hint

Check the 'Vertices' column at step 3 in execution_table.

At which step is the edge added as directed with weight 5?

A Step 3

B Step 4

C Step 2

D Step 5

💡 Hint

Look at the 'Operation' and 'Edge Type' columns in execution_table.

If the edge was undirected and unweighted, how would the Visual State at step 4 change?

A A --5--> B

B A --> B

C A <--> B

D A --0--> B

💡 Hint

Undirected edges show two-way connection without weight, check Visual State format.

Concept Snapshot

Graph = collection of vertices (nodes) and edges (connections).
Vertices must be added before edges.
Edges can be directed (one-way) or undirected (two-way).
Edges may have weights representing cost or distance.
Directed weighted edge example: A --5--> B.

Full Transcript

This lesson shows how a graph is built step-by-step. First, vertices are added as points or nodes. Then edges are added to connect these vertices. Edges can be directed, meaning they go from one vertex to another, or undirected, meaning they connect both ways. Edges can also have weights, which are numbers representing cost or distance. The example code creates a graph, adds vertices A and B, then adds a directed weighted edge from A to B with weight 5. The execution table tracks each step, showing the vertices and edges present, their types, and the visual representation. Key moments clarify why vertices come first, the difference between directed and undirected edges, and the role of weights. The quiz tests understanding of these steps and concepts.

Practice

1. Which of the following best describes a vertex in a graph?

easy

A. A point or node where edges meet

B. A line connecting two vertices

C. A graph with no edges

D. A graph that has weights on edges

Solution

1. Step 1: Understand the definition of vertex

   A vertex is a fundamental unit in a graph representing a point or node.

2. Step 2: Differentiate vertex from edges and graph types

   Edges connect vertices; weights and graph types describe edges or the whole graph, not vertices.

3. Final Answer:

   A point or node where edges meet -> Option A

4. Quick Check:

   Vertex = point/node [OK]

Hint: Vertices are points/nodes, edges are connections [OK]

Common Mistakes:

• Confusing edges with vertices
• Thinking weights define vertices
• Mixing graph types with vertex definition

2. Which of the following is the correct way to declare an undirected weighted graph using adjacency list in Java?

easy

A. Map graph = new HashMap<>();

B. Map graph = new TreeMap<>();

C. Map>> graph = new TreeSet<>();

D. Map>> graph = new HashMap<>();

Solution

1. Step 1: Identify data structure for weighted edges

   Weighted edges need to store both neighbor and weight, so Pair is used.

2. Step 2: Choose correct map and list types

   HashMap with List of pairs is standard for adjacency list of weighted graphs.

3. Final Answer:

   Map>> graph = new HashMap<>(); -> Option D

4. Quick Check:

   Weighted graph uses Pair for edges [OK]

Hint: Weighted edges need pairs: neighbor and weight [OK]

Common Mistakes:

• Using List<Integer> for weighted edges
• Using TreeSet instead of List for adjacency
• Confusing Map types for graph

3. Consider the following Java code snippet for a directed graph:

Map graph = new HashMap<>();
graph.put(1, Arrays.asList(2, 3));
graph.put(2, Arrays.asList(3));
graph.put(3, Arrays.asList());
System.out.println(graph.get(1));

What will be the output?

medium

A. null

B. [1, 2, 3]

C. [2, 3]

D. []

Solution

1. Step 1: Check what is stored for key 1

   Key 1 maps to list containing 2 and 3.

2. Step 2: Print the list for key 1

   Printing graph.get(1) outputs the list [2, 3].

3. Final Answer:

   [2, 3] -> Option C

4. Quick Check:

   graph.get(1) = [2, 3] [OK]

Hint: Print adjacency list for key to see neighbors [OK]

Common Mistakes:

• Expecting all vertices in output
• Confusing keys and values
• Assuming empty list prints null

4. The following code attempts to add an edge to an undirected graph represented by adjacency list. What is the bug?

void addEdge(Map graph, int u, int v) {
    graph.get(u).add(v);
}

medium

A. It adds edge only from u to v, missing v to u

B. It uses get() instead of put() to add edge

C. It should use a Set instead of List for adjacency

D. It should clear the adjacency list before adding

Solution

1. Step 1: Understand undirected graph edge addition

   Undirected edges must be added both ways: u to v and v to u.

2. Step 2: Analyze given code

   Code adds edge only from u to v, missing the reverse edge.

3. Final Answer:

   It adds edge only from u to v, missing v to u -> Option A

4. Quick Check:

   Undirected edges need both directions [OK]

Hint: Undirected edges require adding both directions [OK]

Common Mistakes:

• Adding edge only one way in undirected graph
• Confusing get() and put() usage
• Clearing adjacency list mistakenly

5. You have a weighted directed graph represented as:

Map>> graph = new HashMap<>();
graph.put(1, Arrays.asList(new Pair<>(2, 5), new Pair<>(3, 10)));
graph.put(2, Arrays.asList(new Pair<>(3, 2)));
graph.put(3, Arrays.asList());

How would you find the total weight of edges going out from vertex 1?

hard

A. Sum weights 10 + 2 = 12

B. Sum weights 5 + 10 = 15

C. Sum weights 5 + 2 = 7

D. Count edges: 2

Solution

1. Step 1: Identify edges from vertex 1

   Edges from 1 go to 2 with weight 5, and to 3 with weight 10.

2. Step 2: Sum the weights of these edges

   Total weight = 5 + 10 = 15.

3. Final Answer:

   Sum weights 5 + 10 = 15 -> Option B

4. Quick Check:

   Total outgoing weight from 1 = 15 [OK]

Hint: Add weights of all edges from the vertex [OK]

Common Mistakes:

• Adding weights from wrong vertices
• Counting edges instead of summing weights
• Mixing weights of different edges