algorithm
Graph

Einführung

Bemerkungen

Topologische Sortierung

Eine topologische Anordnung oder eine topologische Sortierung ordnet die Scheitelpunkte in einem gerichteten azyklischen Graphen auf einer Linie, dh in einer Liste, so an, dass alle gerichteten Kanten von links nach rechts gehen. Eine solche Reihenfolge kann nicht bestehen, wenn das Diagramm einen gerichteten Zyklus enthält, da Sie auf einer Linie nicht direkt weitergehen können und trotzdem zu Ihrem Ausgangspunkt zurückkehren können.

Formell in einem Graphen G = (V, E) , dann wird eine lineare Anordnung von allen seinen Ecken derart ist, daß , wenn G einen Rand enthält (u, v) ∈ E vom Vertex u nach Knoten v dann u voran v in der Reihenfolge.

Es ist wichtig zu beachten, dass jede DAG über mindestens eine topologische Sortierung verfügt.

Es sind Algorithmen zum Aufbau einer topologischen Anordnung einer beliebigen DAG in linearer Zeit bekannt. Ein Beispiel ist:

1. Rufen Sie depth_first_search(G) auf, um die depth_first_search(G) vf für jeden Knoten v zu berechnen
2. Wenn jeder Scheitelpunkt fertig ist, fügen Sie ihn vor einer verknüpften Liste ein
3. die verknüpfte Liste der Scheitelpunkte, da sie jetzt sortiert ist.

Eine topologische Sortierung kann in ϴ(V + E) Zeit durchgeführt werden, da der Tiefensuchalgorithmus ϴ(V + E) Zeit benötigt und Ω(1) (konstante Zeit) zum Einfügen von |V| Scheitelpunkte in den Vordergrund einer verknüpften Liste.

Viele Anwendungen verwenden gerichtete azyklische Diagramme, um Vorrang unter Ereignissen anzuzeigen. Wir verwenden die topologische Sortierung, um eine Reihenfolge für die Verarbeitung jedes Scheitelpunkts vor seinen Nachfolgern zu erhalten.

Scheitelpunkte in einem Diagramm können auszuführende Aufgaben darstellen, und die Kanten können Einschränkungen darstellen, dass eine Aufgabe vor der anderen ausgeführt werden muss. Eine topologische Reihenfolge ist eine gültige Reihenfolge, um die in V beschriebenen Tasks auszuführen.

Problemfall und seine Lösung

Lassen Sie einen Knoten v eine Task(hours_to_complete: int) beschreiben Task(hours_to_complete: int) , dh Task(4) beschreibt eine Task , die 4 Stunden dauert, und eine Kante e beschreibt eine Cooldown(hours: int) so dass Cooldown(3) eine Dauer von Zeit zum Abkühlen nach einer abgeschlossenen Aufgabe.

Unser Graph heißt dag (da es sich um einen gerichteten azyklischen Graphen handelt) und 5 Knoten enthalten:

A <- dag.add_vertex(Task(4)); 
B <- dag.add_vertex(Task(5));
C <- dag.add_vertex(Task(3)); 
D <- dag.add_vertex(Task(2));
E <- dag.add_vertex(Task(7));

wo wir die Scheitelpunkte mit gerichteten Kanten verbinden, so dass der Graph azyklisch ist,

// A ---> C ----+
// |      |     |
// v      v     v
// B ---> D --> E
dag.add_edge(A, B, Cooldown(2));
dag.add_edge(A, C, Cooldown(2));
dag.add_edge(B, D, Cooldown(1));
dag.add_edge(C, D, Cooldown(1));
dag.add_edge(C, E, Cooldown(1));
dag.add_edge(D, E, Cooldown(3));

dann gibt es drei mögliche topologische Ordnungen zwischen A und E ,

1. A -> B -> D -> E
2. A -> C -> D -> E
3. A -> C -> E

Thorups Algorithmus

Der Thorup-Algorithmus für den kürzesten Weg der Einzelquelle für einen ungerichteten Graphen hat die Zeitkomplexität O (m), die niedriger ist als die von Dijkstra.

Grundideen sind die folgenden. (Entschuldigung, ich habe es noch nicht versucht, es zu implementieren, so dass ich ein paar Kleinigkeiten vermissen könnte. Und das Originalpapier ist Paywall, daher habe ich versucht, es aus anderen Quellen zu rekonstruieren, die darauf verweisen. Bitte entfernen Sie diesen Kommentar, wenn Sie dies bestätigen könnten.)

