The Minimum Spanning Tree Problem

External

• https://www.coursera.org/learn/algorithms-greedy/lecture/9D5ML/mst-problem-definition

Internal

• Algorithms
• Graph Concepts
• Prim's Algorithm
• Kruskal's Algorithm
• The Optimal Branching Problem

Overview

We discuss the minimum spanning problem in the context of undirected graphs. The same problem can be discussed for directed graphs but in that case it is referred to as the Optimal Branching Problem.

The Problem

Given an undirected graph G=(V, E) and a positive or negative cost c_e for each edge e ∈ E, find the minimum cost spanning tree T ⊆ E (MST).

Algorithms

Prim's Algorithm

Prim's Algorithm