Graph Terminology Vertices Edges Directed Undirected Weighted in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare a graph vertex as a struct with an ID.

DSA Go

type Vertex struct {
    ID [1]
}

Drag options to blanks, or click blank then click option'

Afloat64

Bstring

Cbool

Dint

Attempts:

3 left

💡 Hint

Common Mistakes

Using string instead of int for ID.

Using float64 unnecessarily for ID.

Using bool which is not suitable for ID.

In Go, struct fields are declared as 'Name Type', and vertex IDs are integers (int).

2fill in blank

medium

Complete the code to add an edge from vertex u to vertex v in a directed graph adjacency list.

DSA Go

graph[u] = append(graph[u], [1])

Drag options to blanks, or click blank then click option'

Agraph[v]

Bu

Cv

Dedge

Attempts:

3 left

💡 Hint

Common Mistakes

Appending u instead of v.

Appending graph[v] which is a slice, not a vertex.

Appending an undefined variable 'edge'.

To add an edge from u to v, we append v to u's adjacency list.

3fill in blank

hard

Fix the error in the code to correctly check if an edge exists from u to v in an undirected graph.

DSA Go

for _, neighbor := range graph[[1]] {
    if neighbor == v {
        return true
    }
}
return false

Drag options to blanks, or click blank then click option'

Au

Bv

Cgraph

Dneighbor

Attempts:

3 left

💡 Hint

Common Mistakes

Iterating over graph[v] instead of graph[u].

Using 'neighbor' or 'graph' in place of vertex variable.

Confusing source and destination vertices.

We must iterate over the adjacency list of u to check if v is a neighbor.

4fill in blank

hard

Fill both blanks to define a weighted edge struct with to and weight fields.

DSA Go

type Edge struct {
    to [1]
    weight [2]
}

Drag options to blanks, or click blank then click option'

Aint

Bstring

Cfloat64

Dbool

Attempts:

3 left

💡 Hint

Common Mistakes

Using string for to instead of int.

Using bool for weight which is numeric.

Mixing types between to and weight.

The target vertex is an integer ID, and weight is a floating-point number.

5fill in blank

hard

Fill all three blanks to create a map representing an undirected weighted graph adjacency list.

DSA Go

graph := map[int][][1] {
    1: [][2] { {to: 2, weight: 3.5} },
    2: [][3] { {to: 1, weight: 3.5} },
}

Drag options to blanks, or click blank then click option'

AEdge

BVertex

Dint

Attempts:

3 left

💡 Hint

Common Mistakes

Using Vertex instead of Edge in the map value type.

Using int instead of Edge for slice elements.

Inconsistent types in map values.

The graph maps integers to slices of Edge structs representing weighted connections.

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