• Es gibt Möglichkeiten, den Spannbaum in O (m) zu finden (hier nicht beschrieben). Sie müssen den überspannenden Baum von der kürzesten bis zur längsten Kante "wachsen lassen", und es wäre ein Wald mit mehreren verbundenen Komponenten, bevor er vollständig gewachsen ist.
• Wählen Sie eine ganze Zahl b (b> = 2) und berücksichtigen Sie nur die übergreifenden Gesamtstrukturen mit der Längenbegrenzung b ^ k. Fügen Sie die Komponenten zusammen, die genau gleich sind, aber mit unterschiedlichen k, und nennen Sie das Minimum k die Stufe der Komponente. Dann logisch Komponenten zu einem Baum machen. u ist das übergeordnete Element von v, wenn u die kleinste von v getrennte Komponente ist, die vollständig v enthält. Die Wurzel ist das gesamte Diagramm, und die Blätter sind Einzelscheitelpunkte im ursprünglichen Diagramm (mit der Ebene der negativen Unendlichkeit). Der Baum hat immer noch nur O (n) Knoten.
• Behalten Sie den Abstand der einzelnen Komponenten zur Quelle bei (wie im Dijkstra-Algorithmus). Der Abstand einer Komponente mit mehr als einem Scheitelpunkt ist der Mindestabstand ihrer nicht erweiterten Kinder. Setzen Sie den Abstand des Quellscheitelpunkts auf 0 und aktualisieren Sie die Vorfahren entsprechend.
• Beachten Sie die Abstände in der Basis b. Wenn Sie zum ersten Mal einen Knoten in Ebene k besuchen, legen Sie die untergeordneten Elemente in Buckets ab, die von allen Knoten der Ebene k gemeinsam genutzt werden (wie bei der Bucket-Sortierung, wobei der Heap im Dijkstra-Algorithmus ersetzt wird), um die Ziffer k und eine höhere Entfernung. Berücksichtigen Sie bei jedem Besuch eines Knotens nur die ersten b-Buckets, besuchen Sie und entfernen Sie jeden von ihnen, aktualisieren Sie die Entfernung des aktuellen Knotens und verknüpfen Sie den aktuellen Knoten mit der neuen Entfernung erneut mit seinem eigenen übergeordneten Knoten, und warten Sie auf den nächsten Besuch Eimer
• Wenn ein Blatt besucht wird, ist die aktuelle Entfernung die Endentfernung des Scheitelpunkts. Erweitern Sie alle Kanten im ursprünglichen Diagramm und aktualisieren Sie die Abstände entsprechend.
• Besuchen Sie den Wurzelknoten (ganze Grafik) so oft, bis das Ziel erreicht ist.

Es basiert auf der Tatsache, dass es keine Kante mit einer Länge von weniger als l zwischen zwei verbundenen Komponenten des übergreifenden Waldes mit Längenbegrenzung l gibt. Ausgehend von der Entfernung x können Sie sich nur auf eine verbundene Komponente konzentrieren, bis Sie sie erreichen der Abstand x + l. Sie werden einige Scheitelpunkte besuchen, bevor alle Scheitelpunkte mit geringerer Entfernung besucht werden. Dies ist jedoch nicht von Belang, da bekannt ist, dass von diesen Scheitelpunkten aus kein kürzerer Pfad vorhanden ist. Andere Teile funktionieren wie die Bucket-Sort / MSD-Radix-Sortierung, und natürlich wird der O (m) -Stammbaum benötigt.

Erkennen eines Zyklus in einem gerichteten Graphen mithilfe von Depth First Traversal

Ein Zyklus in einem gerichteten Diagramm ist vorhanden, wenn während einer DFS eine Hinterkante erkannt wird. Eine hintere Kante ist eine Kante von einem Knoten zu sich selbst oder einem der Vorfahren in einer DFS-Struktur. Für ein getrenntes Diagramm erhalten Sie eine DFS-Gesamtstruktur. Sie müssen also alle Scheitelpunkte im Diagramm durchlaufen, um nicht zusammenhängende DFS-Bäume zu finden.

