I denne vejledning lærer du, hvad en nærhedsliste er. Du finder også arbejdseksempler på nærhedsliste i C, C ++, Java og Python.
En nærhedsliste repræsenterer en graf som en matrix af sammenkædede lister.
Indekset for arrayet repræsenterer et toppunkt, og hvert element i dets sammenkædede liste repræsenterer de andre hjørner, der danner en kant med toppunktet.
Adjacency List repræsentation
En graf og den tilsvarende repræsentation af nærhedslisten vises nedenfor.
Adjacency List repræsentation
En nærhedsliste er effektiv med hensyn til opbevaring, fordi vi kun behøver at gemme værdierne for kanterne. For en sparsom graf med millioner af hjørner og kanter kan det betyde meget sparet plads.
Adjacency List Structure
Den enkleste tilknytningsliste har brug for en nodedatastruktur til at gemme et toppunkt og en grafdatastruktur for at organisere noderne.
Vi holder os tæt på den grundlæggende definition af en graf - en samling af hjørner og kanter (V, E). For enkelheds skyld bruger vi en umærket graf i modsætning til en mærket, dvs. hjørnerne identificeres ved deres indeks 0,1,2,3.
Lad os grave i de datastrukturer, der spilles her.
struct node ( int vertex; struct node* next; ); struct Graph ( int numVertices; struct node** adjLists; );
Lad ikke struct node** adjListsovervælde dig.
Alt, hvad vi siger, er, at vi vil gemme en markør til struct node*. Dette skyldes, at vi ikke ved, hvor mange hjørner grafen vil have, og derfor kan vi ikke oprette en matrix af sammenkædede lister på kompileringstidspunktet.
Adjacency List C ++
Det er den samme struktur, men ved at bruge den indbyggede liste STL-datastrukturer på C ++ gør vi strukturen lidt renere. Vi er også i stand til at abstrakte detaljerne i implementeringen.
class Graph ( int numVertices; list *adjLists; public: Graph(int V); void addEdge(int src, int dest); );
Adjacency List Java
Vi bruger Java Collections til at gemme Array of Linked Lists.
class Graph ( private int numVertices; private LinkedList adjLists(); )
Typen af LinkedList bestemmes af, hvilke data du vil gemme i den. For en mærket graf kan du gemme en ordbog i stedet for et heltal
Adjacency List Python
Der er en grund til, at Python får så meget kærlighed. En simpel ordbog over hjørner og dens kanter er en tilstrækkelig gengivelse af en graf. Du kan gøre selve 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); )
