Distinct Edge Weights

Learn about the minimum spanning trees problem with distinct edge weights and its solution using various algorithms.

Suppose we are given a connected, undirected, weighted graph. This is a graph G=(V,E)G = (V, E) together with a function w:ERw: E \rightarrow \mathbb{R} that assigns a real weight w(e)w(e) to each edge ee, which may be positive, negative, or zero. This chapter describes several algorithms to find the minimum spanning tree of G\bold{G}, that is, the spanning tree TT that minimizes the function

w(T):=e ε Tw(e).w(T):=\underset{e \space\varepsilon\space T}{\sum}w(e).

Distinct edge weights

An annoying subtlety in the problem statement is that weighted graphs can have more than one spanning tree with the same minimum weight; in particular, if every edge in GG has weight 11, then every spanning tree of GG is a minimum spanning tree, with weight V1V − 1. This ambiguity complicates the development of our algorithms; everything would be much simpler if we could simply assume that minimum spanning trees are unique.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy