Σε αυτό το σεμινάριο, θα μάθετε τι είναι μια λίστα γειτνίασης. Επίσης, θα βρείτε λειτουργικά παραδείγματα λίστας γειτνίασης σε C, C ++, Java και Python.
Μια λίστα γειτνίασης αντιπροσωπεύει ένα γράφημα ως μια σειρά συνδεδεμένων λιστών.
Ο δείκτης του πίνακα αντιπροσωπεύει μια κορυφή και κάθε στοιχείο στη συνδεδεμένη λίστα του αντιπροσωπεύει τις άλλες κορυφές που σχηματίζουν ένα άκρο με την κορυφή.
Αντιπροσώπευση λίστας προσαρμογής
Ένα γράφημα και η αντίστοιχη αναπαράσταση λίστας γειτνίασης παρουσιάζονται παρακάτω.
Αντιπροσώπευση λίστας προσαρμογής
Μια λίστα γειτνίασης είναι αποτελεσματική από την άποψη του χώρου αποθήκευσης, επειδή πρέπει να αποθηκεύουμε μόνο τις τιμές για τις άκρες. Για ένα αραιό γράφημα με εκατομμύρια κορυφές και άκρα, αυτό μπορεί να σημαίνει πολύ αποθηκευμένο χώρο.
Δομή λίστας προσαρμοστικότητας
Η απλούστερη λίστα γειτνίασης χρειάζεται μια δομή δεδομένων κόμβου για την αποθήκευση μιας κορυφής και μια δομή δεδομένων γραφήματος για την οργάνωση των κόμβων.
Παραμένουμε κοντά στον βασικό ορισμό ενός γραφήματος - μια συλλογή κορυφών και άκρων (V, E). Για απλότητα, χρησιμοποιούμε ένα γράφημα χωρίς ετικέτα σε αντίθεση με ένα επισημασμένο, δηλαδή οι κορυφές αναγνωρίζονται από τους δείκτες τους 0,1,2,3.
Ας ανακαλύψουμε τις δομές δεδομένων που παίζουμε εδώ.
struct node ( int vertex; struct node* next; ); struct Graph ( int numVertices; struct node** adjLists; );
Μην αφήσετε να struct node** adjListsσας κατακλύσει.
Το μόνο που λέμε είναι ότι θέλουμε να αποθηκεύσουμε έναν δείκτη struct node*. Αυτό συμβαίνει επειδή δεν γνωρίζουμε πόσες κορυφές θα έχει το γράφημα και, επομένως, δεν μπορούμε να δημιουργήσουμε έναν πίνακα συνδεδεμένων λιστών κατά τη μεταγλώττιση.
Λίστα Adjacency C ++
Είναι η ίδια δομή, αλλά χρησιμοποιώντας τη ενσωματωμένη δομή δεδομένων STL λίστας του C ++, κάνουμε τη δομή λίγο πιο καθαρή. Είμαστε επίσης σε θέση να αφαιρέσουμε τις λεπτομέρειες της εφαρμογής.
class Graph ( int numVertices; list *adjLists; public: Graph(int V); void addEdge(int src, int dest); );
Λίστα προσαρμογών Java
Χρησιμοποιούμε τις Συλλογές Java για να αποθηκεύσουμε το Array of Linked Lists
class Graph ( private int numVertices; private LinkedList adjLists(); )
Ο τύπος LinkedList καθορίζεται από τα δεδομένα που θέλετε να αποθηκεύσετε σε αυτό. Για ένα γράφημα με ετικέτα, μπορείτε να αποθηκεύσετε ένα λεξικό αντί για έναν ακέραιο
Λίστα Adjacency Python
Υπάρχει ένας λόγος που η Python παίρνει τόση αγάπη. Ένα απλό λεξικό κορυφών και τα άκρα του είναι μια επαρκής αναπαράσταση ενός γραφήματος. Μπορείτε να κάνετε την ίδια την κορυφή τόσο περίπλοκη όσο θέλετε.
graph = ('A': set(('B', 'C')), 'B': set(('A', 'D', 'E')), 'C': set(('A', 'F')), 'D': set(('B')), 'E': set(('B', 'F')), 'F': set(('C', 'E')))
Παραδείγματα Python, Java και C / C ++
Python Java C C ++ # Adjascency List representation in Python class AdjNode: def __init__(self, value): self.vertex = value self.next = None class Graph: def __init__(self, num): self.V = num self.graph = (None) * self.V # Add edges def add_edge(self, s, d): node = AdjNode(d) node.next = self.graph(s) self.graph(s) = node node = AdjNode(s) node.next = self.graph(d) self.graph(d) = node # Print the graph def print_agraph(self): for i in range(self.V): print("Vertex " + str(i) + ":", end="") temp = self.graph(i) while temp: print(" -> ()".format(temp.vertex), end="") temp = temp.next print(" ") if __name__ == "__main__": V = 5 # Create graph and edges graph = Graph(V) graph.add_edge(0, 1) graph.add_edge(0, 2) graph.add_edge(0, 3) graph.add_edge(1, 2) graph.print_agraph()
// Adjascency List representation in Java import java.util.*; class Graph ( // Add edge static void addEdge(ArrayList am, int s, int d) ( am.get(s).add(d); am.get(d).add(s); ) public static void main(String() args) ( // Create the graph int V = 5; ArrayList am = new ArrayList (V); for (int i = 0; i < V; i++) am.add(new ArrayList()); // Add edges addEdge(am, 0, 1); addEdge(am, 0, 2); addEdge(am, 0, 3); addEdge(am, 1, 2); printGraph(am); ) // Print the graph static void printGraph(ArrayList am) ( for (int i = 0; i < am.size(); i++) ( System.out.println("Vertex " + i + ":"); for (int j = 0; j " + am.get(i).get(j)); ) System.out.println(); ) ) )
// Adjascency List representation in C #include #include struct node ( int vertex; struct node* next; ); struct node* createNode(int); struct Graph ( int numVertices; struct node** adjLists; ); // Create a node struct node* createNode(int v) ( struct node* newNode = malloc(sizeof(struct node)); newNode->vertex = v; newNode->next = NULL; return newNode; ) // Create a graph struct Graph* createAGraph(int vertices) ( struct Graph* graph = malloc(sizeof(struct Graph)); graph->numVertices = vertices; graph->adjLists = malloc(vertices * sizeof(struct node*)); int i; for (i = 0; i adjLists(i) = NULL; return graph; ) // Add edge void addEdge(struct Graph* graph, int s, int d) ( // Add edge from s to d struct node* newNode = createNode(d); newNode->next = graph->adjLists(s); graph->adjLists(s) = newNode; // Add edge from d to s newNode = createNode(s); newNode->next = graph->adjLists(d); graph->adjLists(d) = newNode; ) // Print the graph void printGraph(struct Graph* graph) ( int v; for (v = 0; v numVertices; v++) ( struct node* temp = graph->adjLists(v); printf(" Vertex %d: ", v); while (temp) ( printf("%d -> ", temp->vertex); temp = temp->next; ) printf(""); ) ) int main() ( struct Graph* graph = createAGraph(4); addEdge(graph, 0, 1); addEdge(graph, 0, 2); addEdge(graph, 0, 3); addEdge(graph, 1, 2); printGraph(graph); return 0; )
// Adjascency List representation in C++ #include using namespace std; // Add edge void addEdge(vector adj(), int s, int d) ( adj(s).push_back(d); adj(d).push_back(s); ) // Print the graph void printGraph(vector adj(), int V) ( for (int d = 0; d < V; ++d) ( cout << " Vertex " << d << ":"; for (auto x : adj(d)) cout < " << x; printf(""); ) ) int main() ( int V = 5; // Create a graph vector adj(V); // Add edges addEdge(adj, 0, 1); addEdge(adj, 0, 2); addEdge(adj, 0, 3); addEdge(adj, 1, 2); printGraph(adj, V); )
