Πώς μπορώ να εφαρμόσω ένα κατευθυνόμενο γράφημα στο Python;

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

1. Λίστα γειτνίασης (χρησιμοποιώντας ένα λεξικό)

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

* Εφαρμογή:

`` `Python

Κατηγορία DirectedGraph:

def __init __ (εαυτός):

self.graph ={} # λεξικό για την αποθήκευση της λίστας γειτνίασης

def add_node (self, node):

Εάν ο κόμβος δεν είναι σε self.graph:

self.graph [κόμβος] =[]

def add_edge (self, from_node, to_node):

Εάν από το_node δεν είναι στο self.graph:

self.add_node (from_node)

Εάν δεν είναι στο self.graph:

self.add_node (to_node) # ή δημιουργήστε ένα σφάλμα εάν χρειάζεστε να προστεθούν ρητά κόμβοι πρώτα

self.graph [from_node] .ppend (to_node)

def get_neighbors (εαυτός, κόμβος):

Εάν κόμβος στο self.graph:

Επιστρέψτε το self.graph [κόμβος]

αλλού:

Επιστροφή [] # ή δημιουργήστε ένα σφάλμα, ανάλογα με την επιθυμητή συμπεριφορά

def remove_node (self, node):

Εάν κόμβος στο self.graph:

del self.graph [κόμβος]

# Αφαιρέστε τις άκρες που δείχνουν * στον * τον διαγραμμένο κόμβο

για n σε self.graph:

Εάν ο κόμβος στο self.graph [n]:

self.graph [n] .Remove (κόμβος)

def remove_edge (self, from_node, to_node):

Εάν από το_node στο self.graph και στο to_node στο self.graph [from_node]:

self.graph [from_node] .remove (to_node)

def has_node (self, node):

Επιστροφή κόμβου στο self.graph

def has_edge (self, from_node, to_node):

Επιστροφή από_node in self.graph και to_node in self.graph [from_node]

def __str __ (εαυτός):

επιστροφή str (self.graph)

# Παράδειγμα χρήσης

γράφημα =DirectedGraph ()

graph.add_node ("a")

graph.add_node ("b")

graph.add_node ("c")

graph.add_edge ("a", "b")

graph.add_edge ("a", "c")

graph.add_edge ("b", "c")

εκτύπωση (γράφημα) # έξοδος:{'a':['b', 'c'], 'b':['c'], 'c':[]}

εκτύπωση (graph.get_neighbors ("a")) # έξοδος:['b', 'c']

εκτύπωση (graph.has_edge ("a", "b")) # έξοδος:true

graph.remove_edge ("a", "b")

εκτύπωση (γράφημα) # έξοδος:{'a':['c'], 'b':['c'], 'c':[]}

graph.remove_node ("b")

εκτύπωση (γράφημα) # έξοδος:{'a':['c'], 'c':[]}

`` `

* Πλεονεκτήματα:

* Απλό στην εφαρμογή.

* Αποτελεσματική για αραιά γραφήματα.

* Εύκολο να βρείτε γείτονες ενός κόμβου.

* Η προσθήκη και αφαίρεση των κόμβων/άκρων μπορεί να είναι σχετικά αποτελεσματική (O (1) κατά μέσο όρο για λεξικά, O (n) στη χειρότερη περίπτωση για `remove_node` λόγω της ρύθμισης των λιστών των άλλων κόμβων για την απομάκρυνση των άκρων που δείχνουν τον διαγραμμένο κόμβο).

* Μειονεκτήματα:

* Λιγότερο αποτελεσματικά για πυκνά γραφήματα (γραφήματα με σχεδόν όλες τις πιθανές άκρες).

* Έλεγχος εάν υπάρχει άκρη (εκτός από τη χρήση `has_edge ()`) απαιτεί την ρύθμιση της γειτονικής λίστας του κόμβου προέλευσης, ο οποίος μπορεί να είναι o (n) στη χειρότερη περίπτωση.

