O co pytają na rozmowie kwalifikacyjnej: przegląd algorytmów, część 2

Artykuł ten jest kontynuacją mojej krótkiej recenzji na temat algorytmów. Oto link do pierwszej części . Wcześniej przyjrzeliśmy się różnym algorytmom sortowania tablic i tak zwanemu algorytmowi zachłannemu . Dzisiaj porozmawiamy o grafach i algorytmach z nimi związanych. Wykres jest jedną z najbardziej elastycznych i wszechstronnych struktur w programowaniu. Wykres G jest zwykle określany za pomocą pary zbiorów G = (V, R) , gdzie:

• V jest zbiorem wierzchołków;
• R jest zbiorem linii łączących pary wierzchołków.

Typowe linie łączące nazywane są krawędziami : Linie ze strzałkami – łuki : Zwykle wykres jest reprezentowany za pomocą diagramu, na którym niektóre wierzchołki są połączone krawędziami (łukami). Wykresy połączone ze sobą łukami bezpośrednio wskazującymi kierunek nazywane są skierowanymi . Jeśli wykresy zostaną połączone krawędziami, czyli bez wskazania kierunku możliwego ruchu, stają się nieskierowane . Oznacza to, że poruszanie się po nich jest możliwe w obu kierunkach: zarówno od wierzchołka A do B, jak i od B do A. Graf spójny to graf, w którym co najmniej jedna droga prowadzi z każdego wierzchołka do dowolnego innego wierzchołka (jak w przykładzie powyżej ). Jeżeli tak nie jest, graf zostaje rozłączony . Krawędom (łukom) można także przypisać wagi – liczby reprezentujące fizyczną odległość pomiędzy dwoma wierzchołkami (lub względny czas przejścia pomiędzy dwoma wierzchołkami). Takie wykresy nazywane są ważonymi :

3. Algorytmy wyszukiwania ścieżki (głębokość, szerokość)

Jedną z podstawowych operacji wykonywanych na grafach jest wyznaczenie wszystkich wierzchołków osiągalnych z danego wierzchołka. Wyobraź sobie, że próbujesz ustalić, jak dostać się z jednego miasta do drugiego, uwzględniając możliwe przesiadki. Do niektórych miast można dojechać bezpośrednio, do innych trzeba objechać inne miasta. Istnieje wiele innych sytuacji, w których konieczne może być znalezienie wszystkich wierzchołków, do których można znaleźć ścieżkę z danego wierzchołka. Istnieją zatem dwa główne sposoby przechodzenia przez grafy: przechodzenie w głąb i przechodzenie wszerz , które rozważymy. Obie metody zapewnią iterację po wszystkich połączonych wierzchołkach. Aby dokładniej rozważyć algorytmy najpierw w głąb i wszerz , spójrz na następujący wykres:

Głębokość pierwszego przejścia

Jest to jedna z najpopularniejszych metod przechodzenia przez graf. Ta strategia przeszukiwania w głąb polega na zagłębieniu się w graf tak daleko , jak to możliwe, a po dotarciu do ślepego zaułka, powrocie do najbliższego wierzchołka, który ma sąsiadujące wierzchołki, które nie były wcześniej odwiedzone. Algorytm ten przechowuje informacje na stosie o tym, gdzie wrócić, gdy osiągnięty zostanie zakleszczenie. Zasady pierwszego przejścia na głębokość:

1. Odwiedź sąsiedni, nieodwiedzony wcześniej wierzchołek, zaznacz go i odłóż na stos.
2. Idź do tego wierzchołka.
3. Powtórz krok 1.
4. Jeśli nie da się wykonać kroku 1, wróć do poprzedniego wierzchołka i spróbuj powtórzyć zasadę 1. Jeśli nie jest to możliwe, wróć do wierzchołka przed nim i tak dalej, aż znajdziemy wierzchołek, z którego będziemy mogli kontynuować przechodzenie.
5. Kontynuuj, aż wszystkie wierzchołki znajdą się na stosie.

Przyjrzyjmy się, jak mógłby wyglądać kod tego algorytmu w Javie:

public class Graph {
  private final int MAX_VERTS = 10;
  private Vertex vertexArray[]; //массив вершин
  private int adjMat[][]; // матрица смежности
  private int nVerts; // текущее количество вершин
  private Stack<integer> stack;

