עמוד:253

הקדקוד D שייך לשכבה 2 מאחר שניתן להגיע אליו מקדקוד המקור A דרך מסלול שאורכו 2 המתואר להלן : שוב , נצטרך לבחור בכל הקשתות הנוגעות לכל הקדקודים השייכים לשכבה 2 והמובילות לקדקודים שעדיין לא ביקרנו בהם . בדוגמה שלנו , לשכבה 2 שייך רק קדקוד אחד ויחיד - , D ודרך הקשת היחידה הנוגעת בו ( B , D ) לא ניתן להגיע לקדקוד שעדיין לא ביקרנו בו ( כיוון שבקדקוד B כבר ביקרנו . (! בשלב הזה נעצור את הסריקה כיוון שסיימנו את הביקור בכל קדקודי הגרף . בסוף התהליך , כאשר מסיימים לבקר בכל קדקודי הגרף , השכבה שאליה שייך הקדקוד תציין את אורך המסלול בעל האורך המינימלי ( מספר הקשתות הוא מינימלי ) מקדקוד המקור עד אליו . הערות r , האלגוריתם פועל על גרפים מכוונים ולא מכוונים כאחד . מאחר שברצוננו לבקר בכל קדקוד פעם אחת בלבד , נשתמש במערך בוליאני , used כך ש- used [ v ] יציין אם ביקרנו בקדקוד v או לאו . בתחילת האלגוריתם , עדיין לא גילינו את קדקודי הגרף ( ביקרנו בהם , ( ולכן עבור כל קדקוד v בגרף נציב ל- used [ v ] את הערך . FALSE כמו כן , נרצה לשמור עבור כל קדקוד מידע על זהות הקדקוד שביקרנו בו קודם . לכן נשתמש במערך , P כך -שP [ v ] יציין קדקוד בגרף שממנו הגענו ל-ע בעת הסריקה . . 2 הסימן P מציין P [ v ] -v מייצג הורה של הקדקוד v בעת הסריקה . בנוסף , נרצה לשמור עבור כל קדקוד u מידע על המרחק מהקדקוד S לקדקוד M לפיכך , נשתמש במערך dist כך ש- dist [«] יציין את המרחק מקדקוד המקור S לקדקוד . « בנוסף , נשתמש במבנה הנתונים תור , ( Q - Queue ) אשר ינהל את השכבות . כמו כן , נשתמש בפעולות הבסיסיות המוגדרות על תור , כגון : , insert ( g , w ) המוסיפה את האיבר w לתור . Q , Delete ( Q , v ) המסירה את האיבר שבחזית התור Q ושמה אותו ב-ע .

מטח : המרכז לטכנולוגיה חינוכית


לצפייה מיטבית ורציפה בכותר