Diagrammdatenstruktur ist eine Sammlung von Knoten verbunden über Kanten . Es wird verwendet, um Beziehungen zwischen verschiedenen Einheiten darzustellen. Graphalgorithmen sind Methoden zur Manipulation und Analyse von Diagrammen und zur Lösung verschiedener Probleme wie den kürzesten Weg finden oder Zyklen erkennen.

Java-Schlaf

Inhaltsverzeichnis

• Komponenten eines Diagramms
• Grundlegende Operationen an Diagrammen
• Anwendungen von Graph
• Grundlagen des Graphen
• BFS und DFS im Diagramm
• Zyklen im Diagramm
• Kürzester Pfad im Diagramm
• Minimaler Spanning Tree
• Topologische Sortierung
• Konnektivität im Diagramm
• Maximaler Durchfluss im Diagramm
• Einige müssen Aufgaben im Diagramm lösen
• Einige Quizze

Komponenten eines Diagramms:

• Eckpunkte: Eckpunkte sind die Grundeinheiten des Diagramms. Manchmal werden Scheitelpunkte auch als Scheitelpunkt oder Knoten bezeichnet. Jeder Knoten/Scheitelpunkt kann beschriftet oder unbeschriftet sein.
• Kanten: Kanten werden gezeichnet oder verwendet, um zwei Knoten des Diagramms zu verbinden. Es kann ein geordnetes Knotenpaar in einem gerichteten Graphen sein. Kanten können zwei beliebige Knoten auf beliebige Weise verbinden. Es gibt keine Regeln. Manchmal werden Kanten auch als Bögen bezeichnet. Jede Kante kann beschriftet/unbeschriftet sein.

Grundlegende Operationen an Diagrammen:

Nachfolgend sind die grundlegenden Operationen in der Grafik aufgeführt:

• Einfügen von Knoten/Kanten in das Diagramm – Fügen Sie einen Knoten in das Diagramm ein.
• Löschen von Knoten/Kanten im Diagramm – Löschen Sie einen Knoten aus dem Diagramm.
• Suchen in Diagrammen – Suchen Sie nach einer Entität im Diagramm.
• Durchlaufen von Diagrammen – Durchlaufen aller Knoten im Diagramm.

Anwendungen von Graph:

Im Folgenden sind die realen Anwendungen aufgeführt:

• Diagrammdatenstrukturen können verwendet werden, um die Interaktionen zwischen Spielern einer Mannschaft darzustellen, beispielsweise Pässe, Schüsse und Tacklings. Die Analyse dieser Interaktionen kann Einblicke in die Teamdynamik und Verbesserungspotenziale liefern.
• Wird häufig zur Darstellung sozialer Netzwerke verwendet, z. B. Netzwerke von Freunden in sozialen Medien.
• Mithilfe von Diagrammen kann die Topologie von Computernetzwerken dargestellt werden, beispielsweise die Verbindungen zwischen Routern und Switches.
• Mithilfe von Diagrammen werden die Verbindungen zwischen verschiedenen Orten in einem Verkehrsnetz, beispielsweise Straßen und Flughäfen, dargestellt.
• Diagramme werden in neuronalen Netzen verwendet, wobei Scheitelpunkte Neuronen und Kanten die Synapsen zwischen ihnen darstellen. Neuronale Netze werden verwendet, um zu verstehen, wie unser Gehirn funktioniert und wie sich Verbindungen ändern, wenn wir lernen. Das menschliche Gehirn hat etwa 10^11 Neuronen und fast 10^15 Synapsen.

Grundlagen der Grafik:

• Einführung in Grafiken
• Graph und seine Darstellungen
• Arten von Diagrammen mit Beispielen
• Grundlegende Eigenschaften eines Diagramms
• Anwendungen, Vor- und Nachteile von Graph
• Diagramm transponieren
• Unterschied zwischen Diagramm und Baum

BFS und DFS im Diagramm:

• Breitendurchlauf für einen Graphen
• Tiefendurchlauf für einen Graphen
• Anwendungen der Tiefensuche
• Anwendungen der Breiten-ersten-Traversierung
• Iterative Tiefensuche
• BFS für Disconnected Graph
• Transitiver Abschluss eines Graphen mit DFS
• Unterschied zwischen BFS und DFS

Zyklen im Diagramm:

• Zyklus in einem gerichteten Diagramm erkennen
• Zyklus in einem ungerichteten Diagramm erkennen
• Erkennen Sie den Zyklus in einem direkten Diagramm mithilfe von Farben
• Erkennen Sie einen negativen Zyklus in einem Diagramm | (Bellman Ford)
• Zyklen der Länge n in einem ungerichteten und zusammenhängenden Graphen
• Erkennen eines negativen Kreislaufs mit Floyd Warshall
• Klonen Sie einen gerichteten azyklischen Graphen
• Union nach Rang und Pfadkomprimierung im Union-Find-Algorithmus
• Kürzester Weg im Diagramm:
  • Dijkstras Algorithmus für den kürzesten Weg
  • Bellman-Ford-Algorithmus
  • Floyd Warshall-Algorithmus
  • Johnsons Algorithmus für kürzeste Wege aller Paare
  • Kürzester Pfad im gerichteten azyklischen Graphen
  • Dial-Algorithmus
  • Mehrstufiger Graph (kürzester Weg)
  • Kürzester Pfad in einem ungewichteten Diagramm
  • Karps Algorithmus für den minimalen mittleren (oder durchschnittlichen) Gewichtszyklus
  • 0-1 BFS (kürzester Pfad in einem binären Gewichtsdiagramm)
  • Finden Sie den minimalen Gewichtszyklus in einem ungerichteten Diagramm

  Minimaler Spanning Tree:

  • Prims Minimum Spanning Tree (MST)
  • Kruskals Minimum Spanning Tree-Algorithmus
  • Unterschied zwischen Prims und Kruskals Algorithmus für MST
  • Anwendungen des Minimum Spanning Tree Problems
  • Minimale Kosten für die Verbindung aller Städte
  • Gesamtzahl der Spanning Trees in einem Diagramm
  • Minimaler Produktspannbaum
  • Reverse-Delete-Algorithmus für Minimum Spanning Tree
  • Boruvkas Algorithmus für Minimum Spanning Tree

  Topologische Sortierung:

  • Topologische Sortierung
  • Alle topologischen Arten eines gerichteten azyklischen Graphen
  • Kahns Algorithmus zur topologischen Sortierung
  • Maximale Kanten, die der DAG hinzugefügt werden können, sodass sie DAG bleibt
  • Längster Pfad in einem gerichteten azyklischen Graphen
  • Topologische Sortierung eines Graphen anhand der Abfahrtszeit des Scheitelpunkts

  Konnektivität im Diagramm:

  • Artikulationspunkte (oder Schnittscheitelpunkte) in einem Diagramm
  • Zweifach verbundene Komponenten
  • Brücken in einem Diagramm
  • Eulerscher Pfad und Kreis
  • Fleurys Algorithmus zum Drucken des Eulerschen Pfads oder Kreises
  • Stark verbundene Komponenten
  • Zählen Sie alle möglichen Spaziergänge von einer Quelle zu einem Ziel mit genau k Kanten
  • Euler-Kreis in einem gerichteten Graphen
  • Länge der kürzesten Kette, um das Zielwort zu erreichen
  • Finden Sie heraus, ob ein Array von Zeichenfolgen verkettet werden kann, um einen Kreis zu bilden
  • Tarjans Algorithmus zum Finden stark verbundener Komponenten
  • Pfade zum Reisen zu jedem Knoten unter Verwendung jeder Kante (Sieben Brücken von Königsberg)
  • Dynamische Konnektivität | Satz 1 (inkrementell)

  Maximaler Durchfluss im Diagramm:

  • Einführung in das Max-Flow-Problem
  • Ford-Fulkerson-Algorithmus für das Maximum-Flow-Problem
  • Finden Sie die maximale Anzahl kantendisjunkter Pfade zwischen zwei Eckpunkten
  • Finden Sie den minimalen s-t-Schnitt in einem Strömungsnetzwerk
  • Maximale bipartite Übereinstimmung
  • Problem bei der Kanalzuweisung
  • Einführung in den Push-Relabel-Algorithmus
  • Kargers Algorithmus – Satz 1 – Einführung und Implementierung
  • Dinics Algorithmus für maximalen Durchfluss

  Einige müssen Aufgaben im Diagramm lösen:

  • Finden Sie die Länge der größten Region in der Booleschen Matrix
  • Zählen Sie die Anzahl der Bäume in einem Wald
  • Ein Peterson-Graph-Problem
  • Klonen Sie ein ungerichtetes Diagramm
  • Graphfärbung (Einführung und Anwendungen)
  • Implementierung des Travelling-Salesman-Problems (TSP).
  • Scheitelpunktabdeckungsproblem | Satz 1 (Einführung und Näherungsalgorithmus)
  • K-Zentren-Problem | Satz 1 (Gieriger Näherungsalgorithmus)
  • Erdos-Renyl-Modell (zur Generierung von Zufallsgraphen)
  • Chinesischer Postbote oder Routeninspektion | Set 1 (Einführung)
  • Hierholzers Algorithmus für gerichtete Graphen
  • Überprüfen Sie, ob ein gegebener Graph bipartit ist oder nicht
  • Schlangen- und Leiterproblem
  • Boggle (Alle möglichen Wörter in einer Zeichentafel finden)
  • Hopcroft Karp-Algorithmus für maximale Matching-Einführung
  • Mindestzeit, um alle Orangen zu verrotten
  • Konstruieren Sie einen Graphen aus gegebenen Graden aller Eckpunkte
  • Bestimmen Sie, ob in einem gerichteten Graphen eine universelle Senke vorhanden ist
  • Anzahl der Senkenknoten in einem Diagramm
  • Zwei-Cliquen-Problem (Überprüfen Sie, ob der Graph in zwei Cliquen geteilt werden kann)

  Einige Quizze:

  • Quizze zum Thema Graph Traversal
  • Quizze zum Thema „Kurzester Weg des Diagramms“.
  • Quizze zum Graph Minimum Spanning Tree
  • Quizfragen zu Grafiken

  Quicklinks:

  • Die 10 häufigsten Interviewfragen zu Depth First Search (DFS)
  • Einige interessante Fragen zum kürzesten Weg
  • Videos zu Grafiken

  Empfohlen:

  • Lernen Sie Datenstruktur und Algorithmen | DSA-Tutorial