他们在面试中询问的问题：算法回顾，第 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²)，因为我们有嵌套在循环中的循环。好了，我今天的分享就到这里了，谢谢大家的关注！