# Distinct Edge Weights

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

## We'll cover the following

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

$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 $G$ has weight $1$, then every spanning tree of $G$ is a minimum spanning tree, with weight $V − 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