O que perguntam em uma entrevista: revisão de algoritmos, parte 2

Este artigo é uma continuação da minha breve revisão sobre algoritmos. Aqui está o link para a primeira parte . Anteriormente, examinamos vários algoritmos de classificação de array e o chamado algoritmo ganancioso . Hoje falaremos sobre gráficos e algoritmos relacionados a eles. Um gráfico é uma das estruturas mais flexíveis e versáteis da programação. Um gráfico G é geralmente especificado usando um par de conjuntos G = (V, R) , onde:

• V é o conjunto de vértices;
• R é o conjunto de linhas que conectam pares de vértices.

As linhas de conexão comuns são chamadas de arestas : Linhas com setas - arcos : Normalmente, um gráfico é representado por meio de um diagrama no qual alguns vértices são conectados por arestas (arcos). Gráficos conectados entre si por arcos que indicam diretamente a direção são chamados de direcionados . Se os gráficos estiverem conectados por arestas, ou seja, sem indicar a direção do possível movimento, eles se tornam não direcionados . Isso significa que o movimento ao longo deles é possível em ambas as direções: tanto do vértice A para B quanto de B para A. Um grafo conectado é um grafo no qual pelo menos um caminho leva de cada vértice a qualquer outro vértice (como no exemplo acima ). Se este não for o caso, o gráfico fica desconectado : Além disso, as arestas (arcos) podem receber pesos - números que representam a distância física entre dois vértices (ou o tempo relativo de transição entre dois vértices). Esses gráficos são chamados de ponderados :

3. Algoritmos de busca de caminho (profundidade, largura)

Uma das operações básicas realizadas em grafos é determinar todos os vértices que podem ser alcançados a partir de um determinado vértice. Imagine que você está tentando determinar como ir de uma cidade a outra com possíveis transferências. Algumas cidades podem ser alcançadas diretamente, enquanto outras requerem um desvio por outras cidades. Existem muitas outras situações em que pode ser necessário encontrar todos os vértices para os quais um caminho pode ser encontrado a partir de um determinado vértice. Portanto, existem duas maneiras principais de percorrer gráficos: travessia em profundidade e travessia em largura , que consideraremos. Ambos os métodos garantirão a iteração em todos os vértices conectados. Para uma consideração mais aprofundada dos algoritmos de profundidade e largura , pegue o seguinte gráfico:

Primeira travessia em profundidade

Este é um dos métodos de travessia de gráfico mais comuns. Essa estratégia de busca em profundidade consiste em ir “a fundo” no grafo o máximo possível e, ao chegar a um beco sem saída, retornar ao vértice mais próximo que possui vértices adjacentes que não foram visitados antes. Este algoritmo armazena informações na pilha sobre para onde retornar quando um impasse é atingido. Regras para primeira travessia em profundidade:

1. Visite um vértice adjacente não visitado anteriormente, marque-o e coloque-o na pilha.
2. Vá para este vértice.
3. Repita o passo 1.
4. Se for impossível completar o passo 1, retorne ao vértice anterior e tente repetir a regra 1. Se isso for impossível, retorne ao vértice anterior, e assim por diante, até encontrarmos um vértice a partir do qual possamos continuar a travessia.
5. Continue até que todos os vértices estejam na pilha.

Vamos dar uma olhada em como seria o código desse algoritmo em 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>

O topo se parece com:

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

Vamos executar este algoritmo com vértices específicos e ver se funciona corretamente:

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

Saída do console: Como temos uma matriz de adjacência e no método walk usamos um loop aninhado dentro de um loop, a complexidade do tempo será O(N²) .

Ande em largura

Este algoritmo, como o percurso em profundidade, é um dos métodos mais simples e básicos para percorrer um gráfico. Sua essência é que temos um certo vértice atual, a partir do qual colocamos todos os vértices adjacentes não percorridos em uma fila e selecionamos o próximo elemento (que é armazenado primeiro na fila) para torná-lo atual... Se dividirmos este algoritmo em etapas, podemos destacar as seguintes regras:

1. Visite o próximo vértice não visitado anteriormente, adjacente ao vértice atual, marque-o com antecedência e adicione-o à fila.
2. Se a regra nº 1 não puder ser cumprida, remova o vértice da fila e torne-o o vértice atual.
3. Se as regras 1 e 2 forem impossíveis, a travessia será concluída e todos os vértices foram percorridos (se nosso gráfico estiver conectado).

A classe do gráfico é quase idêntica à classe semelhante do algoritmo de busca em profundidade, exceto pelo método que processa o algoritmo e substitui a pilha interna por uma fila:

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>

A classe Vertex é idêntica à classe do algoritmo de busca em profundidade . Vamos colocar esse algoritmo em ação:

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

Saída do console: Novamente: temos uma matriz de adjacência e usamos um loop aninhado dentro de um loop, então O(N²) é a complexidade de tempo do algoritmo acima.

4. Algoritmo de Dijkstra

