V tomto kurzu se dozvíte, co je to seznam sousedství. Pracovní příklady seznamu sousedství také najdete v jazycích C, C ++, Java a Python.
Seznam sousedství představuje graf jako řadu propojených seznamů.
Index pole představuje vrchol a každý prvek v jeho propojeném seznamu představuje další vrcholy, které tvoří hranu s vrcholem.
Reprezentace seznamu sousedů
Níže je uveden graf a jeho ekvivalentní reprezentace seznamu sousedů.
Reprezentace seznamu sousedů
Seznam sousedů je efektivní z hlediska úložiště, protože potřebujeme ukládat pouze hodnoty pro hrany. Pro řídký graf s miliony vrcholů a hran to může znamenat spoustu ušetřeného prostoru.
Struktura seznamu sousedů
Nejjednodušší seznam sousedství potřebuje datovou strukturu uzlu k uložení vrcholu a datovou strukturu grafu k uspořádání uzlů.
Zůstaneme blízko základní definice grafu - kolekce vrcholů a hran (V, E). Pro zjednodušení používáme neznačený graf na rozdíl od označeného, tj. Vrcholy jsou identifikovány podle jejich indexů 0,1,2,3.
Pojďme se podívat na datové struktury, které se zde hrají.
struct node ( int vertex; struct node* next; ); struct Graph ( int numVertices; struct node** adjLists; );
Nenechte se struct node** adjListspřemoci.
Jediné, co říkáme, je, že chceme uložit ukazatel struct node*. Je to proto, že nevíme, kolik vrcholů bude mít graf, a proto nemůžeme vytvořit řadu propojených seznamů v době kompilace.
Seznam sousedství C ++
Je to stejná struktura, ale pomocí zabudovaného seznamu datových struktur STL v C ++ uděláme strukturu trochu čistší. Jsme také schopni abstrahovat podrobnosti implementace.
class Graph ( int numVertices; list *adjLists; public: Graph(int V); void addEdge(int src, int dest); );
Seznam sousedství Java
K ukládání pole propojených seznamů používáme kolekce Java.
class Graph ( private int numVertices; private LinkedList adjLists(); )
Typ LinkedList je určen tím, jaká data do něj chcete uložit. U označeného grafu můžete místo Integer uložit slovník
Seznam sousedství Python
Existuje důvod, proč Python získává tolik lásky. Jednoduchý slovník vrcholů a jeho hran je dostatečnou reprezentací grafu. Samotný vrchol můžete udělat tak složitým, jak chcete.
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 a C / C ++ příklady
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); )
