Graph Terminology Vertices Edges Directed Undirected Weighted in DSA Go

Mental Model

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

Analogy: Think of a city map where intersections are points (vertices) and roads are lines (edges). Some roads go one way (directed), some both ways (undirected), and some roads are longer or shorter (weighted).

Vertices: A, B, C, D
Edges:
A -> B (directed)
B ↔ C (undirected)
C -> D (directed, weight 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: Weight shows cost or distance on edge from C to D

Result:

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

Annotated Code

DSA Go

package main

import "fmt"

type Vertex string

type Edge struct {
	from   Vertex
	to     Vertex
	directed bool
	weight int
}

type Graph struct {
	vertices []Vertex
	edges    []Edge
}

func (g *Graph) AddVertex(v Vertex) {
	g.vertices = append(g.vertices, v)
}

func (g *Graph) AddEdge(from, to Vertex, directed bool, weight int) {
	edge := Edge{from: from, to: to, directed: directed, weight: weight}
	g.edges = append(g.edges, edge)
	if !directed {
		// For undirected, add edge in both directions
		edgeRev := Edge{from: to, to: from, directed: directed, weight: weight}
		g.edges = append(g.edges, edgeRev)
	}
}

func (g *Graph) Print() {
	fmt.Println("Vertices:")
	for _, v := range g.vertices {
		fmt.Printf("%s ", v)
	}
	fmt.Println()
	fmt.Println("Edges:")
	for _, e := range g.edges {
		arrow := "->"
		if !e.directed {
			arrow = "↔"
		}
		if e.weight > 0 {
			fmt.Printf("%s %s %s (weight %d)\n", e.from, arrow, e.to, e.weight)
		} else {
			fmt.Printf("%s %s %s\n", e.from, arrow, e.to)
		}
	}
}

func main() {
	g := Graph{}
	g.AddVertex("A")
	g.AddVertex("B")
	g.AddVertex("C")
	g.AddVertex("D")
	g.AddEdge("A", "B", true, 0)      // directed edge A->B
	g.AddEdge("B", "C", false, 0)     // undirected edge B<->C
	g.AddEdge("C", "D", true, 5)      // directed weighted edge C->D weight 5
	g.Print()
}

g.AddEdge("A", "B", true, 0) // directed edge A->B

Add directed edge from A to B

g.AddEdge("B", "C", false, 0) // undirected edge B<->C

Add undirected edge between B and C by adding edges both ways

g.AddEdge("C", "D", true, 5) // directed weighted edge C->D weight 5

Add directed weighted edge from C to D with weight 5

g.Print()

Print all vertices and edges with direction and weight

Output

Vertices:

A B C D 

Edges:

A -> B

B ↔ C

C ↔ B

C -> D (weight 5)

Complexity Analysis

Time: O(V + E) because printing and storing vertices and edges requires visiting each once

Space: O(V + E) because we store all vertices and edges explicitly

vs Alternative: Compared to adjacency matrix (O(V^2) space), this edge list uses less space for sparse graphs

Edge Cases

Graph with no vertices

Print shows empty vertices and edges lists

DSA Go

func (g *Graph) Print() { for _, v := range g.vertices { ... } }

Graph with single vertex and no edges

Print shows one vertex and no edges

DSA Go

func (g *Graph) Print() { for _, e := range g.edges { ... } }

Undirected edge adds two edges internally

Both directions appear in edges list

DSA Go

if !directed { edgeRev := Edge{...}; g.edges = append(g.edges, edgeRev) }

When to Use This Pattern

When a problem involves connecting points with lines that may have direction or cost, think of graph terminology to model it clearly.

Common Mistakes

Mistake: Treating undirected edges as single edges without adding reverse connection
Fix: Add edges in both directions for undirected edges to represent two-way connection

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 that undirected edges connect both ways, so represent them as two directed edges internally.

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