C ++ - Implementierung:

    #include <iostream>
     #include <list>
        
    using namespace std; 
    
    #define NUM_V   4

    bool helper(list<int> *graph, int u, bool* visited, bool* recStack)
    {
        visited[u]=true;
        recStack[u]=true;
        list<int>::iterator i;
        for(i = graph[u].begin();i!=graph[u].end();++i)
        {  
            if(recStack[*i]) //if vertice v is found in recursion stack of this DFS traversal
                return true;
            else if(*i==u) //if there's an edge from the vertex to itself
                return true;
            else if(!visited[*i])
            {   if(helper(graph, *i, visited, recStack))
                   return true;
            }
        }
        recStack[u]=false;
        return false;
    }
    /*
    /The wrapper function calls helper function on each vertices which have not been visited. Helper function returns true if it detects a back edge in the subgraph(tree) or false.
*/
    bool isCyclic(list<int> *graph, int V)
    {
      bool visited[V];  //array to track vertices already visited
      bool recStack[V]; //array to track vertices in recursion stack of the traversal.

      for(int i = 0;i<V;i++)
       visited[i]=false, recStack[i]=false;  //initialize all vertices as not visited and not recursed

      for(int u = 0; u < V; u++) //Iteratively checks if every vertices have been visited
      {   if(visited[u]==false)
          {  if(helper(graph, u, visited, recStack)) //checks if the DFS tree from the vertex contains a cycle
               return true;
          }
      }
       return false;
    }
    /*
    Driver function
    */
    int main()
    {
        list<int>* graph = new list<int>[NUM_V];
        graph[0].push_back(1);
        graph[0].push_back(2);
        graph[1].push_back(2);
        graph[2].push_back(0);
        graph[2].push_back(3);
        graph[3].push_back(3);
        bool res = isCyclic(graph, NUM_V);
        cout<<res<<endl;
    }

Ergebnis: Wie unten gezeigt, gibt es drei Hinterkanten in der Grafik. Eine zwischen Scheitelpunkt 0 und 2; zwischen Eckpunkt 0, 1 und 2; und Scheitelpunkt 3. Die zeitliche Komplexität der Suche ist O (V + E), wobei V die Anzahl der Scheitelpunkte und E die Anzahl der Kanten ist.

Einführung in die Graphentheorie

Die Graphentheorie ist das Studium von Graphen, bei denen es sich um mathematische Strukturen handelt, mit denen paarweise Beziehungen zwischen Objekten modelliert werden.

Wussten Sie, dass fast alle Probleme des Planeten Erde in Probleme von Straßen und Städten umgewandelt und gelöst werden können? Die Graphentheorie wurde vor vielen Jahren erfunden, noch vor der Erfindung des Computers. Leonhard Euler schrieb einen Artikel über die Sieben Brücken von Königsberg, der als erster Artikel der Graphentheorie gilt. Seitdem haben die Menschen erkannt, dass wir das Problem mit der City-Road problemlos lösen können, wenn wir ein Problem auf dieses Problem mit der City-Road anwenden können.

Graphentheorie hat viele Anwendungen. Eine der gebräuchlichsten Anwendungen ist das Finden der kürzesten Entfernung zwischen einer Stadt zur anderen. Wir alle wissen, dass diese Webseite viele Router vom Server erreichen musste, um Ihren PC zu erreichen. Graph Theory hilft dabei, die Router herauszufinden, die gekreuzt werden müssen. Während des Krieges muss die Straße bombardiert werden, um die Hauptstadt von anderen zu trennen. Auch dies kann mit Graph Theory herausgefunden werden.

Lernen wir zunächst einige grundlegende Definitionen der Graphentheorie.

Graph:

Sagen wir, wir haben 6 Städte. Wir markieren sie als 1, 2, 3, 4, 5, 6. Nun verbinden wir die Städte, die Straßen miteinander verbinden.

Dies ist eine einfache Grafik, in der einige Städte mit den Straßen angezeigt werden, die sie miteinander verbinden. In der Graphentheorie nennen wir jede dieser Städte Knoten oder Scheitelpunkt, und die Straßen werden als Edge bezeichnet. Graph ist einfach eine Verbindung dieser Knoten und Kanten.

