CodeBlanks Logo Icon CodeBlanks
Login Register

Edge sorting

Sort edges by weight and add greedily.

Edge sorting

Kruskal's first step is to sort edges by weight in ascending order. This way, the lowest-weight edges are tried first.

Sorting is the basis of the greedy approach. At each step, the lowest-weight available edge is picked.

Greedy choice

We walk through the sorted edge list and add each edge to the MST if it does not form a cycle. Union-find is used for cycle detection.

This greedy approach guarantees the MST is optimal. Each step makes the locally best choice.

Practice sort_edges function

Write sort_edges(edges). Sort edges by weight in ascending order, return them. Print with print(sort_edges(init_edges())).

Starter code

solution.py
def init_edges():
    # Return edge list
    return [(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)]
def sort_edges(edges):
    # Sort edges by weight

Sample solution

solution.py
def init_edges():
    # Return edge list
    return [(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)]
def sort_edges(edges):
    # Sort edges by weight
    return sorted(edges, key=lambda e: e[2])
print(sort_edges(init_edges()))

Expected output

[(2, 3, 4), (0, 3, 5), (0, 2, 6), (0, 1, 10), (1, 3, 15)]

Questions and answers

Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.

1 Sort key

Question 
sorted(edges, key=lambda e: ____)
Answer 
sorted(edges, key=lambda e: e[2])

Explanation: e[2] is right.

2 In which direction is the sorting done?

  • Descending
  • Ascending Correct answer
  • Random
  • By node index

Explanation: Edges are sorted in ascending order.

3 Edge sorting: match the terms

Term Meaning
sorted Sort
lambda Key
e[2] Weight
edges Source

All lessons in Advanced

1 DP - Memoization

  1. What is memoization?
  2. Fibonacci memoization
  3. Dict-based cache
  4. Summary - Memoization

2 DP - Tabulation

  1. What is tabulation?
  2. Building the table
  3. Fibonacci tabulation
  4. Summary - Tabulation

3 LCS

  1. LCS definition
  2. DP table
  3. Backtracking the table
  4. Summary - LCS

4 Knapsack

  1. Knapsack problem
  2. 0/1 knapsack DP
  3. Decision table
  4. Summary - Knapsack

5 DP project

  1. Project: Overview
  2. Cost table
  3. DP solution
  4. Print the result

6 Matrix chain

  1. Multiplication order
  2. DP table
  3. Split point
  4. Summary - Matrix chain

7 Floyd-Warshall

  1. All pairs
  2. Triple loop
  3. Table update
  4. Summary - Floyd-Warshall

8 Dijkstra

  1. Single source
  2. Priority queue
  3. Relaxation
  4. Summary - Dijkstra

9 Bellman-Ford

  1. Negative weights
  2. Edge relaxation loop
  3. Negative cycle
  4. Summary - Bellman-Ford

10 Kruskal

  1. Minimum spanning tree
  2. Edge sorting
  3. Cycle check
  4. Summary - Kruskal

11 Prim

  1. Prim idea
  2. Priority queue
  3. Visited set
  4. Summary - Prim

12 Topological sort

  1. Dependency order
  2. DFS-based sort
  3. Kahn algorithm
  4. Summary - Topological sort

13 Union-find, trie, segment tree

  1. Union-find
  2. Trie
  3. Segment tree
  4. Summary - Advanced structures

14 Advanced final

  1. Challenge 1
  2. Challenge 2
  3. Challenge 3
  4. Challenge 4