Conforme mencionado anteriormente, os gráficos podem ser direcionados ou não direcionados . E como você se lembra, eles ainda podem ser ponderados . Gráficos direcionados e ponderados são frequentemente encontrados na vida real: por exemplo, um mapa de cidades, onde as cidades são vértices, os caminhos entre elas são estradas, as estradas podem ter tráfego de mão única - a direção do gráfico. Digamos que você esteja envolvido no transporte de cargas e precise criar a rota mais curta entre duas cidades distantes. Como você vai fazer isso? Um dos problemas mais comuns envolvendo grafos ponderados é o problema de escolher o caminho mais curto entre dois vértices. Para resolver este problema usamos o algoritmo de Dijkstra . Gostaria de observar imediatamente que, executando o algoritmo de Dijkstra, descobriremos os caminhos mais curtos para todos os vértices a partir de um determinado vértice inicial. Quais estágios esse algoritmo possui? Vou tentar responder a esta pergunta. Etapas do algoritmo de Dijkstra:

• Etapa 1 : busca pelo nó cuja transição será de menor custo. Você está bem no início e se pergunta para onde ir: para o nó A ou para o nó B. Quanto tempo levará para chegar a cada um desses nós?
• Etapa 2 : calcular quanto tempo leva para chegar a todos os vizinhos de B que ainda não foram afetados pelo algoritmo ao se mover ao longo de uma aresta de B. Se este novo tempo for menor que o antigo, o caminho através da aresta B se tornará o novo caminho mais curto para este vértice.
• Etapa 3 : marcar o vértice B como aprovado.
• Etapa 4 : Vá para a Etapa 1.

Repetiremos o ciclo dessas etapas até que todos os picos tenham sido ultrapassados. Vamos considerar o seguinte gráfico direcionado ponderado: Assim, usando o algoritmo acima, determinaremos o caminho mais curto de A a G:

1. Para o vértice A existem três caminhos possíveis: para B com peso 3, para C com peso 5 e para D com peso 7. De acordo com o primeiro ponto do algoritmo, selecionamos o nó com a transição mais baixa custo - isto é, para B.
2. Como o único vértice vizinho não percorrido para B é o vértice E , verificamos qual será o caminho ao passar por este vértice. 3( AB ) + 6( BE ) = 9.

   Assim, notamos que o caminho mais curto atual para AE = 9.

3. Como nosso trabalho com o vértice B já está concluído, passamos a selecionar o próximo vértice com o peso mínimo da aresta anterior.

   Dos vértices A e B estes podem ser os vértices D (7), C (5), E (6).

   C tem o menor peso de aresta , então passamos para esse vértice.

4. A seguir, como antes, descobrimos o caminho mais curto para vértices vizinhos ao passar por C:
   • AD = 5( AC ) + 3( CD ) = 8, mas como o caminho mais curto anterior AC = 7, ou seja, menor que este através de C , deixamos o caminho mais curto AD = 7 inalterado.
   • CE = 5( AC ) + 4( CE ) = 9, este novo caminho mais curto é igual ao anterior então o deixamos inalterado também.
5. Dos vértices disponíveis mais próximos, E e D , selecionamos o vértice com menor peso de aresta, ou seja, D (3).
6. Descobrimos o caminho mais curto para o seu vizinho - F.

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

7. A partir dos vértices disponíveis mais próximos E e F , selecionamos o vértice com menor peso de aresta, ou seja, F (3).
8. Descobrimos o caminho mais curto para o seu vizinho - G.

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

   Na verdade, aqui encontramos o caminho de A a G.

   Mas para ter certeza de que é o mais curto, devemos executar nossos passos também para o vértice E.

9. Como o vértice G não possui vértices vizinhos aos quais um caminho direcionado levaria, só nos resta o vértice E : nós o selecionamos.
10. Descobrimos o caminho mais curto para o vizinho - G.

    AG = 3( AB ) + 6( BE ) + 6( EG ) = 15, este caminho é mais longo que o anterior mais curto AG(14), então deixamos este caminho inalterado.

    Como não há vértices partindo de G , não faz sentido executar estágios para um determinado vértice. Portanto, o trabalho do algoritmo pode ser considerado completo.

Como eu disse anteriormente, além de encontrar o caminho mais curto para AG , obtivemos os caminhos mais curtos para todos os vértices do vértice A (AB, AC, AD, AE, AF) . Bem, é hora de ver como isso pode ser implementado em Java. Primeiro, vamos dar uma olhada na classe 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;
   }
}

A classe de vértice é na verdade idêntica à classe de vértice da pesquisa em profundidade e em largura. Para exibir os caminhos mais curtos, precisamos de uma nova classe que contenha os dados que precisamos:

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>

Nesta classe podemos ver a distância total do caminho e os vértices que serão percorridos ao passar pelo caminho mais curto. E agora gostaria de considerar a classe em que, de fato, ocorre o menor percurso do gráfico. Então, a classe do gráfico:

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>

Na verdade, essa é toda a mágica =) Bem, agora vamos dar uma olhada neste algoritmo em ação:

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

E a saída no console: A complexidade de tempo deste algoritmo nada mais é do que O(N²) , pois temos loops aninhados dentro de um loop. Bem, isso é tudo para mim hoje, obrigado pela atenção!