Graph Terminology Vertices Edges Directed Undirected Weighted in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of adjacency list for directed weighted graph

What is the printed adjacency list representation of this directed weighted graph after adding edges?

DSA Go

package main

import "fmt"

type Edge struct {
    to     int
    weight int
}

func main() {
    graph := make(map[int][]Edge)
    graph[1] = append(graph[1], Edge{to: 2, weight: 5})
    graph[1] = append(graph[1], Edge{to: 3, weight: 3})
    graph[2] = append(graph[2], Edge{to: 3, weight: 2})
    graph[3] = append(graph[3], Edge{to: 1, weight: 4})

    for from, edges := range graph {
        fmt.Printf("%d ->", from)
        for _, e := range edges {
            fmt.Printf(" (%d, %d)", e.to, e.weight)
        }
        fmt.Println()
    }
}

A

1 -> (3, 3) (2, 5)
2 -> (3, 2)
3 -> (1, 4)

B

1 -> (2, 5) (3, 3)
2 -> (3, 2)
3 -> (1, 4)

C

1 -> (2, 5)
2 -> (3, 2)
3 -> (1, 4) (3, 3)

D

1 -> (2, 5) (3, 3)
2 -> (1, 4)
3 -> (3, 2)

💡 Hint

Look carefully at the order edges were added and which vertex they point to.

The graph is directed and weighted. Edges are added in order: from 1 to 2 with weight 5, from 1 to 3 with weight 3, from 2 to 3 with weight 2, and from 3 to 1 with weight 4. The adjacency list prints edges in insertion order.

🧠 Conceptual

intermediate

Number of edges in an undirected graph

If an undirected graph has 5 vertices and each vertex is connected to every other vertex exactly once, how many edges does the graph have?

A 15

B 20

C 5

D 10

💡 Hint

Use the formula for edges in a complete undirected graph: n*(n-1)/2

In an undirected graph, each edge connects two vertices. For 5 vertices fully connected, edges = 5*4/2 = 10.

❓ Predict Output

advanced

Output of BFS traversal order

What is the order of vertices visited in a BFS traversal starting from vertex 0 in this undirected graph?

DSA Go

package main

import "fmt"

func bfs(graph map[int][]int, start int) []int {
    visited := make(map[int]bool)
    queue := []int{start}
    order := []int{}

    for len(queue) > 0 {
        current := queue[0]
        queue = queue[1:]
        if !visited[current] {
            visited[current] = true
            order = append(order, current)
            for _, neighbor := range graph[current] {
                if !visited[neighbor] {
                    queue = append(queue, neighbor)
                }
            }
        }
    }
    return order
}

func main() {
    graph := map[int][]int{
        0: {1, 2},
        1: {0, 3, 4},
        2: {0, 5},
        3: {1},
        4: {1, 5},
        5: {2, 4},
    }
    order := bfs(graph, 0)
    fmt.Println(order)
}

A [0 1 2 4 3 5]

B [0 2 1 5 3 4]

C [0 1 2 3 4 5]

D [0 2 1 3 4 5]

💡 Hint

BFS visits neighbors level by level in the order they appear in adjacency list.

Starting at 0, neighbors 1 and 2 are enqueued. Visit 1, enqueue 3 and 4. Visit 2, enqueue 5. Then visit 3, 4, 5 in order.

🔧 Debug

advanced

Identify error in weighted undirected graph edge addition

What error will this code cause when adding edges to an undirected weighted graph?

DSA Go

package main

import "fmt"

type Edge struct {
    to     int
    weight int
}

func main() {
    graph := make(map[int][]Edge)
    graph[1] = append(graph[1], Edge{to: 2, weight: 7})
    graph[2] = append(graph[2], Edge{to: 1}) // Missing weight
    fmt.Println(graph)
}

A Compilation error: missing field 'weight' in Edge struct literal

B Prints graph with zero weight for edge 2->1

C Runtime panic: index out of range

D No error, prints graph correctly

💡 Hint

Check struct initialization for all required fields.

Edge struct requires both 'to' and 'weight' fields. Omitting 'weight' causes compilation error.

🧠 Conceptual

expert

Minimum edges to connect all vertices in weighted undirected graph

In a weighted undirected graph with 8 vertices, what is the minimum number of edges required to ensure the graph is connected?

A 7

B 8

C 15

D 28

💡 Hint

Think about the minimum edges in a spanning tree.

A connected graph with n vertices needs at least n-1 edges to connect all vertices without cycles.

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