Lo que preguntan en una entrevista: revisión de algoritmos, parte 2

Este artículo es una continuación de mi breve reseña sobre algoritmos. Aquí os dejo el enlace a la primera parte . Anteriormente, analizamos varios algoritmos de clasificación de matrices y el llamado algoritmo codicioso . Hoy hablaremos de gráficos y algoritmos relacionados con ellos. Un gráfico es una de las estructuras más flexibles y universales en programación. Un gráfico G generalmente se especifica usando un par de conjuntos G = (V, R) , donde:

• V es el conjunto de vértices;
• R es el conjunto de líneas que conectan pares de vértices.

Las líneas de conexión comunes se llaman aristas : Líneas con flechas - arcos : Normalmente, un gráfico se representa mediante un diagrama en el que algunos vértices están conectados por aristas (arcos). Los gráficos conectados entre sí por arcos que indican directamente la dirección se llaman dirigido . Si los gráficos están conectados por aristas, es decir, sin indicar la dirección del posible movimiento, se vuelven no dirigidos . Esto significa que el movimiento a lo largo de ellos es posible en ambas direcciones: tanto del vértice A a B como de B a A. Un gráfico conexo es un gráfico en el que al menos un camino conduce desde cada vértice a cualquier otro vértice (como en el ejemplo arriba ). Si este no es el caso, el gráfico se desconecta : Además, a los bordes (arcos) se les pueden asignar pesos: números que representan la distancia física entre dos vértices (o el tiempo relativo de transición entre dos vértices). Estos gráficos se denominan ponderados :

3. Algoritmos de búsqueda de rutas (profundidad, ancho)

Una de las operaciones básicas que se realiza en los gráficos es determinar todos los vértices a los que se puede llegar desde un vértice determinado. Imagina que estás intentando determinar cómo llegar de una ciudad a otra con posibles traslados. A algunas ciudades se puede llegar directamente, mientras que a otras es necesario desviarse por otras ciudades. Hay muchas otras situaciones en las que puede ser necesario encontrar todos los vértices a los que se puede encontrar un camino desde un vértice determinado. Entonces, hay dos formas principales de recorrer gráficos: recorrido primero en profundidad y recorrido primero en amplitud , que consideraremos. Ambos métodos garantizarán iteraciones sobre todos los vértices conectados. Para una consideración más detallada de los algoritmos primero en profundidad y primero en amplitud , tome el siguiente gráfico:

Primer recorrido en profundidad

Este es uno de los métodos de recorrido de gráficos más comunes. Esta estrategia de búsqueda en profundidad consiste en profundizar lo más posible en el gráfico y, al llegar a un callejón sin salida, regresar al vértice más cercano que tenga vértices adyacentes que no hayan sido visitados antes. Este algoritmo almacena información en la pila sobre dónde regresar cuando se alcanza un punto muerto. Reglas para el primer recorrido en profundidad:

1. Visite un vértice adyacente que no haya sido visitado anteriormente, márquelo y colóquelo en la pila.
2. Ve a este pico.
3. Repita el paso 1.
4. Si es imposible completar el paso 1, regrese al vértice anterior e intente repetir la regla 1. Si esto es imposible, regrese al vértice anterior, y así sucesivamente, hasta que encontremos un vértice desde el cual podamos continuar el recorrido.
5. Continúe hasta que todos los vértices estén en la pila.

Echemos un vistazo a cómo se vería el código de este algoritmo en 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>

El vértice se parece a:

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

Ejecutemos este algoritmo con vértices específicos y veamos si funciona correctamente:

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

Salida de consola: Como tenemos una matriz de adyacencia y en el método walk usamos un bucle anidado dentro de un bucle, la complejidad del tiempo será O(N²) .

caminar a lo ancho

Este algoritmo, al igual que el recorrido en profundidad, es uno de los métodos más simples y básicos para recorrer un gráfico. Su esencia es que tenemos un cierto vértice actual, desde el cual colocamos todos los vértices adyacentes no atravesados ​​en una cola y seleccionamos el siguiente elemento (que se almacena primero en la cola) para convertirlo en actual... Si dividimos este algoritmo en etapas, podemos destacar las siguientes reglas:

1. Visite el siguiente vértice adyacente al vértice actual, no visitado anteriormente, márquelo con anticipación y agréguelo a la cola.
2. Si no se puede cumplir la regla número 1, elimine el vértice de la cola y conviértalo en el vértice actual.
3. Si las reglas 1 y 2 son imposibles, el recorrido se completa y se han atravesado todos los vértices (si nuestro gráfico está conectado).

La clase de gráfico es casi idéntica a la clase similar del algoritmo de búsqueda en profundidad, con la excepción del método que procesa el algoritmo y reemplaza la pila interna con una cola:

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>

La clase Vertex es idéntica a la clase del algoritmo de búsqueda en profundidad . Pongamos este algoritmo en acción:

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

Salida de consola: Nuevamente: tenemos una matriz de adyacencia y usamos un bucle anidado dentro de un bucle, por lo que O(N²) es la complejidad temporal del algoritmo anterior.

4. Algoritmo de Dijkstra

