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

שלום לכולם.

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

אז בואו נתחיל. אבל לא מההתחלה - אני חושב שכולנו כבר יודעים מה זה גרף ומהו (מכוון, לא מכוון, משוקלל, לא משוקלל, עם או בלי קצוות ולולאות מרובות).

אז בוא נלך. אילו אפשרויות למבני נתונים ל"אחסון גרפים" יש לנו?

1. מבני נתונים מטריצות

1.1 מטריקס שכנות. מטריצת הסמיכות היא מטריצה ​​שבה כותרות השורה והעמודות מתאימות למספרי קודקודי הגרף, והערך של כל אחד מהאלמנטים שלה a(i,j) נקבע על פי נוכחות או היעדר קצוות בין קודקודים i ו-j (ברור שעבור גרף לא מכוון מטריצה ​​כזו תהיה סימטרית, או שאנחנו יכולים להסכים שאנחנו מאחסנים את כל הערכים רק מעל האלכסון הראשי). עבור גרפים לא משוקללים, ניתן להגדיר את a(i,j) לפי מספר הקצוות מ-i עד j (אם אין קצה כזה, אז a(i,j)= 0), ולגרפים משוקלל, גם לפי המשקל (משקל כולל) של הקצוות המוזכרים.

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

2. מבני נתונים של ספירה

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

2.2 רשימה של צלעות. מבנה נתונים פופולרי למדי. רשימת הקצוות, כפי שאומר לנו קפטן ברור, היא למעשה רשימה של קצוות של הגרף, שכל אחד מהם מצוין על ידי קודקוד ההתחלה, קודקוד הסיום (עבור גרפים לא מכוונים הסדר לא חשוב כאן, אם כי לאיחוד ניתן השתמש בכללים שונים, למשל, ציון הקודקודים לפי סדר הגדלת) ומשקל (עבור גרפים משוקללים בלבד).

אתה יכול להסתכל על רשימות המטריצות המפורטות לעיל ביתר פירוט (ועם איורים), למשל, כאן.

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

כאן מצאתי את ההסבר הכי מובן (עבור עצמי): ejuo.livejournal.com/4518.html

3. Adjacency Vector ומערך Adjacency Associative

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

3.1 וקטור סמיכות

מקרה (a1): גרף לא משוקלל

נקרא לוקטור סמיכות לגרף לא משוקלל קבוצה מסודרת של מספר זוגי של מספרים שלמים (a[2i], a[2i+1],..., כאשר i ממוספר c 0), שבה כל זוג מספרים הוא a[2i], a[2i+1 ] מציין קצה גרף בין הקודקודים a[2i] ו-a[2i+1], בהתאמה.
פורמט הקלטה זה אינו מכיל מידע לגבי האם הגרף מכוון (שתי האפשרויות אפשריות). בעת שימוש בפורמט הדיגרף, הקצה נחשב למכוון מ-a[2i] ל-a[2i+1]. כאן ולמטה: עבור גרפים לא מכוונים, במידת הצורך, ניתן ליישם דרישות לסדר הקודקודים של רישום (לדוגמה, שהקודקוד עם הערך הנמוך של המספר שהוקצה לו מגיע ראשון).

ב-C++, רצוי לציין וקטור סמיכות באמצעות std::vector, ומכאן שמו של מבנה הנתונים הזה.

מקרה (a2): גרף לא משוקלל, משקלי הקצוות הם מספר שלם

באנלוגיה למקרה (a1), אנו קוראים לווקטור הסמיכות עבור גרף משוקלל עם משקלי קצה שלמים קבוצה מסודרת (מערך דינמי) של מספרים (a[3i], a[3i+1], a[3i+2], ..., כאשר i ממוספר c 0), כאשר כל "שלישייה" של מספרים a[3i], a[3i+1], a[3i+2] מציינת קצה של הגרף בין קודקודים הממוספרים a[3i] ו-a[3i+1], בהתאמה, והערך a [3i+2] הוא המשקל של קצה זה. גרף כזה יכול להיות גם מכוון או לא.

מקרה (ב): גרף לא משוקלל, משקלי קצה שאינם שלמים

מכיוון שאי אפשר לאחסן אלמנטים הטרוגניים במערך אחד (וקטור), למשל, היישום הבא אפשרי. הגרף מאוחסן בזוג וקטורים, שבהם הווקטור הראשון הוא וקטור הסמיכות של הגרף מבלי לציין את המשקולות, והווקטור השני מכיל את המשקולות התואמות (יישום אפשרי עבור C++: std::pair ). לפיכך, עבור קצה המוגדר על ידי זוג קודקודים תחת אינדקסים 2i, 2i+1 של הווקטור הראשון, המשקל יהיה שווה לאלמנט מתחת לאינדקס i של הווקטור השני.