2. (Χρησιμοποιώντας μια λίστα 2D/Array)

* Έννοια: Χρησιμοποιήστε μια συστοιχία 2D (ή μια λίστα με λίστες στο Python) όπου "μήτρα [i] [j]` είναι 1 (ή `true ') αν υπάρχει μια κατευθυνόμενη άκρη από τον κόμβο` i' to node `j` και 0 (ή` false ') διαφορετικά.

* Εφαρμογή:

`` `Python

Κατηγορία DirectedGraphmatrix:

def __init __ (self, num_nodes):

self.num_nodes =num_nodes

self.matrix =[[0] * num_nodes για _ στην περιοχή (num_nodes)]

def add_edge (self, from_node, to_node):

αν 0 <=from_node self.matrix [from_node] [to_node] =1

αλλού:

εκτύπωση ("Μη έγκυροι δείκτες κόμβων.")

def remove_edge (self, from_node, to_node):

αν 0 <=from_node self.matrix [from_node] [to_node] =0

αλλού:

εκτύπωση ("Μη έγκυροι δείκτες κόμβων.")

def has_edge (self, from_node, to_node):

αν 0 <=from_node επιστροφή self.matrix [from_node] [to_node] ==1

αλλού:

εκτύπωση ("Μη έγκυροι δείκτες κόμβων.")

Επιστρέψτε ψευδώς

def get_neighbors (εαυτός, κόμβος):

Εάν 0 <=Κόμβος γείτονες =[]

για το I στην περιοχή (self.num_nodes):

αν self.matrix [κόμβος] [i] ==1:

γείτονες.append (i)

Επιστρέψτε τους γείτονες

αλλού:

εκτύπωση ("Μη έγκυρος δείκτης κόμβου.")

επιστροφή []

def __str __ (εαυτός):

Επιστροφή '\ n'.join ([' '.Join (χάρτης (str, σειρά)) για σειρά στο self.matrix])

# Παράδειγμα χρήσης:

Graph =DirectedGraphMatrix (4) # γράφημα με 4 κόμβους

graph.add_edge (0, 1)

graph.add_edge (0, 2)

graph.add_edge (1, 3)

εκτύπωση (γράφημα)

# Έξοδος:

# 0 1 1 0

# 0 0 0 1

# 0 0 0 0

# 0 0 0 0

εκτύπωση (graph.has_edge (0, 1)) # έξοδος:true

εκτύπωση (graph.get_neighbors (0)) # έξοδος:[1, 2]

`` `

* Πλεονεκτήματα:

* Γρήγορα για να ελέγξετε αν υπάρχει άκρη (O (1)).

* Απλό στην εφαρμογή.

* Μειονεκτήματα:

* Απαιτεί τον προκαθορισμό του αριθμού των κόμβων. Μπορεί να τροποποιηθεί για να αλλάξει το μέγεθος δυναμικά, αλλά αυτό μπορεί να γίνει δαπανηρό.

* Αναποτελεσματική για αραιά γραφήματα (απόβλητα πολύ μνήμη).

* Η προσθήκη/αφαίρεση των κόμβων μπορεί να είναι δαπανηρή επειδή πρέπει να αλλάξετε το μέγεθος ολόκληρου του πίνακα.

3. Χρησιμοποιώντας μια βιβλιοθήκη γραφημάτων (π.χ. NetworkX)

* Έννοια: Αξιοποιήστε τις υπάρχουσες βιβλιοθήκες γραφημάτων που παρέχουν βελτιστοποιημένες εφαρμογές και πληθώρα αλγορίθμων γραφημάτων. Το NetworkX είναι μια δημοφιλής επιλογή.

* Εφαρμογή:

