מטריצת שכנות – הבדלי גרסאות

[[תמונהקובץ:AdjacencyMatrix.png|250px|שמאל|ממוזער|דוגמה למטריצת שכנות של גרף לא מכוון]]

'''מטריצת שכנוּת''' (גם '''מטריצת סמיכויות''' או מטריצת שכנויות) היא שיטה לייצוג [[גרף מכוון]] בעל <math>n</math> צמתים בעזרת [[מטריצה ריבועית]] בגודל <math>n \times n</math>, שערכי תאיה הם 0 או 1.

תא (i,j) בגרף מתאר את קיומה (או העדרה) של הקשת המכוונת מקודקוד i לקודקוד j בגרף. אם אין קשת כזו, הערך בתא במטריצה יהיה 0. אם יש קודקוד כזה, אזי הערך יהיה 1. פעמים רבות דנים בתורת הגרפים [[גרף פשוט|בגרפים פשוטים]];

מטריצת שכנויות של [[גרף לא מכוון]] היא סימטרית. זאת משום שבגרף לא מכוון אין כיוון לקשתות ולכן, אם קיימת קשת מ-i ל-j אזי קיימת קשת מ-j ל-i. גרפים שאינם מכוונים נהוג לשמור רק את המשולש העליון של מטריצת השכנויות.

בגרפים שאינם פשוטים, ייתכנו מספר [[תורת הגרפים|קשתות מקבילות]] בין אותו זוג צמתים. במקרה זה,

יחד עם זאת, אלגוריתמים בסיסיים רבים (כמו [[DFS]], [[BFS]], מיון טופולוגי וכו') רצים בזמן <math>\ O(|V|+|E|)</math> כאשר <math>\ |V|</math> מסמן את מספר הקודקודים ו-<math>\ |E|</math> את מספר הקשתות. בשימוש במטריצת שכנות, הסיבוכיות היא לכל הפחות כגודל המטריצה, כלומר <math>\ O(|V|^2)</math>.