Ein Knoten kann viele Dinge darstellen. In einigen Diagrammen stellen Knoten Städte dar, einige Flughäfen, einige repräsentieren ein Quadrat in einem Schachbrett. Edge repräsentiert die Beziehung zwischen den einzelnen Knoten. Diese Beziehung kann die Zeit sein, um von einem Flughafen zum anderen zu gelangen, die Bewegungen eines Ritters von einem Platz zu allen anderen Feldern usw.

Pfad des Ritters in einem Schachbrett

In einfachen Worten repräsentiert ein Knoten ein beliebiges Objekt, und Edge repräsentiert die Beziehung zwischen zwei Objekten.

Angrenzender Knoten:

Wenn ein Knoten A eine Kante mit dem Knoten B teilt, wird B als benachbart zu A betrachtet . Wenn zwei Knoten direkt miteinander verbunden sind, werden sie als benachbarte Knoten bezeichnet. Ein Knoten kann mehrere benachbarte Knoten haben.

Gerichteter und ungerichteter Graph:

In gerichteten Graphen haben die Kanten auf einer Seite Richtungszeichen, d. H. Andererseits haben die Kanten von ungerichteten Graphen auf beiden Seiten Richtungszeichen, dh sie sind bidirektional . Normalerweise werden ungerichtete Graphen auf beiden Seiten der Kanten ohne Zeichen dargestellt.

Nehmen wir an, es gibt eine Party. Die Leute in der Partei werden durch Knoten dargestellt und es gibt eine Kante zwischen zwei Leuten, wenn sie sich die Hand geben. Dann ist dieser Graph ungerichtet ist , weil jede Person A schütteln sich die Hände mit Person B , wenn und nur wenn B auch schüttelt Hände mit A. Im Gegensatz dazu , wenn die Kanten von einer Person A an einem anderen Person B zu A ‚s bewundern B entspricht, dann wird dieser Graph gerichtet, weil sie die Bewunderung nicht unbedingt hin und her bewegt. Der erste Graphentyp wird als ungerichteter Graph bezeichnet, und die Kanten werden als ungerichtete Kanten bezeichnet, während der letztere Typ als gerichteter Graph und die Kanten als gerichtete Kanten bezeichnet werden.

Gewichtete und ungewichtete Grafik:

Ein gewichteter Graph ist ein Graph, in dem jeder Kante eine Zahl (das Gewicht) zugewiesen wird. Solche Gewichte können beispielsweise Kosten, Längen oder Kapazitäten darstellen, abhängig von dem anstehenden Problem.

Ein ungewichtetes Diagramm ist einfach das Gegenteil. Wir gehen davon aus, dass das Gewicht aller Kanten gleich ist (vermutlich 1).

Pfad:

Ein Pfad stellt einen Weg dar, um von einem Knoten zu einem anderen zu gelangen. Es besteht aus einer Folge von Kanten. Zwischen zwei Knoten können mehrere Pfade vorhanden sein.

Im obigen Beispiel gibt es zwei Pfade von A nach D. A-> B, B-> C, C-> D ist ein Pfad. Die Kosten für diesen Pfad betragen 3 + 4 + 2 = 9 . Wieder gibt es einen anderen Pfad A-> D. Die Kosten für diesen Weg betragen 10 . Der Pfad, der den niedrigsten Preis kostet, wird als kürzester Pfad bezeichnet .

Grad:

Der Grad eines Scheitelpunkts ist die Anzahl der Kanten, die mit ihm verbunden sind. Wenn sich eine Kante an beiden Enden (eine Schleife) mit dem Scheitelpunkt verbindet, wird zweimal gezählt.

In gerichteten Graphen haben die Knoten zwei Arten von Graden:

• In-Grad: Die Anzahl der Kanten, die auf den Knoten zeigen.
• Out-Grad: Die Anzahl der Kanten, die vom Knoten auf andere Knoten zeigen.

Für ungerichtete Graphen werden sie einfach Grad genannt.

Einige Algorithmen zur Graphentheorie

• Bellman-Ford-Algorithmus
• Dijkstra-Algorithmus
• Ford-Fulkerson-Algorithmus
• Kruskal-Algorithmus
• Nächster Nachbaralgorithmus
• Prims Algorithmus
• Tiefensuche
• Breitensuche

Diagramme speichern (Adjazenzmatrix)

Um ein Diagramm zu speichern, gibt es zwei Methoden:

• Angrenzungsmatrix
• Angrenzungsliste

