I denne opplæringen lærer du hva en tilknytningsliste er. Du finner også arbeidseksempler på nærhetsliste i C, C ++, Java og Python.
En tilknytningsliste representerer en graf som en rekke lenker.
Indeksen til matrisen representerer et toppunkt, og hvert element i den tilknyttede listen representerer de andre toppunktene som danner en kant med toppunktet.
Tilstøtning Liste representasjon
En graf og dens tilsvarende representasjon for tilstøtningslisten vises nedenfor.
Tilstøtning Liste representasjon
En nærhetsliste er effektiv når det gjelder lagring fordi vi bare trenger å lagre verdiene for kantene. For en sparsom graf med millioner av hjørner og kanter kan dette bety mye lagret plass.
Støtte for tilgrenseliste
Den enkleste tilknytningslisten trenger en nodedatastruktur for å lagre et toppunkt og en grafdatastruktur for å organisere nodene.
Vi holder oss nær den grunnleggende definisjonen av en graf - en samling av hjørner og kanter (V, E). For enkelhets skyld bruker vi en umerket graf i motsetning til en merket, det vil si at hjørnene er identifisert ved indeksene 0,1,2,3.
La oss grave i datastrukturene som spilles her.
struct node ( int vertex; struct node* next; ); struct Graph ( int numVertices; struct node** adjLists; );
Ikke la struct node** adjListsovervelde deg.
Alt vi sier er at vi vil lagre en peker til struct node*. Dette er fordi vi ikke vet hvor mange hjørner grafen vil ha, og derfor kan vi ikke opprette en rekke lenker på kompileringstidspunktet.
Tilstøtningsliste C ++
Det er den samme strukturen, men ved å bruke den innebygde listen STL-datastrukturer til C ++, gjør vi strukturen litt renere. Vi er også i stand til å abstrakte detaljene i implementeringen.
class Graph ( int numVertices; list *adjLists; public: Graph(int V); void addEdge(int src, int dest); );
Tilstøtningsliste Java
Vi bruker Java Collections til å lagre Array of Linked Lists.
class Graph ( private int numVertices; private LinkedList adjLists(); )
Typen LinkedList bestemmes av hvilke data du vil lagre i den. For en merket graf kan du lagre en ordbok i stedet for et heltall
Tilstøtningsliste Python
Det er en grunn til at Python får så mye kjærlighet. En enkel ordbok med hjørner og kantene er en tilstrekkelig fremstilling av en graf. Du kan gjøre toppunktet så komplekst som du vil.
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 og C / C ++ eksempler
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); )
