כיצד ליישם את מבנה נתוני הגרף בגולנג

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

גרפים הם מבני נתונים בסיסיים המשמשים ביישומים שונים, החל מרשתות חברתיות ומערכות תחבורה ועד למנועי המלצות וניתוח רשתות.

מהו גרף, וכיצד ניתן ליישם גרפים ב-Go?

מה זה גרף?

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

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

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

יישום גרף בגולנג

רוב הפעמים כדי ליישם מבנה נתונים בעצמך, אתה צריך ליישם תכנות מונחה עצמים (OOP) מושגים, אבל יישום OOP ב-Go זה לא בדיוק כמו שיש לך בשפות אחרות כמו Java ו-C++.

Go משתמשת במבנים, סוגים וממשקים כדי ליישם מושגי OOP, וזה כל מה שאתה צריך כדי ליישם מבנה נתוני גרף והשיטות שלו.

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

כדי ליישם גרף ב-Go, תחילה עליך להגדיר מבנה צומת שהנכס שלו יהיה השכנים שלו. השכנים של צומת הם הצמתים האחרים המחוברים ישירות לצומת.

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

הקוד הבא מדגים כיצד צוֹמֶת מראה מבנה:

type Node struct {
 Neighbors []*Node
}

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

type Node struct {
 OutNeighbors []*Node // outgoing edges
 InNeighbors []*Node // incoming edges
}

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

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

הקוד הבא מציג את גרָף מבנה:

type Graph struct {
 nodes map[int]*Node
}

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

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

funcNewGraph() *Graph {
return &Graph{
 nodes: make(map[int]*Node),
 }
}

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

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

הוספת צומת לגרף

כדי להוסיף צומת חדש לגרף, אתה צריך את פונקציית ההכנסה שנראית כך:

func(g *Graph)AddNode(nodeID int) {
if _, exists := g.nodes[nodeID]; !exists {
 newNode := &Node{
 Neighbors: []*Node{},
 }
 g.nodes[nodeID] = newNode
 fmt.Println("New node added to graph")
 } else {
 fmt.Println("Node already exists!")
 }
}

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

הוספת Edge לגרף

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

הנה הפונקציה להוסיף קצה בין שני צמתים בגרף:

func(g *Graph)AddEdge(nodeID1, nodeID2 int) {
 node1 := g.nodes[nodeID1]
 node2 := g.nodes[nodeID2]
 node1.Neighbors = append(node1.Neighbors, node2)
 node2.Neighbors = append(node2.Neighbors, node1)
}

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

הסרת קצה מהגרף

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

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

להלן היישום של RemoveEdge פוּנקצִיָה:

func(g *Graph)removeEdge(node, neighbor *Node) {
 index := -1
for i, n := range node.Neighbors {
if n == neighbor {
 index = i
break
 }
 }
if index != -1 {
 node.Neighbors = 
append(node.Neighbors[:index], node.Neighbors[index+1:]...)
 }
}
func(g *Graph)RemoveEdge(node, neighbor *Node) {
 g.removeEdge(node, neighbor)
 g.removeEdge(neighbor, node)
 fmt.Println("Edge successfully removed")
}

ה RemoveEdge הפונקציה מקבלת שני צמתים כפרמטרים ומחפשת את האינדקס של הצומת השני (השכן) ברשימת השכנים של הצומת הראשי. לאחר מכן הוא ממשיך להסיר את השכן צוֹמֶת. שכנים באמצעות טכניקה הנקראת פורסים את הנתח.

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

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

הסרת צומת מהגרף

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

func(g *Graph)RemoveNode(nodeID int) {
 node, exists := g.nodes[nodeID]
if !exists {
 fmt.Println("Node doesn't exist")
return
 }
for _, neighbor := range node.Neighbors {
 g.RemoveEdge(node, neighbor)
 }
delete(g.nodes, nodeID)
 fmt.Println("Node deleted successfully")
}

הפונקציה מקבלת את המזהה של הצומת שאתה צריך להסיר. הוא בודק אם הצומת קיים לפני שהוא ממשיך להסיר את כל הקצוות שלו. לאחר מכן הוא מוחק את הצומת מהגרף באמצעות המובנה של Go לִמְחוֹק פוּנקצִיָה.

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

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

בנה תוכנה אופטימלית תוך שימוש במבני הנתונים הנכונים

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

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