工作面试中的问答：Java 中的算法，第 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[]; // Array of vertices
  private int adjMat[][]; // Adjacency matrix
  private int nVerts; // Current number of vertices
  private Stack stack;

  public Graph() { // Initialize internal fields
     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() { // Depth-first search
     vertexArray[0].setVisited(true); // Take the first vertex
     displayVertex(0);
     stack.push(0);

     while (!stack.empty()) {
        int v = getAdjUnvisitedVertex(stack.peek()); // Return the index of the adjacent vertex: if any, 1; if not, -1
        if (v == -1) { // If there is no unvisited adjacent vertex
           stack.pop(); // The element is removed from the stack
        }
        else {
           vertexArray[v].setVisited(true);
           displayVertex(v);
           stack.push(v); // The element goes on top of the stack
        }
     }

     for (int j = 0; j < nVerts; j++) {  // Reset the flags
        vertexArray[j].visited = false;
     }

  }

  private int getAdjUnvisitedVertex(int v) {
     for (int j = 0; j < nVerts; j++) {
        if (adjMat[v][j] == 1 && vertexArray[j].visited == false) {
           return j; // Returns the first vertex found
        }
     }
     return -1;
  }
}

顶点看起来像这样：

public class Vertex {
  private char label;  // for example, 'A'
  public boolean visited;

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

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

  public boolean isVisited() {
     return this.visited;
  }

  public void setVisited(final boolean visited) {
     this.visited = visited;
  }
}

让我们用特定的顶点运行这个算法，看看它是否正常工作：

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

控制台输出： 由于我们有一个邻接矩阵并且在循环中使用循环，因此时间复杂度将为 O(N²)。

广度优先搜索

与深度优先搜索一样，该算法是最简单、最基本的图遍历方法之一。要点是我们有一些当前的顶点。我们将所有未访问的相邻顶点放入队列中，并选择下一个元素（即存储在队列头部的顶点），该元素成为当前顶点……将该算法分为几个阶段，我们可以确定以下步骤：

1. 访问与当前顶点相邻的下一个先前未访问的顶点，将其标记为提前访问过，并将其添加到队列中。
2. 如果步骤#1 无法执行，则从队列中删除该顶点并使其成为当前顶点。
3. 如果步骤#1和#2无法执行，那么我们就完成了遍历——每个顶点都已被遍历（如果我们有一个连通图）。

这里的图类与我们用于深度优先搜索算法的图类几乎相同，除了搜索方法本身以及队列取代了内部堆栈这一事实：

public class Graph {
  private final int MAX_VERTS = 10;
  private Vertex vertexList[]; // Array of vertices
  private int adjMat[][]; // Adjacency matrix
  private int nVerts; // Current number of vertices
  private Queue 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++) {  // Fill the adjacency matrix with zeros
           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() { // Depth-first search
     vertexList[0].setVisited(true);
     displayVertex(0);
     queue.add(0);
     int v2;

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

        while((v2 = getAdjUnvisitedVertex(v))!=-1) {// The loop runs until every adjacent vertex is found and added to the queue
           vertexList[v2].visited = true;
           displayVertex(v2);
           queue.add(v2);
        }
     }

     for (int j = 0; j < nVerts; j++) {  // Reset the flags
        vertexList[j].visited = false;
     }

  }

  private int getAdjUnvisitedVertex(int v) {
     for (int j = 0; j < nVerts; j++) {
        if (adjMat[v][j] == 1 && vertexList[j].visited == false) {
           return j; // Returns the first vertext found
        }
     }
     return -1;
  }
}

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算法的步骤：

• 步骤 1：找到导航成本最低（边权重最低）的相邻节点。您站在最开始的位置，思考要去哪里：节点 A 或节点 B。移动到每个节点的成本是多少？
• 步骤2：计算从B开始遍历边时，到算法尚未访问过的所有节点B的邻居的距离。如果新距离小于旧距离，则通过边 B 的路径将成为该顶点的新最短路径。
• 步骤3：将顶点B标记为已访问。
• 步骤 4：转到步骤 1。

