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

Concept Flow - Graph Terminology Vertices Edges Directed Undirected Weighted

Start: Define Graph

↓

Identify Vertices

↓

Identify Edges

↓

Check Edge Type

↓

Directed

↓

Check Weight?

↓

Weighted Edge

↓

Unweighted

↓

Done

This flow shows how a graph is built from vertices and edges, then edges are classified as directed or undirected, and weighted or unweighted.

Execution Sample

DSA Go

Vertices: A, B, C
Edges: A->B (directed), B-C (undirected), C->A (weighted directed with weight 5)

Defines a graph with 3 vertices and 3 edges showing directed, undirected, and weighted edges.

Execution Table

Step	Operation	Vertices	Edges	Edge Type	Weight	Visual State
1	Define vertices	A, B, C	None	None	None	Vertices: A, B, C
2	Add edge A->B	A, B, C	A->B	Directed	Unweighted	A -> B
3	Add edge B-C	A, B, C	A->B, B-C	Undirected	Unweighted	A -> B, B <-> C
4	Add edge C->A with weight 5	A, B, C	A->B, B-C, C->A	Directed	Weighted (5)	A -> B, B <-> C, C -(5)-> A
5	Graph complete	A, B, C	A->B, B-C, C->A	Mixed	Mixed	Graph with 3 vertices and 3 edges

💡 All vertices and edges defined with their types and weights.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
Vertices	None	A, B, C	A, B, C	A, B, C	A, B, C	A, B, C
Edges	None	None	A->B	A->B, B-C	A->B, B-C, C->A	A->B, B-C, C->A
Edge Types	None	None	Directed	Directed, Undirected	Directed, Undirected, Directed	Mixed
Weights	None	None	Unweighted	Unweighted, Unweighted	Unweighted, Unweighted, Weighted(5)	Mixed

Key Moments - 3 Insights

Why is the edge B-C considered undirected while A->B is directed?

Because B-C connects B and C both ways (no arrow), while A->B has an arrow showing direction from A to B, as shown in execution_table rows 2 and 3.

How do we know if an edge is weighted or unweighted?

If the edge has a number representing cost or weight (like 5 in C->A), it is weighted; otherwise, it is unweighted. See execution_table row 4.

Can a graph have both directed and undirected edges?

Yes, as shown in the final graph state (row 5), the graph contains mixed edge types.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what type of edge is B-C?

A Weighted

B Directed

C Undirected

D No edge

💡 Hint

Check the 'Edge Type' column at step 3 in execution_table.

At which step does the graph first include a weighted edge?

A Step 2

B Step 4

C Step 3

D Step 5

💡 Hint

Look at the 'Weight' column in execution_table to find when 'Weighted' appears.

If the edge C->A was unweighted, how would the 'Weights' variable change after step 4?

A It would be 'Unweighted' for all edges

B It would be 'Weighted' for all edges

C It would remain 'None'

D It would be 'Mixed' as before

💡 Hint

Check variable_tracker 'Weights' row after step 4.

Concept Snapshot

Graph = vertices + edges
Edges connect vertices
Edges can be directed (arrow) or undirected (no arrow)
Edges can be weighted (have cost) or unweighted
Graphs can mix edge types

Full Transcript

A graph is made of points called vertices and connections called edges. Edges can point one way (directed) or both ways (undirected). Some edges have weights, which are numbers showing cost or distance. This example shows a graph with three vertices A, B, C and three edges: A->B directed and unweighted, B-C undirected and unweighted, and C->A directed and weighted with 5. The graph can have mixed edge types and weights.

Practice

1. In a graph, what do we call the points or nodes where edges meet?

easy

A. Paths

B. Edges

C. Weights

D. Vertices

Solution

1. Step 1: Understand graph components

   A graph consists of points called nodes and connections called edges.

2. Step 2: Identify the term for nodes

   The points or nodes where edges meet are called vertices.