  public Graph() { // инициализация внутрених полей
     vertexArray = new Vertex[MAX_VERTS];
     adjMat = new int[MAX_VERTS][MAX_VERTS];
     nVerts = 0;
     for (int j = 0; j < MAX_VERTS; j++) {
        for (int k = 0; k < MAX_VERTS; k++) {
           adjMat[j][k] = 0;
        }
     }
     stack = new Stack<>();
  }

  public void addVertex(char lab) {
     vertexArray[nVerts++] = new Vertex(lab);
  }

  public void addEdge(int start, int end) {
     adjMat[start][end] = 1;
     adjMat[end][start] = 1;
  }

  public void displayVertex(int v) {
     System.out.println(vertexArray[v].getLabel());
  }

  public void dfs() { // обход в глубину
     vertexArray[0].setWasVisited(true); // берётся первая вершина
     displayVertex(0);
     stack.push(0);

     while (!stack.empty()) {
        int v = getAdjUnvisitedVertex(stack.peek()); // вынуть индекс смежной веришины, еckи есть 1, нету -1
        if (v == -1) { // если непройденных смежных вершин нету
           stack.pop(); // элемент извлекается из стека
        }
        else {
           vertexArray[v].setWasVisited(true);
           displayVertex(v);
           stack.push(v); // элемент попадает на вершину стека
        }
     }

     for (int j = 0; j < nVerts; j++) {  // сброс флагов
        vertexArray[j].wasVisited = false;
     }

  }

  private int getAdjUnvisitedVertex(int v) {
     for (int j = 0; j < nVerts; j++) {
        if (adjMat[v][j] == 1 && vertexArray[j].wasVisited == false) {
           return j; //возвращает первую найденную вершину
        }
     }
     return -1;
  }
}
</integer>

Góra wygląda tak:

public class Vertex {
  private char label;  // метка А например
  public boolean wasVisited;

  public Vertex(final char label) {
     this.label = label;
     wasVisited = false;
  }

  public char getLabel() {
     return this.label;
  }

  public boolean isWasVisited() {
     return this.wasVisited;
  }

  public void setWasVisited(final boolean wasVisited) {
     this.wasVisited = wasVisited;
  }
}

Uruchommy ten algorytm z określonymi wierzchołkami i sprawdźmy, czy działa poprawnie:

public class Solution {
  public static void main(String[] args) {
     Graph graph = new Graph();
     graph.addVertex('A'); //0
     graph.addVertex('B'); //1
     graph.addVertex('C'); //2
     graph.addVertex('D'); //3
     graph.addVertex('E'); //4
     graph.addVertex('F'); //5
     graph.addVertex('G'); //6

     graph.addEdge(0,1);
     graph.addEdge(0,2);
     graph.addEdge(0,3);
     graph.addEdge(1,4);
     graph.addEdge(3,5);
     graph.addEdge(5,6);

     System.out.println("Visits: ");
     graph.dfs();
  }
}

Wyjście konsoli: Ponieważ mamy macierz sąsiedztwa, a w metodzie spaceru używamy pętli zagnieżdżonej w pętli, złożoność czasowa będzie wynosić O(N²) .

Idź na szerokość

Algorytm ten, podobnie jak przechodzenie w głąb, jest jedną z najprostszych i najbardziej podstawowych metod poruszania się po grafie. Jego istotą jest to, że mamy pewien bieżący wierzchołek, z którego umieszczamy wszystkie sąsiednie, nieprzechodzone wierzchołki w kolejce i wybieramy kolejny element (który jest przechowywany jako pierwszy w kolejce), aby był aktualny... Jeśli podzielimy ten algorytm na etapach możemy wyróżnić następujące zasady:

1. Odwiedź kolejny, nieodwiedzony wcześniej wierzchołek sąsiadujący z bieżącym wierzchołkiem, zaznacz go wcześniej i dodaj do kolejki.
2. Jeśli nie można spełnić reguły nr 1, usuń wierzchołek z kolejki i ustaw go jako wierzchołek bieżący.
3. Jeśli zasady nr 1 i nr 2 są niemożliwe, przechodzenie jest zakończone i wszystkie wierzchołki zostały przebyte (jeśli nasz graf jest spójny).

Klasa graph jest prawie identyczna z podobną klasą z algorytmu przeszukiwania w głąb, z wyjątkiem metody, która przetwarza algorytm i zastępuje wewnętrzny stos kolejką:

