他們在面試中詢問的問題：演算法回顧，第 2 部分

本文是我對演算法的簡短評論的延續。這是第一部分的連結。 之前，我們了解了各種數組排序演算法和所謂的貪心演算法。今天我們來談談圖以及與之相關的演算法。圖是程式設計中最靈活、最通用的結構之一。 圖 G通常使用一對集合G = (V, R)來指定，其中：

• V是頂點集；
• R是連接頂點對的線的集合。

常見的連接線稱為邊：帶箭頭的線 -弧：通常，圖是使用其中一些頂點透過邊（弧）連接的圖來表示的。透過直接指示方向的弧線相互連接的圖稱為有向圖。如果圖是透過邊連接的，也就是沒有指示可能移動的方向，那麼它們就變成無向的。這意味著沿著它們的移動可以在兩個方向上進行：從頂點 A 到 B，以及從 B 到 A。 連通圖是其中至少一條路徑從每個頂點通往任何其他頂點的圖（如範例中所示）多於 ）。如果不是這種情況，圖就會斷開：此外，可以為邊（弧）分配權重 - 表示兩個頂點之間的物理距離（或兩個頂點之間過渡的相對時間）的數字。這樣的圖稱為加權圖：

3.路徑搜尋演算法（深度、寬度）

對圖執行的基本操作之一是確定從給定頂點可到達的所有頂點。想像一下，您正在嘗試確定如何透過可能的轉乘從一個城市前往另一個城市。有的城市可以直達，有的則需要繞道其他城市。在許多其他情況下，可能需要找到從給定頂點到可以找到路徑的所有頂點。所以，圖的遍歷主要有兩種方式：深度優先遍歷和廣度優先遍歷，我們將考慮這兩種方法。兩種方法都將確保迭代所有連接的頂點。為了進一步考慮深度優先和廣度優先演算法，請看下圖：

深度優先遍歷

這是最常見的圖遍歷方法之一。這種深度優先搜尋策略包括盡可能「深入」圖，當到達死胡同時，返回到具有先前未訪問過的相鄰頂點的最近頂點。該演算法在堆疊上儲存有關達到死鎖時返回位置的資訊。深度優先遍歷的規則：

1. 訪問一個相鄰的、以前未訪問過的頂點，對其進行標記並將其放入堆疊中。
2. 走向這個巔峰。
3. 重複步驟 1。
4. 如果不可能完成步驟1，則回到前一個頂點並嘗試重複規則1。如果不可能，則回到它之前的頂點，依此類推，直到找到可以繼續遍歷的頂點。
5. 繼續，直到所有頂點都在堆疊上。

讓我們來看看該演算法的 Java 程式碼：

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>

頂部看起來像：

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;
  }
}

讓我們用特定的頂點來運行這個演算法，看看它是否正常運作：

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();
  }
}

控制台輸出： 由於我們有一個鄰接矩陣，並且在 walk 方法中我們使用嵌套在循環中的循環，因此時間複雜度將為O(N²)。

步行寬度

此演算法與深度優先遍歷一樣，是遍歷圖的最簡單、最基本的方法之一。它的本質是，我們有一個特定的當前頂點，我們將所有相鄰的、未遍歷的頂點放入隊列中，並選擇下一個元素（隊列中第一個存儲的）使其成為當前...如果我們將這個演算法分解為階段，我們可以強調以下規則：

1. 訪問與當前頂點相鄰的下一個、之前未訪問過的頂點，提前標記它並將其添加到佇列中。
2. 如果無法滿足規則#1，則從佇列中刪除該頂點並將其設為目前頂點。
3. 如果規則 #1 和規則 #2 不可能，則遍歷完成並且所有頂點都已遍歷（如果我們的圖是連通的）。

此圖類與深度優先搜尋演算法中的類似類別幾乎相同，除了處理演算法並用佇列取代內部堆疊的方法：

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>

Vertex 類別與深度優先搜尋演算法中的類別相同。讓我們將這個演算法付諸實現：

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();
  }
}

控制台輸出： 再次強調：我們有一個鄰接矩陣並使用嵌套在循環中的循環，因此O(N²)是上述演算法的時間複雜度。

4.Dijkstra演算法

