V tomto tutoriáli sa dozviete, čo je zoznam susedov. Nájdete tiež pracovné príklady zoznamu adjacency v jazykoch C, C ++, Java a Python.
Zoznam susedstiev predstavuje graf ako pole prepojených zoznamov.
Index poľa predstavuje vrchol a každý prvok v jeho prepojenom zozname predstavuje ďalšie vrcholy, ktoré tvoria hranu s vrcholom.
Reprezentácia zoznamu susedov
Ďalej je uvedený graf a jeho ekvivalentné zastúpenie.
Reprezentácia zoznamu susedov
Zoznam susedstiev je efektívny z hľadiska ukladania, pretože musíme ukladať iba hodnoty pre okraje. Pre riedky graf s miliónmi vrcholov a hrán to môže znamenať veľa ušetreného miesta.
Štruktúra zoznamu susedov
Najjednoduchší zoznam susedstiev vyžaduje dátovú štruktúru uzla na uloženie vrcholu a grafovú dátovú štruktúru na usporiadanie uzlov.
Zostávame blízko základnej definície grafu - zbierky vrcholov a hrán (V, E). Pre jednoduchosť používame neoznačený graf na rozdiel od označeného, tj. Vrcholy sú identifikované podľa ich indexov 0,1,2,3.
Poďme sa ponoriť do dátových štruktúr, ktoré tu hráme.
struct node ( int vertex; struct node* next; ); struct Graph ( int numVertices; struct node** adjLists; );
Nenechajte sa struct node** adjListspremôcť.
Všetko, čo hovoríme, je, že chceme uložiť ukazovateľ na struct node*. Je to tak preto, lebo nevieme, koľko vrcholov bude mať graf, a preto nemôžeme vytvoriť rad prepojených zoznamov v čase kompilácie.
Zoznam susedov C ++
Je to rovnaká štruktúra, ale použitím zabudovaného zoznamu dátových štruktúr STL v C ++ urobíme štruktúru trochu čistejšou. Sme tiež schopní abstraktizovať podrobnosti implementácie.
class Graph ( int numVertices; list *adjLists; public: Graph(int V); void addEdge(int src, int dest); );
Zoznam susedných počítačov Java
Na ukladanie poľa prepojených zoznamov používame zbierky Java.
class Graph ( private int numVertices; private LinkedList adjLists(); )
Typ LinkedList je určený tým, aké údaje do neho chcete uložiť. Pre označený graf môžete namiesto celého čísla uložiť slovník
Zoznam susedných krajín Python
Existuje dôvod, prečo Python získa toľko lásky. Jednoduchý slovník vrcholov a jeho okrajov je dostatočným znázornením grafu. Samotný vrchol môžete urobiť tak zložitým, ako 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')))
Príklady jazyka Python, Java a C / C ++
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); )