我们将循环重复这些步骤，直到访问完所有顶点。让我们考虑以下加权有向图：使用上述算法，我们将确定从 A 到 G 的最短路径：

1. 顶点 A 有 3 种可能的路径：到 B 的权重为 3、到 С 的权重为 5、到 D 的权重为 7。根据算法的第一步，我们选择成本最低的节点（边权重）。在这种情况下，B.

2. 由于 B 唯一未访问的邻居是顶点 Е，因此我们检查如果经过该顶点，路径将会是什么。3(AB) + 6(BE) = 9。

   因此，我们记录当前从 A 到 E 的最短路径是 9。

3. 由于我们对顶点 B 的处理已完成，因此我们继续选择边具有最小权重的下一个顶点。

   从顶点 A 和 B 开始，可能的顶点是 D (7)、C (5) 或 E (6)。

   С 的边权重最小，所以我们去这个顶点。

4. 接下来，和之前一样，我们找到经过 C 时到达相邻顶点的最短路径：

   • AD = 5 (AC) + 3 (CD) = 8，但由于之前的最短路径 (AC = 7) 小于经过 С 的这条最短路径，因此我们保持最短路径 (AC = 7) 不变。

   • CE = 5(AC) + 4(CE) = 9。这条新的最短路径与前一条相同，因此我们也保持不变。

5. 从最近的可访问顶点（E和D）中，选择边权最小的顶点，即D（3）。

6. 我们找到到其邻居 F 的最短路径。

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

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 { // A class that contains the distance and the previous and traversed vertices
   private int distance; // Current distance from the starting vertex
   private List parentVertices; // Current parent vertex

   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 getParentVertices() {
       return parentVertices;
   }

   public void setParentVertices(List parentVertices) {
       this.parentVertices = parentVertices;
   }
}

在这个类中，我们可以看到路径的总距离以及经过最短路径时将要遍历的顶点。现在让我们看看我们实际遍历图形的最短路径的类。所以这里我们有 Graph 类：

public class Graph {
   private final int MAX_VERTS = 10;// Maximum number of vertices
   private final int INFINITY = 100000000; // This number represents infinity
   private Vertex vertexList[]; // List of vertices
   private int relationMatrix[][]; // Matrix of edges between vertices
   private int numberOfVertices; // Current number of vertices
   private int numberOfVerticesInTree; // Number of visited vertices in the tree
   private List shortestPaths; // List of shortest paths
   private int currentVertex; // Current vertex
   private int startToCurrent; // Distance to currentVertex

   public Graph() {
       vertexList = new Vertex[MAX_VERTS]; // Adjacency matrix
       relationMatrix = new int[MAX_VERTS][MAX_VERTS];
       numberOfVertices = 0;
       numberOfVerticesInTree = 0;
       for (int i = 0; i < MAX_VERTS; i++) { // Fill the adjacency matrix
           for (int k = 0; k < MAX_VERTS; k++) { // with "infinity"
               relationMatrix[i][k] = INFINITY; // Assign default values
               shortestPaths = new ArrayList<>(); // Assign an empty list
           }
       }
   }

   public void addVertex(char lab) {// Assign new vertices
       vertexList[numberOfVertices++] = new Vertex(lab);
   }

   public void addEdge(int start, int end, int weight) {
       relationMatrix[start][end] = weight; // Set weighted edges between vertices
   }

