The Minimum Spanning Tree Problem: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
 
(17 intermediate revisions by the same user not shown)
Line 1: Line 1:
=External=
* https://www.coursera.org/learn/algorithms-greedy/lecture/9D5ML/mst-problem-definition
* https://www.coursera.org/learn/algorithms-greedy/lecture/Wt9aw/msts-state-of-the-art-and-open-questions-advanced-optional
=Internal=
=Internal=
* [[Algorithms#Greedy_Algorithms|Algorithms]]
* [[Algorithms#Greedy_Algorithms|Greedy Algorithms]]
* [[Graph_Concepts#Minimum_Spanning_Tree_.28MST.29|Graph Concepts]]
* [[Prim%27s_Algorithm|Prim's Algorithm]]
* [[Prim%27s_Algorithm|Prim's Algorithm]]
* [[Kruskal%27s_Algorithm|Kruskal's Algorithm]]
* [[Kruskal%27s_Algorithm|Kruskal's Algorithm]]
* [[The Optimal Branching Problem]]
=Overview=
=Overview=
We discuss the minimum spanning problem in the context of [[Graph_Concepts#Undirected_Graph|undirected]] graphs. The same problem can be discussed for directed graphs but in that case it is referred to as the [[The Optimal Branching Problem|Optimal Branching Problem]].
We discuss the minimum spanning problem in the context of [[Graph_Concepts#Undirected_Graph|undirected]] graphs. The same problem can be discussed for [[Graph_Concepts#Directed_Graph|directed]] graphs but in that case it is referred to as the [[The Optimal Branching Problem|Optimal Branching Problem]].


=The Problem=
=The Problem=


Given an [[Graph_Concepts#Undirected_Graph|undirected]] graph G=(V, E),
Given an [[Graph_Concepts#Undirected_Graph|undirected]] graph G=(V, E) and a positive or negative cost c<sub>e</sub> for each edge e ∈ E, find the [[Graph_Concepts#Spanning_Tree_Cost|minimum cost]] [[Graph_Concepts#Spanning_Trees|spanning tree]] T ⊆ E (MST).
 
=Algorithms=
The minimum spanning tree problem is solved by [[Algorithms#Greedy_Algorithms|greedy algorithms]]:
==Prim's Algorithm==
{{Internal|Prim%27s_Algorithm#Overview|Prim's Algorithm}}
 
==Kruskal's Algorithm==
{{Internal|Kruskal%27s_Algorithm|Kruskal's Algorithm}}

Latest revision as of 20:07, 22 October 2021

External

Internal

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 ce for each edge e ∈ E, find the minimum cost spanning tree T ⊆ E (MST).

Algorithms

The minimum spanning tree problem is solved by greedy algorithms:

Prim's Algorithm

Prim's Algorithm

Kruskal's Algorithm

Kruskal's Algorithm