Eine Adjazenzmatrix ist eine quadratische Matrix, die zur Darstellung eines endlichen Graphen dient. Die Elemente der Matrix geben an, ob Scheitelpunkte im Diagramm benachbart sind oder nicht.

Angrenzend bedeutet "neben oder neben etwas anderem" oder neben etwas zu sein. Zum Beispiel sind Ihre Nachbarn neben Ihnen. Wenn wir in der Graphentheorie vom Knoten A zum Knoten B gehen können, können wir sagen, dass der Knoten B dem Knoten A benachbart ist. Jetzt erfahren Sie, wie Sie über Adjacency Matrix speichern, welche Knoten an welche angrenzend sind. Das heißt, wir stellen dar, welche Knoten einen gemeinsamen Rand haben. Hier bedeutet Matrix 2D-Array.

Hier sehen Sie eine Tabelle neben der Grafik, dies ist unsere Adjazenzmatrix. Hier steht Matrix [i] [j] = 1 für eine Kante zwischen i und j . Wenn es keine Kante gibt, setzen wir einfach Matrix [i] [j] = 0 .

Diese Kanten können gewichtet werden, so wie sie die Entfernung zwischen zwei Städten darstellen können. Dann setzen wir den Wert in Matrix [i] [j] anstelle von 1.

Der oben beschriebene Graph ist bidirektional oder ungerichtet , dh wenn wir vom Knoten 2 zum Knoten 1 gehen können, können wir auch vom Knoten 1 zum Knoten 2 gehen. Wenn der Graph gerichtet war, dann würde es Pfeil Zeichen auf einer Seite des Diagramms gewesen ist. Selbst dann könnten wir es mit der Adjazenzmatrix darstellen.

Wir stellen die Knoten dar, die keinen Rand durch unendlich teilen. Zu beachten ist, dass die Matrix symmetrisch wird, wenn der Graph ungerichtet ist.

Der Pseudo-Code zum Erstellen der Matrix:

Procedure AdjacencyMatrix(N):    //N represents the number of nodes
Matrix[N][N]
for i from 1 to N
    for j from 1 to N
        Take input -> Matrix[i][j]
    endfor
endfor

Wir können die Matrix auch folgendermaßen füllen:

Procedure AdjacencyMatrix(N, E):    // N -> number of nodes
Matrix[N][E]                        // E -> number of edges
for i from 1 to E
    input -> n1, n2, cost
    Matrix[n1][n2] = cost
    Matrix[n2][n1] = cost
endfor

Bei gerichteten Graphen können Sie Matrix [n2] [n1] = Kostenzeile entfernen.

Die Nachteile der Adjacency-Matrix:

Das Gedächtnis ist ein großes Problem. Unabhängig davon, wie viele Kanten vorhanden sind, benötigen wir immer eine N * N-Matrix, wobei N die Anzahl der Knoten ist. Wenn es 10000 Knoten gibt, beträgt die Matrixgröße 4 * 10000 * 10000 bei 381 Megabyte. Dies ist eine große Verschwendung von Speicher, wenn wir Diagramme betrachten, die einige Kanten haben.

Angenommen, wir möchten herausfinden, zu welchem ​​Knoten wir von einem Knoten u gehen können . Wir müssen die ganze Zeile von u überprüfen, was viel Zeit kostet.

Der einzige Vorteil ist, dass wir die Verbindung zwischen den UV- Knoten und deren Kosten mithilfe der Adjacency Matrix leicht finden können.

Java-Code, der mithilfe des obigen Pseudocodes implementiert wurde:

import java.util.Scanner;
 
public class Represent_Graph_Adjacency_Matrix 
{
    private final int vertices;
    private int[][] adjacency_matrix;
 
    public Represent_Graph_Adjacency_Matrix(int v) 
    {
        vertices = v;
        adjacency_matrix = new int[vertices + 1][vertices + 1];
    }
 
    public void makeEdge(int to, int from, int edge) 
    {
        try 
        {
            adjacency_matrix[to][from] = edge;
        }
        catch (ArrayIndexOutOfBoundsException index) 
        {
            System.out.println("The vertices does not exists");
        }
    }
 
    public int getEdge(int to, int from) 
    {
        try 
        {
            return adjacency_matrix[to][from];
        }
        catch (ArrayIndexOutOfBoundsException index) 
        {
            System.out.println("The vertices does not exists");
        }
        return -1;
    }
 