public class Graph {
  private final int MAX_VERTS = 10;
  private Vertex vertexList[]; //массив вершин
  private int adjMat[][]; // матрица смежности
  private int nVerts; // текущее количество вершин
  private Queue<integer> queue;

  public Graph() {
     vertexList = new Vertex[MAX_VERTS];
     adjMat = new int[MAX_VERTS][MAX_VERTS];
     nVerts = 0;
     for (int j = 0; j < MAX_VERTS; j++) {
        for (int k = 0; k < MAX_VERTS; k++) {  // заполнение матрицы смежности нулями
           adjMat[j][k] = 0;
        }
     }
     queue = new PriorityQueue<>();
  }

  public void addVertex(char lab) {
     vertexList[nVerts++] = new Vertex(lab);
  }

  public void addEdge(int start, int end) {
     adjMat[start][end] = 1;
     adjMat[end][start] = 1;
  }

  public void displayVertex(int v) {
     System.out.println(vertexList[v].getLabel());
  }

  public void bfc() { // обход в глубину
     vertexList[0].setWasVisited(true);
     displayVertex(0);
     queue.add(0);
     int v2;

     while (!queue.isEmpty()) {
        int v = queue.remove();

        while((v2 = getAdjUnvisitedVertex(v))!=-1) {// цикл будет работать, пока все смежные вершины не будут найденны, и не будут добавлены в очередь
           vertexList[v2].wasVisited =true;
           displayVertex(v2);
           queue.add(v2);
        }
     }

     for (int j = 0; j < nVerts; j++) {  // сброс флагов
        vertexList[j].wasVisited = false;
     }

  }

  private int getAdjUnvisitedVertex(int v) {
     for (int j = 0; j < nVerts; j++) {
        if (adjMat[v][j] == 1 && vertexList[j].wasVisited == false) {
           return j; //возвращает первую найденную вершину
        }
     }
     return -1;
  }
}
</integer>

Klasa Vertex jest identyczna z klasą z algorytmu przeszukiwania w głąb . Wprowadźmy ten algorytm w działanie:

public class Solution {
  public static void main(String[] args) {
     Graph graph = new Graph();
     graph.addVertex('A'); //0
     graph.addVertex('B'); //1
     graph.addVertex('C'); //2
     graph.addVertex('D'); //3
     graph.addVertex('E'); //4
     graph.addVertex('F'); //5
     graph.addVertex('G'); //6

     graph.addEdge(0,1);
     graph.addEdge(0,2);
     graph.addEdge(0,3);
     graph.addEdge(1,4);
     graph.addEdge(3,5);
     graph.addEdge(5,6);

     System.out.println("Visits: ");
     graph.bfc();
  }
}

Wyjście konsoli: Powtórzę: mamy macierz sąsiedztwa i używamy pętli zagnieżdżonej w pętli, więc O(N²) jest złożonością czasową powyższego algorytmu.

4. Algorytm Dijkstry

Jak wspomniano wcześniej, grafy mogą być skierowane lub nieskierowane . A jak pamiętacie, nadal można je ważyć . Ważone, skierowane wykresy często można znaleźć w prawdziwym życiu: na przykład mapa miast, gdzie miasta są wierzchołkami, ścieżki między nimi to drogi, drogi mogą mieć ruch jednokierunkowy - kierunek wykresu. Załóżmy, że zajmujesz się transportem ładunków i musisz wyznaczyć najkrótszą trasę pomiędzy dwoma odległymi miastami. Jak to zrobisz? Jednym z najczęstszych problemów związanych z grafami ważonymi jest problem wyboru najkrótszej ścieżki pomiędzy dwoma wierzchołkami. Aby rozwiązać ten problem, używamy algorytmu Dijkstry . Od razu zaznaczę, że wykonując algorytm Dijkstry, znajdziemy najkrótszą ścieżkę do wszystkich wierzchołków z danego początkowego. Z jakich etapów składa się ten algorytm? Spróbuję odpowiedzieć na to pytanie. Etapy algorytmu Dijkstry:

• Etap 1 : wyszukaj węzeł, do którego przejście będzie najtańsze. Stoisz na samym początku i zastanawiasz się, dokąd pójść: do węzła A czy do węzła B. Ile czasu zajmie dotarcie do każdego z tych węzłów?
• Etap 2 : obliczenie, ile czasu potrzeba, aby dotrzeć do wszystkich sąsiadów B , na których algorytm nie miał jeszcze wpływu podczas poruszania się wzdłuż krawędzi od B. Jeśli ten nowy czas okaże się krótszy od starego, droga przez krawędź B stanie się nową najkrótszą ścieżką dla tego wierzchołka.
• Etap 3 : zaznacz wierzchołek B jako zaliczony.
• Krok 4 : Przejdź do kroku 1.

Cykl tych etapów będziemy powtarzać, aż wszystkie szczyty zostaną przekroczone. Rozważmy następujący graf ważony skierowany: Zatem korzystając z powyższego algorytmu wyznaczymy najkrótszą ścieżkę od A do G:

1. Dla wierzchołka A możliwe są trzy ścieżki: do B o wadze 3, do C o wadze 5 i do D o wadze 7. Zgodnie z pierwszym punktem algorytmu wybieramy węzeł z najniższym przejściem koszt – czyli dla B.
2. Ponieważ jedynym nieprzekraczanym sąsiednim wierzchołkiem B jest wierzchołek E , sprawdzamy, jaka będzie ścieżka przechodząca przez ten wierzchołek. 3( AB ) + 6 ( BE ) = 9.

   Zatem zauważamy, że obecna najkrótsza ścieżka do AE = 9.

3. Ponieważ nasza praca z wierzchołkiem B jest już zakończona, przechodzimy do wybierania kolejnego wierzchołka z minimalną wagą krawędzi znajdującej się przed nim.

   Z wierzchołków A i B mogą to być wierzchołki D (7), C (5), E (6).

   C ma najmniejszą wagę krawędzi , więc przechodzimy do tego wierzchołka.

4. Następnie, tak jak poprzednio, przy przejściu przez C znajdujemy najkrótszą ścieżkę do sąsiednich wierzchołków:
   • AD = 5( AC ) + 3( CD ) = 8, ale ponieważ poprzednia najkrótsza ścieżka AC = 7, czyli krótsza niż ta do C , pozostawiamy najkrótszą ścieżkę AD = 7 bez zmian.
   • CE = 5( AC ) + 4( CE ) = 9, ta nowa najkrótsza ścieżka jest równa poprzedniej, więc ją również pozostawiamy bez zmian.
5. Z najbliższych dostępnych wierzchołków E i D wybieramy wierzchołek o najmniejszej wadze krawędzi, czyli D (3).
6. Znajdujemy najkrótszą drogę do sąsiada - F.

   AF = 7( AD ) + 3 ( DF ) = 10

7. Z najbliższych dostępnych wierzchołków E i F wybieramy wierzchołek o najmniejszej wadze krawędzi, czyli F (3).
8. Znajdujemy najkrótszą drogę do sąsiada - G.

   AG = 7( AD ) + 3( DF ) + 4( FG ) = 14

   Właściwie tutaj znaleźliśmy ścieżkę od A do G.

   Aby jednak mieć pewność , że będzie on najkrótszy, musimy wykonać nasze kroki także dla wierzchołka E.

9. Ponieważ wierzchołek G nie ma sąsiadujących wierzchołków, do których prowadziłaby skierowana ścieżka, pozostaje nam tylko wierzchołek E : wybieramy go.
10. Znajdujemy najkrótszą drogę do sąsiada - G.

    AG = 3( AB ) + 6( BE ) + 6( EG ) = 15, ta ścieżka jest dłuższa niż poprzednia najkrótsza AG(14), więc pozostawiamy tę ścieżkę bez zmian.

    Ponieważ z G nie ma wierzchołków wychodzących , nie ma sensu uruchamiać etapów dla danego wierzchołka. Dlatego pracę algorytmu można uznać za zakończoną.

Jak mówiłem wcześniej, oprócz znalezienia najkrótszej ścieżki dla AG , otrzymaliśmy najkrótsze ścieżki do wszystkich wierzchołków z wierzchołka A (AB, AC, AD, AE, AF) . Cóż, czas przyjrzeć się, jak można to zaimplementować w Javie. Najpierw spójrzmy na klasę wierzchołków:

public class Vertex {
   private char label;
   private boolean isInTree;

   public Vertex(char label) {
       this.label = label;
       this.isInTree = false;
   }

   public char getLabel() {
       return label;
   }

