מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתמים למציאת עפ"מ

תבנית:מבני נתונים ואלגוריתמים - מחברת קורס

דף זו עוסק באלגוריתם למציאת ההעץ הפורש הזול ביותר בגרף לא מכוון בעל טבלת עלויות לקשתות.

הבעיה

נתונים גרף לא מכוון $G = (V, E)$ וטבלת עלויות לקשתות $E$ . רוצים לדעת מהי קבוצת הקשתות הזולה ביותר כך שכל שני צמתים יהיו מחוברים.

תבנית:מבנה תבנית

הרעיון הכללי

כבר ראינו (בעצים) "אלגוריתם" למציאת עץ פורש. נשנה אותו מעט:

# Takes a connected undirected graph (G) and a cost table (Edge-Costs)
# Returns a set of edges E' such that (V(G), E') is 
#	a MST (minimum spanning tree).
Grow-MST(G, Edge-Costs)
1	V= V(G)
2	E' = {}

3	while (V, E') isn't a tree
4		e = some (u, v): u, v are from different trees; e is a light edge
5		E' = E' ∪ {e}

6	return E'

כלומר, השינוי היחידי הוא שעתה אנו בוחרים בכל איטרציה קשת קלה. מיד נעסוק בשאלה מהן קשתות קלות ומה חשיבותן. בהמשך נראה שני אלגוריתמים שהם מקרים פרטיים של "אלגוריתם" זה.