   public void path() { // Choose the shortest path
       // Set the initial vertex data
       int startTree = 0; // Start from vertex 0
       vertexList[startTree].setInTree(true); // Include the first element in the tree
       numberOfVerticesInTree = 1;

       // Fill out the shortest paths for vertices adjacent to the initial vertex
       for (int i = 0; i < numberOfVertices; i++) {
           int tempDist = relationMatrix[startTree][i];
           Path path = new Path(tempDist);
           path.getParentVertices().add(0);// The starting vertex will always be a parent vertex
           shortestPaths.add(path);
       }
       // Until every vertex is in the tree
       while (numberOfVerticesInTree < numberOfVertices) { // Do this until the number of of vertices in the tree equals the total number of vertices
           int indexMin = getMin();// Get the index of the of the vertex with the smallest distance from the vertices not yet in the tree
           int minDist = shortestPaths.get(indexMin).getDistance(); // Minimum distance to the vertices not yet in the tree

           if (minDist == INFINITY) {
               System.out.println("The graph has an unreachable vertex");
               break; // If only unreachable vertices have not been visited, then we exit the loop
           } else {
               currentVertex = indexMin; // Set currentVert to the index of the current vertex
               startToCurrent = shortestPaths.get(indexMin).getDistance(); // Set the distance to the current vertex
           }

           vertexList[currentVertex].setInTree(true);  // Add the current vertex to the tree
           numberOfVerticesInTree++; // Increase the count of vertices in the tree
           updateShortestPaths(); // Update the list of shortest paths
       }

       displayPaths(); // Display the results on the console
   }

   public void clear() { // Clear the tree
       numberOfVerticesInTree = 0;
       for (int i = 0; i < numberOfVertices; i++) {
           vertexList[i].setInTree(false);
       }
   }

   private int getMin() {
       int minDist = INFINITY; // The distance of the initial shortest path is taken to be infinite
       int indexMin = 0;
       for (int i = 1; i < numberOfVertices; i++) { // For each vertex
           if (!vertexList[i].isInTree() && shortestPaths.get(i).getDistance() < minDist) { // If the vertex is not yet in the tree and the distance to the vertex is less than the current minimum
               minDist = shortestPaths.get(i).getDistance(); // then update the minimum
               indexMin = i; // Update the index of the vertex with the minimum distance
           }
       }
       return indexMin; // Returns the index of the vertex with the smallest distance among those not yet in the tree
   }

   private void updateShortestPaths() {
       int vertexIndex = 1; // The initial vertex is skipped
       while (vertexIndex < numberOfVertices) { // Run over the columns

           if (vertexList[vertexIndex].isInTree()) { // If the column vertex is already in the tree, then we skip it
               vertexIndex++;
               continue;
           }
           // Calculate the distance for one element sPath
           // Get the edge from currentVert to column
           int currentToFringe = relationMatrix[currentVertex][vertexIndex];
           // Add up all the distances
           int startToFringe = startToCurrent + currentToFringe;
           // Determine the distance to the current vertexIndex
           int shortPathDistance = shortestPaths.get(vertexIndex).getDistance();

           // Compare the distance through currentVertex with the current distance in the vertex with index vertexIndex
           if (startToFringe < shortPathDistance) { // If it is smaller, then the vertex at vertexIndex is assigned the new shortest path
               List newParents = new ArrayList<>(shortestPaths.get(currentVertex).getParentVertices()); // Create a copy of the list of vertices of vertex currentVert's parents
               newParents.add(currentVertex); // And add currentVertex to it as the previous vertex
               shortestPaths.get(vertexIndex).setParentVertices(newParents); // Save the new path
               shortestPaths.get(vertexIndex).setDistance(startToFringe); // Save the new distance
           }
           vertexIndex++;
       }
   }

   private void displayPaths() { // A method for displaying the shortest paths on the screen
       for (int i = 0; i < numberOfVertices; 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 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() + ")");
           }
       }
   }
}

这就是神奇之处 =) 现在，让我们看看这个算法的实际应用：

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("The following nodes form the shortest paths from node A:");
       graph.path();
       graph.clear();
   }
}

控制台输出是这样的： 该算法的时间复杂度正是 O(N²)，因为我们有嵌套循环。这就是我今天的全部内容。感谢您的关注！