The Minimum Spanning Tree Problem: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
| (11 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
=External= | =External= | ||
* https://www.coursera.org/learn/algorithms-greedy/lecture/9D5ML/mst-problem-definition | * 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]] | ||
| Line 13: | Line 15: | ||
=The Problem= | =The Problem= | ||
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 | 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
- 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
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: