Πώς να εφαρμόσετε τη δομή δεδομένων γραφήματος στο Golang

Προβλήματα που σχετίζονται με γραφήματα θα εμφανιστούν συχνά στη βιομηχανία λογισμικού. Είτε σε τεχνικές συνεντεύξεις είτε κατά την κατασκευή εφαρμογών που χρησιμοποιούν γραφήματα.

Τα γραφήματα είναι θεμελιώδεις δομές δεδομένων που χρησιμοποιούνται σε διάφορες εφαρμογές, που κυμαίνονται από κοινωνικά δίκτυα και συστήματα μεταφοράς έως μηχανές συστάσεων και ανάλυση δικτύου.

Τι είναι ένα γράφημα και πώς μπορείτε να εφαρμόσετε γραφήματα στο Go;

Τι είναι ένα γράφημα;

Ένα γράφημα είναι μια μη γραμμική δομή δεδομένων που αντιπροσωπεύει μια συλλογή κόμβων (ή κορυφών) και συνδέσεων μεταξύ τους (άκρες). Τα γραφήματα χρησιμοποιούνται ευρέως σε εφαρμογές λογισμικού που ασχολούνται σε μεγάλο βαθμό με συνδέσεις όπως δίκτυα υπολογιστών, κοινωνικά δίκτυα και άλλα.

Ένα γράφημα είναι ένα από τις δομές δεδομένων που πρέπει να γνωρίζετε ως προγραμματιστής. Τα γραφήματα παρέχουν έναν ισχυρό και ευέλικτο τρόπο μοντελοποίησης και ανάλυσης διαφόρων σεναρίων πραγματικού κόσμου, και αυτό τα καθιστά μια θεμελιώδη και βασική δομή δεδομένων στην επιστήμη των υπολογιστών.

Μια μεγάλη ποικιλία αλγορίθμων επίλυσης προβλημάτων που χρησιμοποιούνται στον κόσμο του λογισμικού βασίζονται σε γραφήματα. Μπορείτε να κάνετε μια βαθύτερη βουτιά στα γραφήματα σε αυτό οδηγός για τη δομή δεδομένων γραφήματος.

Εφαρμογή γραφήματος στο Golang

Τις περισσότερες φορές για να εφαρμόσετε μια δομή δεδομένων μόνοι σας, πρέπει να την εφαρμόσετε αντικειμενοστραφής προγραμματισμός (OOP) έννοιες, αλλά υλοποίηση του OOP στο Go δεν είναι ακριβώς το ίδιο όπως το έχετε σε άλλες γλώσσες όπως η Java και η C++.

Το Go χρησιμοποιεί δομές, τύπους και διεπαφές για την υλοποίηση εννοιών OOP και αυτά είναι όλα όσα χρειάζεστε για να εφαρμόσετε μια δομή δεδομένων γραφήματος και τις μεθόδους της.

Ένα γράφημα αποτελείται από κόμβους (ή κορυφές) και ακμές. Ένας κόμβος είναι μια οντότητα ή ένα στοιχείο στο γράφημα. Ένα παράδειγμα κόμβου είναι μια συσκευή σε ένα δίκτυο ή ένα άτομο σε ένα κοινωνικό δίκτυο. Ενώ μια άκρη είναι μια σύνδεση ή σχέση μεταξύ δύο κόμβων.

Για να εφαρμόσετε ένα γράφημα στο Go, πρέπει πρώτα να ορίσετε μια δομή κόμβου της οποίας η ιδιότητα θα είναι οι γείτονές της. Οι γείτονες ενός κόμβου είναι οι άλλοι κόμβοι που συνδέονται απευθείας με τον κόμβο.

Στα κατευθυνόμενα γραφήματα, οι ακμές έχουν κατευθύνσεις, επομένως μόνο οι κόμβοι στους οποίους δείχνει ένας δεδομένος κόμβος θεωρούνται γείτονές του. Ενώ στα μη κατευθυνόμενα γραφήματα, όλοι οι κόμβοι που μοιράζονται μια άκρη με έναν κόμβο είναι οι γείτονές του.

