|
|
עמוד:332
6 , 3 האלגוריתם של קרוסקל ( Kruskal ) למציאת עץ פורש מינימלי באלגוריתם של קרוסקל בוחרים בכל פעם את הקשת בעלת המשקל המינימלי מבין הקשתות הקיימות , ובלבד שלא ייווצר מעגל . 6 . 3 . 1 האלגוריתם של קרוסקל אלגוריתם מילולי צעד : 1 בשלב ההתחלי קבוצת הקשתות הנה קבוצה ריקה ( £ < - ())) r צעד 12 יצור | v' | עצים כאשר כל קדקוד בגרף הנתון מגדיר עץ שהנו קבוצה בת איבר אחד . צעד : 3 מיין את קשתות העץ לפי סדר לא יורד , על סמך המשקלות המיוחסים להן . צעד : 4 לכל קשת , (« , ' 1 ) לפי הסדר שנקבע בצעד , 3 בצע ! 4 . 1 אם הקבוצה שאליה שייך הקדקוד u שונה מהקבוצה שאליה שייך הקדקוד , v אז בצע : E < -E v [( u , v )} 4 . 1 . 1 T T אין קשת מפרידה . משפט 6 . 2 . 5 נתון גרף בלתי מכוון קשיר G = { V , E ) קשת כלשהי ee E היא קשת מפרידה אם ורק אם e אינה שייכת לקבוצת קשתות כלשהי המהוות מעגל בגרף . G
|
|