In deze tutorial leer je wat een aangrenzende lijst is. Ook vindt u werkende voorbeelden van een aangrenzende lijst in C, C ++, Java en Python.
Een aangrenzende lijst vertegenwoordigt een grafiek als een reeks gekoppelde lijsten.
De index van de array vertegenwoordigt een hoekpunt en elk element in de gekoppelde lijst vertegenwoordigt de andere hoekpunten die een rand vormen met het hoekpunt.
Adjacency List-weergave
Een grafiek en de equivalente weergave van de aangrenzende lijst worden hieronder weergegeven.
Adjacency List-weergave
Een aangrenzende lijst is efficiënt in termen van opslag omdat we alleen de waarden voor de randen hoeven op te slaan. Voor een spaarzame grafiek met miljoenen hoekpunten en randen kan dit veel bespaarde ruimte betekenen.
Nabijheidslijststructuur
De eenvoudigste aangrenzende lijst heeft een knooppuntgegevensstructuur nodig om een hoekpunt op te slaan en een grafiekgegevensstructuur om de knooppunten te organiseren.
We blijven dicht bij de basisdefinitie van een graaf: een verzameling hoekpunten en randen (V, E). Voor de eenvoud gebruiken we een niet-gelabelde graaf in plaats van een gelabelde, dwz de hoekpunten worden geïdentificeerd door hun indices 0,1,2,3.
Laten we eens kijken naar de datastructuren die hier spelen.
struct node ( int vertex; struct node* next; ); struct Graph ( int numVertices; struct node** adjLists; );
Laat je niet struct node** adjListsoverweldigen.
Het enige wat we zeggen is dat we een aanwijzer willen opslaan struct node*. Dit komt omdat we niet weten hoeveel hoekpunten de grafiek zal hebben en dus kunnen we tijdens het compileren geen array van gekoppelde lijsten maken.
Nabijheidslijst C ++
Het is dezelfde structuur maar door gebruik te maken van de ingebouwde lijst STL datastructuren van C ++, maken we de structuur een beetje schoner. We zijn ook in staat om de details van de implementatie te abstraheren.
class Graph ( int numVertices; list *adjLists; public: Graph(int V); void addEdge(int src, int dest); );
Nabijheidslijst Java
We gebruiken Java-verzamelingen om de reeks gekoppelde lijsten op te slaan.
class Graph ( private int numVertices; private LinkedList adjLists(); )
Het type LinkedList wordt bepaald door de gegevens die u erin wilt opslaan. Voor een gelabelde grafiek kunt u een woordenboek opslaan in plaats van een geheel getal
Nabijheidslijst Python
Er is een reden waarom Python zoveel liefde krijgt. Een eenvoudig woordenboek van hoekpunten en zijn randen is een voldoende weergave van een grafiek. U kunt het hoekpunt zelf zo complex maken als u wilt.
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 en C / C ++ voorbeelden
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); )