Ο παρακάτω κώδικας δείχνει πώς το Κόμβος η δομή φαίνεται:

type Node struct {
 Neighbors []*Node
}

Σε αυτό το άρθρο, η εστίαση θα είναι σε ένα μη κατευθυνόμενο γράφημα. Ωστόσο, για καλύτερη σαφήνεια, ορίστε τι α Κόμβος Η δομή για ένα κατευθυνόμενο γράφημα μπορεί να μοιάζει με:

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

Με αυτόν τον ορισμό, το Έξω Γείτονες slice θα αποθηκεύσει τους κόμβους στους οποίους υπάρχουν εξερχόμενες ακμές από τον τρέχοντα κόμβο και το Στους Γείτονες slice θα αποθηκεύσει τους κόμβους από τους οποίους υπάρχουν εισερχόμενες ακμές στον τρέχοντα κόμβο.

Θα εφαρμόσετε το γράφημα χρησιμοποιώντας έναν χάρτη ακεραίων σε κόμβους. Αυτός ο χάρτης χρησιμεύει ως λίστα γειτνίασης (ο κοινός τρόπος αναπαράστασης γραφημάτων). Το κλειδί χρησιμεύει ως μοναδικό αναγνωριστικό για έναν κόμβο, ενώ η τιμή θα είναι ο κόμβος.

Ο παρακάτω κώδικας δείχνει το Γραφική παράσταση δομή:

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

Το ακέραιο κλειδί μπορεί επίσης να φανταστεί ως την τιμή του κόμβου στον οποίο αντιστοιχίζεται. Αν και σε σενάρια πραγματικού κόσμου, ο κόμβος σας θα μπορούσε να είναι μια διαφορετική δομή δεδομένων που αντιπροσωπεύει το προφίλ ενός ατόμου ή κάτι παρόμοιο. Σε τέτοιες περιπτώσεις, θα πρέπει να έχετε τα δεδομένα ως μία από τις ιδιότητες της δομής 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 Η συνάρτηση προσθέτει έναν νέο κόμβο στο γράφημα με το αναγνωριστικό να του έχει μεταβιβαστεί ως παράμετρος. Η συνάρτηση ελέγχει εάν υπάρχει ήδη ένας κόμβος με το ίδιο αναγνωριστικό πριν τον προσθέσει στο γράφημα.

Προσθήκη ακμής στο γράφημα

Η επόμενη σημαντική μέθοδος της δομής δεδομένων γραφήματος είναι η συνάρτηση προσθήκης ακμής (δηλαδή δημιουργίας σύνδεσης μεταξύ δύο κόμβων). Δεδομένου ότι το γράφημα εδώ είναι μη κατευθυνόμενο, δεν χρειάζεται να ανησυχείτε για την κατεύθυνση κατά τη δημιουργία ακμών.

Εδώ είναι η συνάρτηση για να προσθέσετε μια άκρη μεταξύ δύο κόμβων στο γράφημα:

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 παρέχει ήδη μια εξαιρετική πλατφόρμα για την ανάπτυξη αποτελεσματικών εφαρμογών λογισμικού, αλλά όταν παραμελείτε το καλό πρακτικές ανάπτυξης, μπορεί να προκαλέσει διαφορετικά προβλήματα για την αρχιτεκτονική και την απόδοση της εφαρμογής σας.

Μια σημαντική βέλτιστη πρακτική είναι η υιοθέτηση των σωστών δομών δεδομένων, όπως πίνακες, συνδεδεμένες λίστες και γραφήματα, για διαφορετικές ανάγκες. Με αυτό, μπορείτε να διασφαλίσετε ότι η εφαρμογή σας λειτουργεί σωστά και να ανησυχείτε λιγότερο για τα σημεία συμφόρησης απόδοσης ή τις αστοχίες που μπορεί να προκύψουν.