Ce qu'ils demandent lors d'un entretien : revue des algorithmes, partie 2

Cet article est la suite de ma brève revue sur les algorithmes. Voici le lien vers la première partie . Auparavant, nous avons examiné divers algorithmes de tri de tableaux et ce que l'on appelle l' algorithme glouton . Aujourd'hui, nous parlerons des graphiques et des algorithmes qui leur sont associés. Un graphe est l’une des structures les plus flexibles et universelles de la programmation. Un graphe G est généralement spécifié à l'aide d'une paire d'ensembles G = (V, R) , où :

• V est l'ensemble des sommets ;
• R est l'ensemble des lignes reliant des paires de sommets.

Les lignes de connexion courantes sont appelées arêtes : Lignes avec flèches - arcs : Généralement, un graphique est représenté à l'aide d'un diagramme dans lequel certains sommets sont reliés par des arêtes (arcs). Les graphiques reliés entre eux par des arcs indiquant directement la direction sont appelés orientés . Si les graphiques sont reliés par des arêtes, c'est-à-dire sans indiquer la direction d'un mouvement possible, ils deviennent non orientés . Cela signifie que le mouvement le long d'eux est possible dans les deux sens : à la fois du sommet A à B et de B à A. Un graphe connexe est un graphe dans lequel au moins un chemin mène de chaque sommet à n'importe quel autre sommet (comme dans l'exemple au-dessus de ). Si ce n'est pas le cas, le graphe devient déconnecté : De plus, les arêtes (arcs) peuvent se voir attribuer des poids - des nombres représentant la distance physique entre deux sommets (ou le temps relatif de transition entre deux sommets). De tels graphiques sont appelés pondérés :

3. Algorithmes de recherche de chemin (profondeur, largeur)

L'une des opérations de base effectuées sur les graphiques consiste à déterminer tous les sommets accessibles à partir d'un sommet donné. Imaginez que vous essayez de déterminer comment vous rendre d'une ville à une autre avec des transferts possibles. Certaines villes sont accessibles directement, tandis que d'autres nécessitent un détour par d'autres villes. Il existe de nombreuses autres situations dans lesquelles vous devrez peut-être trouver tous les sommets vers lesquels vous pouvez trouver un chemin à partir d'un sommet donné. Il existe donc deux manières principales de parcourir des graphiques : le parcours en profondeur d'abord et le parcours en largeur d'abord , que nous considérerons. Les deux méthodes garantiront une itération sur tous les sommets connectés. Pour un examen plus approfondi des algorithmes de profondeur d'abord et de largeur d'abord , prenons le graphique suivant :

Première traversée en profondeur

Il s’agit de l’une des méthodes de parcours graphique les plus courantes. Cette stratégie de recherche en profondeur consiste à aller « en profondeur » dans le graphe aussi loin que possible, et lorsqu'on atteint une impasse, à revenir au sommet le plus proche qui a des sommets adjacents qui n'ont pas été visités auparavant. Cet algorithme stocke des informations sur la pile indiquant où revenir lorsqu'un blocage est atteint. Règles pour la première traversée en profondeur :

1. Visitez un sommet adjacent non visité auparavant, marquez-le et placez-le sur la pile.
2. Allez à ce sommet.
3. Répétez l'étape 1.
4. S'il est impossible de terminer l'étape 1, revenez au sommet précédent et essayez de répéter la règle 1. Si cela est impossible, revenez au sommet qui le précède, et ainsi de suite, jusqu'à ce que nous trouvions un sommet à partir duquel nous pouvons continuer le parcours.
5. Continuez jusqu'à ce que tous les sommets soient sur la pile.

Voyons à quoi pourrait ressembler le code de cet algorithme 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>

Le sommet ressemble à :

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

Exécutons cet algorithme avec des sommets spécifiques et voyons s'il fonctionne correctement :

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

Sortie de la console : Puisque nous avons une matrice de contiguïté et que dans la méthode walk nous utilisons une boucle imbriquée dans une boucle, la complexité temporelle sera O(N²) .

Marcher en largeur

Cet algorithme, comme le parcours en profondeur d'abord, est l'une des méthodes les plus simples et les plus basiques pour parcourir un graphique. Son essence est que nous avons un certain sommet actuel, à partir duquel nous mettons tous les sommets adjacents non traversés dans une file d'attente et sélectionnons l'élément suivant (qui est stocké en premier dans la file d'attente) pour le rendre actuel... Si nous divisons cet algorithme en étapes, nous pouvons souligner les règles suivantes :

1. Visitez le sommet suivant, non visité auparavant, adjacent au sommet actuel, marquez-le à l'avance et ajoutez-le à la file d'attente.
2. Si la règle n°1 ne peut pas être remplie, supprimez le sommet de la file d'attente et faites-en le sommet actuel.
3. Si les règles n°1 et n°2 sont impossibles, le parcours est terminé et tous les sommets ont été parcourus (si notre graphe est connecté).

La classe graph est presque identique à la classe similaire de l'algorithme de recherche en profondeur d'abord, à l'exception de la méthode qui traite l'algorithme et remplace la pile interne par une file d'attente :

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 classe Vertex est identique à la classe de l' algorithme de recherche en profondeur d'abord . Mettons cet algorithme en action :

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

Sortie de la console : Encore une fois : nous avons une matrice de contiguïté et utilisons une boucle imbriquée dans une boucle, donc O(N²) est la complexité temporelle de l'algorithme ci-dessus.

4. L'algorithme de Dijkstra

Comme mentionné précédemment, les graphiques peuvent être orientés ou non . Et comme vous vous en souvenez, ils peuvent toujours être pondérés . Des graphiques orientés et pondérés se trouvent souvent dans la vie réelle : par exemple, une carte de villes, où les villes sont des sommets, les chemins entre elles sont des routes, les routes peuvent avoir un trafic à sens unique - la direction du graphique. Disons que vous êtes engagé dans le transport de marchandises et que vous devez créer l'itinéraire le plus court entre deux villes distantes. Comment allez-vous faire cela ? L’un des problèmes les plus courants liés aux graphes pondérés est le problème du choix du chemin le plus court entre deux sommets. Pour résoudre ce problème, nous utilisons l'algorithme de Dijkstra . Je voudrais immédiatement noter qu'en exécutant l'algorithme de Dijkstra, nous découvrirons les chemins les plus courts vers tous les sommets à partir d'un sommet initial donné. Quelles sont les étapes de cet algorithme ? Je vais essayer de répondre à cette question. Étapes de l'algorithme de Dijkstra :

• Étape 1 : recherche du nœud dont la transition sera la moins coûteuse. Vous vous trouvez au tout début et vous vous demandez où aller : au nœud A ou au nœud B. Combien de temps faudra-t-il pour atteindre chacun de ces nœuds ?
• Étape 2 : calculer le temps nécessaire pour atteindre tous les voisins de B qui n'ont pas encore été affectés par l' algorithme lors du déplacement le long d'une arête depuis B. Si ce nouveau temps s’avère inférieur à l’ancien, le chemin passant par l’arête B deviendra le nouveau chemin le plus court pour ce sommet.
• Étape 3 : marquer le sommet B comme réussi.
• Étape 4 : Passez à l'étape 1.

Nous répéterons le cycle de ces étapes jusqu’à ce que tous les pics soient dépassés. Considérons le graphe orienté pondéré suivant : Ainsi, en utilisant l'algorithme ci-dessus, nous déterminerons le chemin le plus court de A à G :

1. Pour le sommet A il y a trois chemins possibles : vers B de poids 3, vers C de poids 5 et vers D de poids 7. Selon le premier point de l'algorithme, on sélectionne le nœud avec la transition la plus basse coût - c'est-à-dire pour B.
2. Puisque le seul sommet voisin non parcouru pour B est le sommet E , nous vérifions quel sera le chemin en passant par ce sommet. 3( AB ) + 6( BE ) = 9.

   Ainsi, nous notons que le chemin le plus court actuel vers AE = 9.

3. Puisque notre travail avec le sommet B est déjà terminé, nous passons à la sélection du prochain sommet avec le poids minimum de l’arête qui le précède.

   A partir des sommets A et B , ceux-ci peuvent être les sommets D (7), C (5), E (6).

   C a le plus petit poids d’arête , nous passons donc à ce sommet.

4. Ensuite, comme précédemment, nous trouvons le chemin le plus court vers les sommets voisins en passant par C :
   • AD = 5( AC ) + 3( CD ) = 8, mais comme le chemin le plus court précédent AC = 7, c'est-à-dire inférieur à celui-ci passant par C , nous laissons le chemin le plus court AD = 7 inchangé.
   • CE = 5( AC ) + 4( CE ) = 9, ce nouveau chemin le plus court est égal au précédent donc nous le laissons également inchangé.
5. Parmi les sommets disponibles les plus proches, E et D , nous sélectionnons le sommet avec le plus petit poids d'arête, c'est-à-dire D (3).
6. Nous découvrons le chemin le plus court vers son voisin - F.

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

7. Parmi les sommets disponibles les plus proches E et F , nous sélectionnons le sommet avec le plus petit poids d'arête, c'est-à-dire F (3).
8. Nous découvrons le chemin le plus court vers son voisin - G.

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

   En fait, nous avons ici trouvé le chemin de A à G.

   Mais pour nous assurer qu'il est le plus court, nous devons également exécuter nos étapes pour le sommet E.

9. Puisque le sommet G n'a pas de sommets voisins auxquels mènerait un chemin dirigé, il ne nous reste que le sommet E : nous le sélectionnons.
10. Nous découvrons le chemin le plus court vers le voisin - G.

    AG = 3( AB ) + 6( BE ) + 6( EG ) = 15, ce chemin est plus long que le précédent AG(14) le plus court, nous laissons donc ce chemin inchangé.

    Puisqu’il n’y a aucun sommet partant de G , cela n’a aucun sens d’exécuter des étapes pour un sommet donné. Par conséquent, le travail de l’algorithme peut être considéré comme terminé.

Comme je l'ai dit plus tôt, en plus de trouver le chemin le plus court pour AG , nous avons obtenu les chemins les plus courts vers tous les sommets à partir du sommet A (AB, AC, AD, AE, AF) . Eh bien, il est temps de voir comment cela peut être implémenté en Java. Tout d’abord, regardons la classe vertex :

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 classe de sommets est en fait identique à la classe de sommets de la recherche en profondeur et en largeur. Pour afficher les chemins les plus courts, nous avons besoin d'une nouvelle classe qui contiendra les données dont nous avons besoin :

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>

Dans cette classe, nous pouvons voir la distance totale du chemin et les sommets qui seront parcourus en passant par le chemin le plus court. Et maintenant, je voudrais considérer la classe dans laquelle, en fait, le parcours le plus court du graphe se produit. Donc, la classe graph :

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>

En fait, c'est toute la magie =) Eh bien, maintenant, jetons un coup d'œil à cet algorithme en action :

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

Et le résultat dans la console : La complexité temporelle de cet algorithme n'est rien de plus que O(N²) puisque nous avons des boucles imbriquées dans une boucle. Eh bien, c'est tout pour moi aujourd'hui, merci pour votre attention !