Ein effektiver Programmierer braucht ein solides Verständnis von Datenstrukturen und Algorithmen. Technische Interviews werden oft Ihre Fähigkeiten zur Problemlösung und zum kritischen Denken testen.

Graphen sind eine der vielen wichtigen Datenstrukturen in der Programmierung. In den meisten Fällen ist es nicht einfach, Graphen zu verstehen und graphenbasierte Probleme zu lösen.

Was ist ein Diagramm und was müssen Sie darüber wissen?

Was ist ein Diagramm?

Ein Graph ist eine nichtlineare Datenstruktur, die Knoten (oder Scheitelpunkte) mit Kanten hat, die sie verbinden. Alle Bäume sind Subtypen von Graphen, aber nicht alle Graphen sind Bäume, und der Graph ist die Datenstruktur, aus der Bäume entstanden sind.

Obwohl du kannst Erstellen Sie Datenstrukturen in JavaScript und anderen Sprachen können Sie einen Graphen auf verschiedene Weise implementieren. Die beliebtesten Ansätze sind Kantenlisten, Nachbarschaftslisten, und Adjazenzmatrizen.

Das Leitfaden der Khan Academy zur Darstellung von Graphen ist eine großartige Ressource, um zu lernen, wie man einen Graphen darstellt.

instagram viewer

Es gibt viele verschiedene Arten von Diagrammen. Eine gängige Unterscheidung ist zwischen gerichtet und ungerichtet Grafiken; Diese tauchen häufig bei Codierungsherausforderungen und realen Anwendungen auf.

Arten von Diagrammen

  1. Gerichteter Graph: Ein Graph, in dem alle Kanten eine Richtung haben, auch als bezeichnet Digraph.
  2. Ungerichteter Graph: Ein ungerichteter Graph wird auch als Zwei-Wege-Graph bezeichnet. In ungerichteten Graphen spielt die Richtung der Kanten keine Rolle, und die Traversierung kann in jede Richtung gehen.
  3. Gewichteter Graph: Ein gewichteter Graph ist ein Graph, dessen Knoten und Kanten einen zugeordneten Wert haben. In den meisten Fällen stellt dieser Wert die Kosten für die Untersuchung dieses Knotens oder dieser Kante dar.
  4. Endlicher Graph: Ein Graph, der eine endliche Anzahl von Knoten und Kanten hat.
  5. Unendlicher Graph: Ein Graph mit unendlich vielen Knoten und Kanten.
  6. Trivialer Graph: Ein Graph, der nur einen Knoten und keine Kante hat.
  7. Einfache Grafik: Wenn nur eine Kante jedes Knotenpaar eines Graphen verbindet, spricht man von einem einfachen Graphen.
  8. Nullgraph: Ein Nullgraph ist ein Graph, der keine Kanten hat, die seine Knoten verbinden.
  9. Multigraph: In einem Multigraphen hat mindestens ein Knotenpaar mehr als eine Kante, die sie verbindet. In Multigraphen gibt es keine Selbstschleifen.
  10. Vollständige Grafik: Ein vollständiger Graph ist ein Graph, in dem jeder Knoten mit jedem anderen Knoten im Graphen verbunden ist. Es ist auch als bekannt vollständige Grafik.
  11. Pseudograph: Ein Graph, der neben anderen Graphkanten eine Selbstschleife aufweist, wird als Pseudograph bezeichnet.
  12. Regelmäßige Grafik: Ein regulärer Graph ist ein Graph, bei dem alle Knoten den gleichen Grad haben; d.h. jeder Knoten hat gleich viele Nachbarn.
  13. Verbundener Graph: Ein verbundener Graph ist einfach jeder Graph, in dem zwei beliebige Knoten verbunden sind; dh ein Graph mit mindestens einem Pfad zwischen jeweils zwei Knoten des Graphen.
  14. Getrennter Graph: Ein getrennter Graph ist das direkte Gegenteil eines verbundenen Graphen. In einem nicht verbundenen Graphen gibt es keine Kanten, die die Knoten des Graphen verbinden, wie z. B. in a Null Graph.
  15. Zyklischer Graph: Ein zyklischer Graph ist ein Graph, der mindestens einen Graphzyklus enthält (ein Pfad, der dort endet, wo er begonnen hat).
  16. Azyklischer Graph: Ein azyklischer Graph ist ein Graph ohne Zyklen. Sie kann gerichtet oder ungerichtet sein.
  17. Teilgraph: Ein Untergraph ist ein abgeleiteter Graph. Es ist ein Graph, der aus Knoten und Kanten besteht, die Teilmengen eines anderen Graphen sind.

EIN Schleife in einem Graphen ist eine Kante, die an einem Knoten beginnt und am selben Knoten endet. Daher ein Selbstschleife ist eine Schleife über nur einen Graphknoten, wie in einem Pseudographen zu sehen.

Graph-Traversal-Algorithmen