   public void setLabel(char label) {
       this.label = label;
   }

   public boolean isInTree() {
       return isInTree;
   }

   public void setInTree(boolean inTree) {
       isInTree = inTree;
   }
}

Klasa wierzchołków jest w rzeczywistości identyczna z klasą wierzchołków z wyszukiwania w głąb i wszerz. Aby wyświetlić najkrótsze ścieżki, potrzebujemy nowej klasy, która będzie zawierać potrzebne nam dane:

public class Path { // obiekt данного класса содержащий расстояние и предыдущие и пройденные вершины
   private int distance; // текущая дистанция от начальной вершины
   private List<integer> parentVertices; // текущий родитель вершины

   public Path(int distance) {
       this.distance = distance;
       this.parentVertices = new ArrayList<>();
   }

   public int getDistance() {
       return distance;
   }

   public void setDistance(int distance) {
       this.distance = distance;
   }

   public List<integer> getParentVertices() {
       return parentVertices;
   }

   public void setParentVertices(List<integer> parentVertices) {
       this.parentVertices = parentVertices;
   }
}
</integer></integer></integer>

W tej klasie możemy zobaczyć całkowitą odległość ścieżki oraz wierzchołki, które zostaną pokonane podczas przejazdu najkrótszą ścieżką. A teraz chciałbym się zastanowić, w której klasie faktycznie następuje najkrótsze przejście przez graf. Zatem klasa grafów:

public class Graph {
   private final int MAX_VERTS = 10;// максимальное количество вершин
   private final int INFINITY = 100000000; // это число у нас будет служить в качестве "бесконечности"
   private Vertex vertexList[]; // список вершин
   private int relationMatrix[][]; // матрица связей вершин
   private int countOfVertices; // текущее количество вершин
   private int countOfVertexInTree; // количество рассмотренных вершин в дереве
   private List<path> shortestPaths; // список данных кратчайших путей
   private int currentVertex; // текущая вершина
   private int startToCurrent; //расстояние до currentVertex

   public Graph() {
       vertexList = new Vertex[MAX_VERTS]; // матрица смежности
       relationMatrix = new int[MAX_VERTS][MAX_VERTS];
       countOfVertices = 0;
       countOfVertexInTree = 0;
       for (int i = 0; i < MAX_VERTS; i++) {// матрица смежности заполняется
           for (int k = 0; k < MAX_VERTS; k++) { // бесконечными расстояниями
               relationMatrix[i][k] = INFINITY; // задания значений по умолчанию
               shortestPaths = new ArrayList<>();// задается пустым
           }
       }
   }

   public void addVertex(char lab) {// задание новых вершин
       vertexList[countOfVertices++] = new Vertex(lab);
   }

   public void addEdge(int start, int end, int weight) {
       relationMatrix[start][end] = weight; // задание ребер между вершинами, с весом между ними
   }

   public void path() { // выбор кратчайшего пути
       //  задание данных для стартовой вершины
       int startTree = 0; // стартуем с вершины 0
       vertexList[startTree].setInTree(true); // включение в состав дерева первого element
       countOfVertexInTree = 1;

       // заполнение коротких путей для вершин смежных с стартовой
       for (int i = 0; i < countOfVertices; i++) {
           int tempDist = relationMatrix[startTree][i];
           Path path = new Path(tempDist);
           path.getParentVertices().add(0);// первым родительским элементом, будет всегда стартовая вершина
           shortestPaths.add(path);
       }
       // пока все вершины не окажутся в дереве
       while (countOfVertexInTree < countOfVertices) { // выполняем, пока количество вершин в дереве не сравняется с общим количеством вершин
           int indexMin = getMin();//получаем индекс вершины с наименшей дистанцией, из вершин еще не входящих в дерево
           int minDist = shortestPaths.get(indexMin).getDistance();// минимальная дистанция вершины, из тек которые ещё не в дереве

           if (minDist == INFINITY) {
               System.out.println("В графе пристувствуют недостижимые вершины");
               break;// в случае если остались непройденными только недостижимые вершины, мы выходим из цикла
           } else {
               currentVertex = indexMin; // переводим указатель currentVert к текущей вершине
               startToCurrent = shortestPaths.get(indexMin).getDistance();// задаем дистанцию к текущей вершине
           }

           vertexList[currentVertex].setInTree(true);  //включение текущей вершины в дерево
           countOfVertexInTree++; // увеличиваем счетчик вершин в дереве
           updateShortestPaths(); // обновление списка кратчайших путей
       }

       displayPaths(); // выводим в консоль результаты
   }