Como se mencionó anteriormente, los gráficos pueden ser dirigidos o no dirigidos . Y como recordarás, todavía se pueden pesar . Los gráficos dirigidos y ponderados se encuentran a menudo en la vida real: por ejemplo, un mapa de ciudades, donde las ciudades son vértices, los caminos entre ellas son carreteras, las carreteras pueden tener tráfico en un solo sentido: la dirección del gráfico. Digamos que se dedica al transporte de carga y necesita crear la ruta más corta entre dos ciudades distantes. ¿Cómo harás ésto? Uno de los problemas más comunes que involucran gráficos ponderados es el problema de elegir el camino más corto entre dos vértices. Para resolver este problema utilizamos el algoritmo de Dijkstra . Me gustaría señalar de inmediato que al ejecutar el algoritmo de Dijkstra encontraremos los caminos más cortos a todos los vértices desde el inicial dado. ¿Qué etapas tiene este algoritmo? Intentaré responder a esta pregunta. Etapas del algoritmo de Dijkstra:

• Etapa 1 : busque el nodo cuya transición supondrá el menor coste. Estás parado desde el principio y te preguntas adónde ir: al nodo A o al nodo B. ¿Cuánto tiempo llevará llegar a cada uno de estos nodos?
• Etapa 2 : calcular cuánto tiempo lleva llegar a todos los vecinos de B que aún no han sido afectados por el algoritmo cuando se mueve a lo largo de un borde desde B. Si este nuevo tiempo resulta ser menor que el anterior, el camino que pasa por el borde B se convertirá en el nuevo camino más corto para este vértice.
• Etapa 3 : marque el vértice B como aprobado.
• Paso 4 : Vaya al Paso 1.

Repetiremos el ciclo de estas etapas hasta haber superado todos los picos. Consideremos el siguiente gráfico dirigido ponderado: Entonces, usando el algoritmo anterior, determinaremos el camino más corto de A a G:

1. Para el vértice A hay tres caminos posibles: a B con un peso de 3, a C con un peso de 5 y a D con un peso de 7. Según el primer punto del algoritmo, seleccionamos el nodo con la transición más baja. costo, es decir, a B.
2. Dado que el único vértice vecino no atravesado para B es el vértice E , comprobamos cuál será el camino al pasar por este vértice. 3( AB ) + 6( SER ) = 9.

   Por tanto, observamos que el camino más corto actual hacia AE = 9.

3. Como nuestro trabajo con el vértice B ya está completo, pasamos a seleccionar el siguiente vértice con el peso mínimo del borde anterior.

   De los vértices A y B estos pueden ser los vértices D (7), C (5), E (6).

   C tiene el peso de borde más pequeño , por lo que pasamos a este vértice.

4. A continuación, como antes, encontramos el camino más corto a los vértices vecinos al pasar por C:
   • AD = 5( AC ) + 3( CD ) = 8, pero como el camino más corto anterior AC = 7, es decir, menor que este que pasa por C , dejamos el camino más corto AD = 7 sin cambios.
   • CE = 5( AC ) + 4( CE ) = 9, este nuevo camino más corto es igual al anterior por lo que también lo dejamos sin cambios.
5. De los vértices disponibles más cercanos, E y D , seleccionamos el vértice con el peso de borde más pequeño, es decir, D (3).
6. Descubrimos el camino más corto hacia su vecino , F.

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

7. De los vértices disponibles más cercanos E y F , seleccionamos el vértice con el menor peso de arista, es decir, F (3).
8. Descubrimos el camino más corto hacia su vecino , G.

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

   En realidad, aquí hemos encontrado el camino de A a G.

   Pero para asegurarnos de que sea el más corto, también debemos ejecutar nuestros pasos para el vértice E.

9. Como el vértice G no tiene vértices vecinos a los que conduciría un camino dirigido, sólo nos queda el vértice E : lo seleccionamos.
10. Descubrimos el camino más corto hacia el vecino : G.

    AG = 3( AB ) + 6( BE ) + 6( EG ) = 15, este camino es más largo que el anterior AG más corto (14), por lo que dejamos este camino sin cambios.

    Dado que no hay vértices que partan de G , no tiene sentido ejecutar etapas para un vértice determinado. Por tanto, el trabajo del algoritmo puede considerarse completo.

Como dije antes, además de encontrar el camino más corto para AG , obtuvimos los caminos más cortos a todos los vértices desde el vértice A (AB, AC, AD, AE, AF) . Bueno, es hora de ver cómo se puede implementar esto en Java. Primero, veamos la clase de vértice:

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

La clase de vértice es en realidad idéntica a la clase de vértice de la búsqueda en profundidad y en amplitud. Para mostrar las rutas más cortas, necesitamos una nueva clase que contendrá los datos que necesitamos:

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

En esta clase podemos ver la distancia total del camino y los vértices que se recorrerán al pasar por el camino más corto. Y ahora me gustaría considerar la clase en la que, de hecho, se produce el recorrido más corto del gráfico. Entonces, la clase gráfica:

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); // включение в состав дерева первого elemento
       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;
           }
           // вычисление расстояния для одного elemento sPath
           // получение ребра от currentVert к column
           int currentToFringe = relationMatrix[currentVertex][vertexIndex];
           // суммирование всех расстояний
           int startToFringe = startToCurrent + currentToFringe;
           // определение расстояния текущего elemento 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 Cómo предыдущий
               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>

En realidad, esa es toda la magia =) Bueno, ahora, echemos un vistazo a este algoritmo en acción:

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

Y la salida en la consola: La complejidad temporal de este algoritmo no es más que O(N²) ya que tenemos bucles anidados dentro de un bucle. Bueno, eso es todo para mí hoy, ¡gracias por su atención!