I denna handledning lär du dig vad en angränsningslista är. Du hittar också arbetsexempel på närliggande lista i C, C ++, Java och Python.
En angränsningslista representerar ett diagram som en matris med länkade listor.
Matrisens index representerar ett toppunkt och varje element i dess länkade lista representerar de andra topparna som bildar en kant med toppunkten.
Närhet List representation
Nedan visas ett diagram och dess motsvarande angränsningslista.

En närliggande lista är effektiv när det gäller lagring eftersom vi bara behöver lagra värdena för kanterna. För ett sparsamt diagram med miljontals hörn och kanter kan det betyda mycket sparat utrymme.
Adjacency List Structure
Den enklaste angränsningslistan behöver en noddatastruktur för att lagra ett toppunkt och en grafdatastruktur för att organisera noderna.
Vi håller oss nära den grundläggande definitionen av en graf - en samling hörn och kanter (V, E)
. För enkelhetens skull använder vi en omärkt graf i motsats till en märkt, dvs. hörnen identifieras av deras index 0,1,2,3.
Låt oss gräva i datastrukturerna som spelas här.
struct node ( int vertex; struct node* next; ); struct Graph ( int numVertices; struct node** adjLists; );
Låt inte struct node** adjLists
överväldiga dig.
Allt vi säger är att vi vill lagra en pekare till struct node*
. Detta beror på att vi inte vet hur många vertikaler grafen kommer att ha och så att vi inte kan skapa en uppsättning länkade listor vid tidpunkten för sammanställningen.
Adjacency List C ++
Det är samma struktur men med hjälp av den inbyggda listan STL-datastrukturer för C ++ gör vi strukturen lite renare. Vi kan också abstrakta detaljerna i implementeringen.
class Graph ( int numVertices; list *adjLists; public: Graph(int V); void addEdge(int src, int dest); );
Adjacency List Java
Vi använder Java Collections för att lagra Array of Linked Lists.
class Graph ( private int numVertices; private LinkedList adjLists(); )
Typen av LinkedList bestäms av vilken data du vill lagra i den. För ett märkt diagram kan du lagra en ordlista istället för ett heltal
Adjacency List Python
Det finns en anledning till att Python får så mycket kärlek. En enkel ordlista över hörn och dess kanter är en tillräcklig representation av ett diagram. Du kan göra toppunkten så komplex som du vill.
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 och C / C ++ exempel
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); )