   public void clean() { // очиска дерева
       countOfVertexInTree = 0;
       for (int i = 0; i < countOfVertices; i++) {
           vertexList[i].setInTree(false);
       }
   }

   private int getMin() {
       int minDist = INFINITY; // за точку старта взята "бесконечная" длина
       int indexMin = 0;
       for (int i = 1; i < countOfVertices; i++) {// для каждой вершины
           if (!vertexList[i].isInTree() && shortestPaths.get(i).getDistance() < minDist) { // если вершина ещё не ве дереве и её растояние меньше старого минимума
               minDist = shortestPaths.get(i).getDistance(); // задаётся новый минимум
               indexMin = i; // обновление индекса вершины содержащую минимаьную дистанцию
           }
       }
       return indexMin; //возвращает индекс вершины с наименшей дистанцией, из вершин еще не входящих в дерево
   }

   private void updateShortestPaths() {
       int vertexIndex = 1; // стартовая вершина пропускается
       while (vertexIndex < countOfVertices) { // перебор столбцов

           if (vertexList[vertexIndex].isInTree()) { // если вершина column уже включена в дерево, она пропускается
               vertexIndex++;
               continue;
           }
           // вычисление расстояния для одного element sPath
           // получение ребра от currentVert к column
           int currentToFringe = relationMatrix[currentVertex][vertexIndex];
           // суммирование всех расстояний
           int startToFringe = startToCurrent + currentToFringe;
           // определение расстояния текущего element vertexIndex
           int shortPathDistance = shortestPaths.get(vertexIndex).getDistance();

           // сравнение расстояния через currentVertex с текущим расстоянием в вершине с индексом vertexIndex
           if (startToFringe < shortPathDistance) {// если меньше, то у вершины под индексом vertexIndex будет задан новый кратчайший путь
               List<integer> newParents = new ArrayList<>(shortestPaths.get(currentVertex).getParentVertices());//создаём копию списка родителей вершины currentVert
               newParents.add(currentVertex);// задаём в него и currentVertex Jak предыдущий
               shortestPaths.get(vertexIndex).setParentVertices(newParents); // соохраняем новый маршут
               shortestPaths.get(vertexIndex).setDistance(startToFringe); // соохраняем новую дистанцию
           }
           vertexIndex++;
       }
   }

   private void displayPaths() { // метод для вывода кратчайших путей на экран
       for (int i = 0; i < countOfVertices; i++) {
           System.out.print(vertexList[i].getLabel() + " = ");
           if (shortestPaths.get(i).getDistance() == INFINITY) {
               System.out.println("0");
           } else {
               String result = shortestPaths.get(i).getDistance() + " (";
               List<integer> parents = shortestPaths.get(i).getParentVertices();
               for (int j = 0; j < parents.size(); j++) {
                   result += vertexList[parents.get(j)].getLabel() + " -> ";
               }
               System.out.println(result + vertexList[i].getLabel() + ")");
           }
       }
   }
}
</integer></integer></path>

Właściwie to cała magia =) Cóż, teraz przyjrzyjmy się temu algorytmowi w akcji:

public class Solution {

   public static void main(String[] args) {
       Graph graph = new Graph();
       graph.addVertex('A');
       graph.addVertex('B');
       graph.addVertex('C');
       graph.addVertex('D');
       graph.addVertex('E');
       graph.addVertex('F');
       graph.addVertex('G');

       graph.addEdge(0, 1, 3);
       graph.addEdge(0, 2, 5);
       graph.addEdge(0, 3, 7);
       graph.addEdge(1, 4, 6);
       graph.addEdge(2, 4, 4);
       graph.addEdge(2, 3, 3);
       graph.addEdge(3, 5, 3);
       graph.addEdge(4, 6, 6);
       graph.addEdge(5, 6, 4);

       System.out.println("Элементы имеют кратчайшие пути из точки A: ");
       graph.path();
       graph.clean();
   }
}

I wynik w konsoli: Złożoność czasowa tego algorytmu to nic innego jak O(N²), ponieważ mamy pętle zagnieżdżone w pętli. Cóż, to wszystko na dzisiaj, dziękuję za uwagę!