如前所述，圖可以是有向的，也可以是無向的。正如您所記得的，它們仍然可以被加權。加權有向圖在現實生活中經常出現：例如，一張城市地圖，其中城市是頂點，城市之間的路徑是道路，道路可以有單向交通——圖的方向。假設您從事貨物運輸，需要創建兩個遙遠城市之間的最短路線。你將如何做到這一點？涉及加權圖的最常見問題之一是選擇兩個頂點之間的最短路徑問題。為了解決這個問題我們使用Dijkstra演算法。我想立即指出，透過執行 Dijkstra 演算法，我們將找出從給定的初始頂點到所有頂點的最短路徑。這個演算法有哪幾個階段？我將嘗試回答這個問題。 Dijkstra 演算法的階段：

• 第 1 階段：搜尋節點，過渡到該節點的成本最小。您站在一開始，想知道要去哪裡：節點A還是節點B。到達每個節點需要多長時間？
• 第2階段：計算當沿著B的一邊移動時，到達B的所有尚未受演算法影響的鄰居需要多少時間。如果新的時間小於舊的時間，則通過邊 B 的路徑將成為該頂點的新的最短路徑。
• 第 3 階段：將頂點 B 標記為通過。
• 步驟 4：轉到步驟 1。

我們將重複這些階段的循環，直到所有的峰值都被通過。讓我們考慮以下加權有向圖：因此，使用上述演算法，我們將確定從 A 到 G 的最短路徑：

1. 對於頂點A，有 3 條可能的路徑：到B的權重為 3、到C的權重為 5、到D的權重為 7。根據演算法的第一點，我們選擇具有最低轉移的節點成本-B .
2. 由於B唯一未遍歷的相鄰頂點是頂點E，因此我們檢查穿過該頂點時的路徑是什麼。3( AB )+6( BE )=9。

   因此，我們注意到目前到 AE 的最短路徑 = 9。

3. 由於我們對頂點B 的處理已經完成，因此我們繼續選擇下一個頂點，其先前的邊權重最小。

   從頂點A和B可以得到頂點D (7)、C (5)、E (6)。

   C的邊權重最小，所以我們繼續移動到這個頂點。

4. 接下來，和之前一樣，我們找出經過 C 時到達相鄰頂點的最短路徑：
   • AD = 5( AC ) + 3( CD ) = 8，但由於先前的最短路徑AC = 7，即小於通過C的這條最短路徑，因此我們保持最短路徑AD = 7 不變。
   • CE = 5( AC ) + 4( CE ) = 9，這條新的最短路徑等於前一條，所以我們也維持不變。
5. 從最近的可用頂點E和D中，我們選擇邊權重最小的頂點，即D (3)。
6. 我們找出其鄰居F的 最短路徑。

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

7. 從最近可用的頂點E和F中，我們選擇邊權重最小的頂點，即F (3)。
8. 我們找出其鄰居 G的最短路徑。

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

   實際上，這裡我們已經找到了從A到G的路徑。

   但為了確保它是最短的，我們還必須對頂點E運行我們的步驟。

9. 由於頂點G沒有有向路徑所通往的相鄰頂點，因此我們只剩下頂點E：我們選擇它。
10. 我們找出到鄰居的最短路徑- G。

    AG = 3( AB ) + 6( BE ) + 6( EG ) = 15，這條路徑比之前最短的 AG(14) 更長，所以我們保持這條路徑不變。

    由於沒有從G引出的頂點，因此為給定頂點運行階段是沒有意義的。因此，演算法的工作可以認為已經完成。

正如我之前所說，除了找到AG的最短路徑之外，我們還獲得了從頂點A (AB, AC, AD, AE, AF)到所有頂點的最短路徑。好吧，是時候看看如何在 Java 中實現這一點了。首先，我們來看看頂點類別：

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;
   }
}

頂點類別實際上與深度優先和廣度優先搜尋中的頂點類別相同。為了顯示最短路徑，我們需要一個新類別來包含我們需要的資料：

public class Path { // an object данного класса содержащий расстояние и предыдущие и пройденные вершины
   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>

在這個類別中，我們可以看到路徑的總距離以及經過最短路徑時將要覆蓋的頂點。現在我想考慮實際上發生圖的最短遍歷的類別。所以，圖類：

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 How предыдущий
               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>

實際上，這就是所有的魔力 =) 好吧，現在讓我們來看看這個演算法的實際應用：

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();
   }
}

以及控制台中的輸出： 這個演算法的時間複雜度只不過是O(N²)，因為我們有嵌套在迴圈中的迴圈。好了，我今天的分享就到這裡了，謝謝大家的關注！