    public static void main(String args[]) 
    {
        int v, e, count = 1, to = 0, from = 0;
        Scanner sc = new Scanner(System.in);
        Represent_Graph_Adjacency_Matrix graph;
        try 
        {
            System.out.println("Enter the number of vertices: ");
            v = sc.nextInt();
            System.out.println("Enter the number of edges: ");
            e = sc.nextInt();
 
            graph = new Represent_Graph_Adjacency_Matrix(v);
 
            System.out.println("Enter the edges: <to> <from>");
            while (count <= e) 
            {
                to = sc.nextInt();
                from = sc.nextInt();
 
                graph.makeEdge(to, from, 1);
                count++;
            }
 
            System.out.println("The adjacency matrix for the given graph is: ");
            System.out.print("  ");
            for (int i = 1; i <= v; i++)
                System.out.print(i + " ");
            System.out.println();
 
            for (int i = 1; i <= v; i++) 
            {
                System.out.print(i + " ");
                for (int j = 1; j <= v; j++) 
                    System.out.print(graph.getEdge(i, j) + " ");
                System.out.println();
            }
 
        }
        catch (Exception E) 
        {
            System.out.println("Somthing went wrong");
        }
 
        sc.close();
    }
}

Ausführen des Codes: Speichern Sie die Datei und kompilieren Sie sie mit javac Represent_Graph_Adjacency_Matrix.java

Beispiel:

$ java Represent_Graph_Adjacency_Matrix
Enter the number of vertices:
4
Enter the number of edges:
6
Enter the edges: <to> <from>
1 1
3 4
2 3
1 4
2 4
1 2
The adjacency matrix for the given graph is:
  1 2 3 4
1 1 1 0 1
2 0 0 1 1
3 0 0 0 1
4 0 0 0 0

Speichern von Diagrammen (Angrenzungsliste)

Die Angrenzungsliste ist eine Sammlung ungeordneter Listen, die zur Darstellung eines endlichen Graphen verwendet werden. Jede Liste beschreibt die Menge der Nachbarn eines Scheitelpunkts in einem Diagramm. Das Speichern von Diagrammen erfordert weniger Speicherplatz.

Sehen wir uns ein Diagramm und seine Nachbarschaftsmatrix an:

Jetzt erstellen wir eine Liste mit diesen Werten.

Dies wird als Adjazenzliste bezeichnet. Es zeigt, welche Knoten mit welchen Knoten verbunden sind. Wir können diese Informationen mithilfe eines 2D-Arrays speichern. Aber kostet uns das gleiche Gedächtnis wie Adjacency Matrix. Stattdessen verwenden wir dynamisch zugewiesenen Speicher, um diesen zu speichern.

Viele Sprachen unterstützen Vector oder List, mit denen wir die Nachbarschaftsliste speichern können. Für diese müssen wir nicht die Größe der Liste angeben. Wir müssen nur die maximale Anzahl von Knoten angeben.

Der Pseudo-Code lautet:

Procedure Adjacency-List(maxN, E):       // maxN denotes the maximum number of nodes
edge[maxN] = Vector()                    // E denotes the number of edges
for i from 1 to E
    input -> x, y                        // Here x, y denotes there is an edge between x, y
    edge[x].push(y)
    edge[y].push(x)
end for
Return edge

Da es sich um einen ungerichteten Graphen handelt, gibt es eine Kante von x nach y , es gibt auch eine Kante von y nach x . Wenn es sich um eine gerichtete Grafik handelte, würden wir die zweite auslassen. Bei gewichteten Diagrammen müssen wir auch die Kosten speichern. Wir erstellen einen anderen Vektor oder eine Liste namens cost [] , um diese zu speichern. Der Pseudo-Code:

Procedure Adjacency-List(maxN, E):
edge[maxN] = Vector()
cost[maxN] = Vector()
for i from 1 to E
    input -> x, y, w
    edge[x].push(y)
    cost[x].push(w)
end for
Return edge, cost

Aus diesem können wir leicht die Gesamtzahl der mit jedem Knoten verbundenen Knoten und deren Anzahl ermitteln. Es dauert weniger Zeit als die Adjacency Matrix. Wenn wir jedoch herausfinden müssten, ob zwischen u und v eine Kante besteht, wäre es einfacher gewesen, wenn wir eine Adjazenzmatrix beibehalten würden.