Da es sich um eine Art nichtlineare Datenstruktur handelt, ist das Durchlaufen eines Diagramms ziemlich schwierig. Das Durchqueren eines Graphen bedeutet, jeden Knoten zu durchlaufen und zu untersuchen, vorausgesetzt, es gibt einen gültigen Pfad durch die Kanten. Es gibt hauptsächlich zwei Arten von Graph-Traversal-Algorithmen.

  1. Breitensuche (BFS): Die Breitensuche ist ein Graphtraversalalgorithmus, der einen Graphknoten besucht und seine Nachbarn untersucht, bevor er zu einem seiner untergeordneten Knoten weitergeht. Obwohl Sie mit dem Durchlaufen eines Diagramms von jedem ausgewählten Knoten aus beginnen können, ist die Wurzelknoten ist normalerweise der bevorzugte Ausgangspunkt.
  2. Tiefensuche (DFS): Dies ist der zweite große Algorithmus zum Traversieren von Graphen. Es besucht einen Graphknoten und untersucht seine untergeordneten Knoten oder Verzweigungen, bevor es zum nächsten Knoten übergeht – das heißt, es geht zuerst in die Tiefe, bevor es in die Breite geht.

Die Breitensuche ist der empfohlene Algorithmus, um möglichst schnell Wege zwischen zwei Knoten zu finden, insbesondere den kürzesten Weg.

Die Tiefensuche wird meistens empfohlen, wenn Sie jeden Knoten im Diagramm besuchen möchten. Beide Traversalalgorithmen funktionieren in jedem Fall gut, aber in ausgewählten Szenarien kann einer einfacher und optimierter sein als der andere.

Eine einfache Illustration kann helfen, beide Algorithmen besser zu verstehen. Stellen Sie sich die Staaten eines Landes als Graphen vor und versuchen Sie zu prüfen, ob zwei Staaten, X und Y, sind verbunden. Eine Tiefensuche könnte fast um das ganze Land herumgehen, ohne das früh genug zu erkennen Y ist nur 2 Staaten entfernt von X.

Der Vorteil einer Breitensuche besteht darin, dass die Nähe zum aktuellen Knoten so weit wie möglich beibehalten wird, bevor zum nächsten übergegangen wird. Es wird die Verbindung zwischen finden X und Y in kurzer Zeit, ohne das ganze Land erkunden zu müssen.

Ein weiterer wesentlicher Unterschied zwischen diesen beiden Algorithmen besteht in der Art und Weise, wie sie im Code implementiert werden. Die Breitensuche ist eine Iterativer Algorithmus und nutzt a Warteschlange, während eine Tiefensuche normalerweise als implementiert wird rekursiver Algorithmus das nutzt die Stapel.

Unten ist ein Pseudocode, der die Implementierung beider Algorithmen demonstriert.

Breitensuche

bfs (Graph G, GraphNode-Wurzel) {
Lassen q sein Neu Warteschlange
// Wurzel als besucht markieren
 root.besucht = Stimmt


// Root zur Warteschlange hinzufügen
q.einreihen(Wurzel)
während (q ist nicht leer) {
Lassen aktuell sein q.dequeue() // vorderes Element in der Warteschlange entfernen
 for (Nachbarn n des Stroms in G) {
wenn (n istnicht noch besucht) {
// zur Warteschlange hinzufügen - damit Sie auch seine Nachbarn erkunden können
q.einreihen(n)
 n.besucht = Stimmt
 }
 }
 }
}

Tiefensuche

dfs (Graph G, GraphNode-Wurzel) {
// Basisfall
wenn (Wurzel ist Null) Rückkehr
// Wurzel als besucht markieren
 root.besucht = Stimmt
for (Nachbarn n der Wurzel in G)
wenn (n istnicht noch besucht)
 dfs (G, n) // rekursiver Aufruf
}

Einige andere Graph-Traversal-Algorithmen leiten sich von Breiten- und Tiefensuchen ab. Die beliebtesten sind:

  • Bidirektionale Suche: Dieser Algorithmus ist ein optimierter Weg, um den kürzesten Weg zwischen zwei Knoten zu finden. Es verwendet zwei Breitensuchen, die kollidieren, wenn es einen Pfad gibt.
  • Topologische Sortierung: Dies wird in verwendet gerichtete Graphen um die Knoten in der gewünschten Reihenfolge zu sortieren. Sie können eine topologische Sortierung nicht auf ungerichtete Graphen oder Graphen mit Zyklen anwenden.
  • Dijkstra-Algorithmus: Dies ist auch eine Art von BFS. Es wird auch verwendet, um den kürzesten Weg zwischen zwei Knoten in a zu finden gewichteter gerichteter Graph, die Zyklen haben kann oder nicht.

Häufige Interviewfragen basierend auf Diagrammen

Graphen gehören zu den wichtigen Datenstrukturen, die jeder Programmierer kennen sollte. In Fachgesprächen tauchen oft Fragen zu diesem Thema auf, und Sie können auf einige klassische Probleme rund um das Thema stoßen. Dazu gehören Dinge wie die Probleme „Stadtrichter“, „Anzahl der Inseln“ und „Handelsvertreter“.

Dies sind nur einige der vielen beliebten grafikbasierten Interviewprobleme. Du kannst sie anprobieren LeetCode, HackerRank, oder GeeksfürGeeks.

Graphdatenstrukturen und Algorithmen verstehen

Diagramme sind nicht nur für technische Interviews nützlich. Sie haben auch reale Anwendungsfälle, wie z Netzwerke, Karten, und Airline-Systeme zum Finden von Routen. Sie werden auch in der zugrunde liegenden Logik von Computersystemen verwendet.

Diagramme eignen sich hervorragend zum Organisieren von Daten und zum Visualisieren komplexer Probleme. Diagramme sollten jedoch nur verwendet werden, wenn es absolut notwendig ist, um Speicherplatzprobleme oder Speicherprobleme zu vermeiden.