3. Final Answer:

   Vertices -> Option D

4. Quick Check:

   Nodes = Vertices [OK]

Hint: Remember: nodes = vertices, connections = edges [OK]

Common Mistakes:

• Confusing edges with vertices
• Thinking weights are nodes
• Mixing paths with vertices

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

easy

A. graph := make(map[int][]int)

B. graph := make([][]int, 0)

C. graph := make(map[int]int)

D. graph := make([]int, 0)

Solution

1. Step 1: Understand adjacency list representation

   An adjacency list uses a map from a vertex to a list of connected vertices.

2. Step 2: Choose correct Go syntax

   Using map[int][]int creates a map from int to slice of ints, perfect for adjacency list.

3. Final Answer:

   graph := make(map[int][]int) -> Option A

4. Quick Check:

   Map of int to slice[int] = adjacency list [OK]

Hint: Adjacency list = map from node to list of nodes [OK]

Common Mistakes:

• Using map[int]int which stores single int, not list
• Using slice of slices without map for keys
• Using slice of ints which can't map nodes

3. What will be the output of the following Go code snippet representing a weighted directed graph adjacency list?

graph := map[int]map[int]int{
  1: {2: 5, 3: 10},
  2: {3: 2},
  3: {},
}
fmt.Println(graph[1][3])

medium

A. 2

B. 5

C. 10

D. 0

Solution

1. Step 1: Understand graph structure

   graph[1] is a map with keys 2 and 3, values 5 and 10 respectively.

2. Step 2: Access graph[1][3]

   graph[1][3] accesses the weight from vertex 1 to 3, which is 10.

3. Final Answer:

   10 -> Option C

4. Quick Check:

   Weight from 1 to 3 = 10 [OK]

Hint: Access nested map keys for weights: graph[from][to] [OK]

Common Mistakes:

• Confusing weight 5 (edge 1->2) with 1->3
• Assuming 0 means no edge but 3 has empty map
• Mixing up keys and values in nested maps

4. Identify the error in this Go code snippet for adding an edge to an undirected graph adjacency list:

func addEdge(graph map[int][]int, u, v int) {
  graph[u] = append(graph[u], v)
  graph[v] = append(graph[u], v)
}

medium

A. Appending v to graph[u] twice

B. Appending v to graph[v] incorrectly

C. Missing initialization of graph map

D. Using wrong data type for graph

Solution

1. Step 1: Analyze append statements

   First append adds v to graph[u], correct for edge u->v.

2. Step 2: Check second append

   Second append incorrectly appends v to graph[u] again instead of graph[v].

3. Final Answer:

   Appending v to graph[v] incorrectly -> Option B

4. Quick Check:

   Second append should be graph[v] = append(graph[v], u) [OK]

Hint: For undirected, append u to v's list and v to u's list [OK]

Common Mistakes:

• Appending to wrong slice variable
• Forgetting to append both directions
• Not initializing map slices before append

5. Given a weighted undirected graph represented as a map[int]map[int]int in Go, how can you ensure that adding an edge between two vertices u and v with weight w updates both directions correctly?

hard

A. graph[u][v] = w; graph[v][u] = w

B. graph[u][v] = w only

C. graph[v][u] = w only

D. graph[u][v] = w; graph[u][v] = w

Solution

1. Step 1: Understand undirected graph edge representation

   In undirected graphs, edges go both ways, so weights must be stored both ways.

2. Step 2: Update both directions in map

   Assign weight w to graph[u][v] and graph[v][u] to reflect undirected edge.

3. Final Answer:

   graph[u][v] = w; graph[v][u] = w -> Option A

4. Quick Check:

   Both directions updated = undirected edge [OK]

Hint: Update both graph[u][v] and graph[v][u] for undirected edges [OK]

Common Mistakes:

• Updating only one direction
• Assigning weight twice to same direction
• Confusing directed and undirected edge updates