`` `Python

Εισαγωγή δικτύου ως NX

# Δημιουργήστε ένα κατευθυνόμενο γράφημα

γράφημα =nx.digraph ()

# Προσθήκη κόμβων

graph.add_nodes_from (["a", "b", "c"])

# Προσθήκη άκρων

graph.add_edge ("a", "b")

graph.add_edge ("a", "c")

graph.add_edge ("b", "c")

# Ελέγξτε εάν υπάρχει άκρη

εκτύπωση (graph.has_edge ("a", "b")) # έξοδος:true

# Λάβετε γείτονες

εκτύπωση (λίστα (Graph.Successors ("a"))) # έξοδος:['b', 'c'] (διαδόχοι =εξερχόμενοι γείτονες)

# Αφαιρέστε μια άκρη

graph.remove_edge ("a", "b")

εκτύπωση (graph.has_edge ("a", "b")) # έξοδος:false

# Αφαιρέστε έναν κόμβο

graph.remove_node ("b")

εκτύπωση (graph.nodes ()) # έξοδος:['a', 'c']

# Μπορείτε να σχεδιάσετε το γράφημα (απαιτεί matplotlib)

# Εισαγωγή matplotlib.pyplot ως plt

# nx.draw (γράφημα, with_labels =true, node_color ="skyblue", node_size =1500, font_size =15)

# plt.show ()

`` `

* Πλεονεκτήματα:

* Ώριμη και καλά δοκιμασμένη βιβλιοθήκη.

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

* Ευκολότερη εκτέλεση σύνθετων εργασιών γραφημάτων.

* Υποστηρίζει την απεικόνιση γραφημάτων.

* Μειονεκτήματα:

* Ελαφρώς επιβάρυνση σε σύγκριση με την εφαρμογή της δικής σας δομής γραφήματος.

* Απαιτεί την εγκατάσταση εξωτερικής βιβλιοθήκης.

Επιλέγοντας τη σωστή εφαρμογή

* αραιά γραφήματα: Η λίστα γειτνίασης είναι γενικά η καλύτερη επιλογή.

* πυκνά γραφήματα: Το Matrix Adjacency μπορεί να είναι ταχύτερος για τους ελέγχους της ύπαρξης άκρων, αλλά καταναλώνει περισσότερη μνήμη. Εξετάστε τις συμφωνίες.

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

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

Βασικές εκτιμήσεις:

* Χρήση μνήμης: Οι λίστες γειτνίασης είναι πιο αποδοτικές από τη μνήμη για αραιά γραφήματα. Οι πίνακες γειτνίασης μπορούν να χρησιμοποιήσουν πολλή μνήμη, ειδικά για μεγάλα, αραιά γραφήματα.

* απόδοση: Οι πίνακες γειτνίασης παρέχουν o (1) αναζήτηση άκρων, ενώ οι λίστες γειτνίασης απαιτούν o (n) στη χειρότερη περίπτωση (όπου n είναι ο αριθμός των γειτόνων).

* Ευκολία χρήσης: Οι βιβλιοθήκες γραφημάτων παρέχουν ένα πιο βολικό και πλούσιο σε χαρακτηριστικά API.

* Μεταλλιμότητα έναντι αμετάβλητης: Αποφασίστε εάν πρέπει να τροποποιείτε συχνά τη δομή γραφημάτων. Οι λίστες γειτνίασης και οι μήτρες είναι μεταβλητοί. Τα γραφήματα NetworkX είναι επίσης μεταβλητά. Εάν χρειάζεστε ένα αμετάβλητο γράφημα, ίσως χρειαστεί να εξερευνήσετε εναλλακτικές δομές δεδομένων.

* σταθμισμένα γραφήματα: Εάν πρέπει να αντιπροσωπεύετε σταθμισμένα άκρα, μπορείτε να τροποποιήσετε τη λίστα γειτνίασης ή τη μήτρα για να αποθηκεύσετε τα βάρη άκρων. Για παράδειγμα, στον κατάλογο παρακολούθησης, θα μπορούσατε να αποθηκεύσετε ένα λεξικό του `to_node:weight` αντί για μια λίστα κόμβων. Το NetworkX έχει ενσωματωμένη υποστήριξη για σταθμισμένα γραφήματα.

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