גרפים כמטריצת סמיכויות
ייצוג ע"י מטריצת
סמיכויות הוא פשוט יותר ליישום. אנו מניחים שהקודקודים שהקודקודים
ממוספרים בסדר שרירותי. מטריצת הסמיכויות המייצגת גרף G
היא מטריצה שממדיה |V|x|V| .
בתא i,j יהיה 1 אם קיימת קשת
בין קודקוד i לקודקוד j
או 0 במקרה ואין קשת כזאת.
דוגמא נוספת
קיימת
בסוף פרק זה.
נשים לב לסימטריה
סביב האלכסון הראשי. במטריצה המייצגת גרף לא מכוון תמיד
מטריצה תהיה המוחלפת
של עצמה. ביישומים משתלם לאחסן רק את האיברים של מטריצת
הסמיכויות הנמצאים באלכסון העליון ובכך לצמצם בחצי את כמות
הזיכרון הנדרשת לאיחסון.
בדומה לייצוג ע"י
רשימת סמיכות, גם ייצוג ע"י מטריצה סמיכויות יכול לשמש
לייצוג גרפים ממושקלים. בתא i,j
נשים את משקל הקשת בין i ל j,
אם הקשת אינה קיימת נוכל לשים NULL,
0 או INF תלוי בפעולות שאנו רוצים
לבצע על המטריצה.