ובכן, למה זה נחוץ?

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

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

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

3.2 מערך סמיכות אסוציאטיבית

לכן, אם הגישה לקצה מסוים, משקלו ומאפיינים אחרים קריטיים עבורנו, ודרישות הזיכרון אינן מאפשרות לנו להשתמש במטריצת הסמיכות, אז בואו נחשוב כיצד נוכל לשנות את וקטור הסמיכות כדי לפתור בעיה זו. אז, המפתח הוא קצה של הגרף, אותו ניתן לציין כזוג מסודר של מספרים שלמים. איך זה נראה? זה לא מפתח במערך אסוציאטיבי? ואם כן, למה אנחנו לא מיישמים את זה? תנו לנו מערך אסוציאטיבי שבו כל מפתח - זוג מספרים שלמים מסודר - ישויך לערך - מספר שלם או מספר ממשי המציין את משקל הקצה. ב-C++, רצוי ליישם מבנה זה על סמך מיכל std::map (std::map , int> או std::map , double>), או std::multimap אם צפויים קצוות מרובים. ובכן, יש לנו מבנה לאחסון גרפים שתופס פחות זיכרון ממבני "מטריקס", יכול להגדיר גרפים עם מספר לולאות וקצוות, ואפילו אין לו דרישות מחמירות לאי-שליליות של מספרי קודקוד (אני לא יודע מי צריך את זה, אבל בכל זאת).

4. מבני נתונים מלאים, אבל משהו חסר

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

אז, תנו לנו גרף לא משוקלל, שלכל קצה שלו יש צורך לאחסן, למשל, 2 תכונות נוספות המצוינות במספרים שלמים. במקרה זה, ניתן להגדיר את וקטור הסמיכות שלו כקבוצה מסודרת לא של "זוגות", אלא של "רביעיות" של מספרים שלמים (a[2i], a[2i+1], a[2i+2], a [2i+3]...), כאשר a[2i+2] ו-a[2i+3] יקבעו את המאפיינים של הקצה המתאים. עבור גרף עם משקלים שלמים של קצוות, הסדר בדרך כלל דומה (ההבדל היחיד יהיה שהתכונות ילכו אחרי משקל הקצה ויצוינו על ידי האלמנטים a[2i+3] ו-a[2i+4] , והקצה עצמו יצוין לא 4, אלא 5 מספרים מסודרים). ועבור גרף עם משקלי קצה שאינם שלמים, ניתן לכתוב את התכונות ברכיב הלא משוקלל שלו.

כאשר משתמשים במערך סמיכות אסוציאטיבית עבור גרפים עם משקלי קצה שלמים, ניתן לציין כערך לא מספר בודד, אלא מערך (וקטור) של מספרים המציינים, בנוסף למשקל של קצה, את כל שאר ההכרחי שלו. מאפיינים. יחד עם זאת, אי נוחות למקרה של משקלים שאינם שלמים יהיה הצורך לציין סימן עם מספר נקודה צפה (כן, זו אי נוחות, אבל אם אין כל כך הרבה סימנים כאלה, ואם לא. אל תגדיר אותם "מסובכים" מדי כפול, אז יכול להיות שזה כלום). המשמעות היא שב-C++ ניתן להגדיר מערכי סמיכות אסוציאטיביים מורחבים באופן הבא: std::map , std::vector> או std::map , std::vector, שבו הערך הראשון ב-"key-value-vector" יהיה משקל הקצה, ולאחר מכן ממוקמים הייעודים המספריים של המאפיינים שלו.

ספרות:

על גרפים ואלגוריתמים באופן כללי:

1. קורמן, תומאס ה., לייזרסון, צ'ארלס הראשון, ריבסט, רונלד ל., סטיין, קליפורד. אלגוריתמים: בנייה וניתוח, מהדורה 2: טרנס. מאנגלית – M.: Williams Publishing House, 2011.
2. הררי פרנק. תורת הגרפים. מ.: מיר, 1973.
דו"ח המחבר על אותם מערך וקטור ואסוציאטיבי של סמיכות:
3. Chernoukhov S.A. וקטור סמיכות ומערך סמיכות אסוציאטיבית כדרכים לייצוג ואחסון גרפים / SA Chernouhov. וקטור סמיכות ומפת סמיכות כמבני נתונים לייצוג גרף // אוסף מאמרים של הכנס הבינלאומי המדעי והמעשי "בעיות ביישום התוצאות של פיתוחים חדשניים ודרכים לפתור אותן" (סראטוב, 14.09.2019 בספטמבר 2019). – Sterlitamak: AMI, 65, p. 69-XNUMX
מקורות מקוונים שימושיים בנושא:
4. prog-cpp.ru/data-graph
5. ejuo.livejournal.com/4518.html

מקור: www.habr.com