Graph Terminology Vertices Edges Directed Undirected Weighted in DSA Go - Build from Scratch

Graph Terminology: Vertices, Edges, Directed, Undirected, Weighted

📖 Scenario: Imagine you are organizing a small city map. The map has places (like parks, schools) and roads connecting them. Some roads go one way only, some go both ways, and some roads have distances (weights).

🎯 Goal: You will create a simple graph using Go to represent places and roads. You will add places (vertices), roads (edges), mark if roads are one-way or two-way (directed or undirected), and assign distances (weights) to roads.

📋 What You'll Learn

Create a map called graph to hold places and their connections

Add a boolean variable isDirected to indicate if roads are one-way

Add roads with distances between places using a nested map

Print the graph connections showing places, connected places, and distances

💡 Why This Matters

🌍 Real World

Maps, social networks, and transportation systems use graphs to show connections and distances.

💼 Career

Understanding graph basics is important for software roles involving data modeling, routing, and network analysis.

1

Create the graph data structure

Create a variable called graph as a map where keys are strings and values are maps from strings to integers. This will hold places and distances to connected places.

DSA Go

graph := make(map[string]map[string]int)
// Your code here

Hint

Use make(map[string]map[string]int) to create the graph variable.

2

Add a variable to indicate if the graph is directed

Add a boolean variable called isDirected and set it to true to show roads are one-way.

DSA Go

package main

import "fmt"

func main() {
    graph := make(map[string]map[string]int)
    // Your code here
}

Hint

Use isDirected := true to create the variable.

3

Add edges with weights to the graph

Add these roads with distances to graph: from Park to School with distance 5, and from School to Mall with distance 10. Initialize nested maps if needed.

DSA Go

package main

import "fmt"

func main() {
    graph := make(map[string]map[string]int)
    isDirected := true
    // Your code here
}

Hint

Initialize nested maps before adding edges. Use graph["Place"] = make(map[string]int).

4

Print the graph showing places and roads with distances

Use a for loop with variables place and connections to iterate over graph. Inside, use another for loop with connectedPlace and distance to print each road in the format: Place -> ConnectedPlace : Distance.

DSA Go

package main

import "fmt"

func main() {
    graph := make(map[string]map[string]int)
    isDirected := true

    graph["Park"] = make(map[string]int)
    graph["Park"]["School"] = 5

    graph["School"] = make(map[string]int)
    graph["School"]["Mall"] = 10

    // Your code here
}

Hint

Use nested for loops and fmt.Printf to print each edge.

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