Cosa chiedono durante un colloquio: revisione degli algoritmi, parte 2

Questo articolo è la continuazione della mia breve recensione sugli algoritmi. Ecco il link alla prima parte . In precedenza, abbiamo esaminato vari algoritmi di ordinamento degli array e il cosiddetto algoritmo greedy . Oggi parleremo dei grafici e degli algoritmi ad essi correlati. Un grafico è una delle strutture più flessibili e versatili nella programmazione. Un grafo G viene solitamente specificato utilizzando una coppia di insiemi G = (V, R) , dove:

• V è l'insieme dei vertici;
• R è l'insieme delle linee che collegano coppie di vertici.

Le linee di collegamento comuni sono chiamate spigoli : Linee con frecce - archi : Tipicamente, un grafico viene rappresentato utilizzando un diagramma in cui alcuni vertici sono collegati da spigoli (archi). I grafici collegati tra loro da archi che indicano direttamente la direzione si dicono diretti . Se i grafici sono collegati da spigoli, cioè senza indicare la direzione del possibile movimento, diventano non orientati . Ciò significa che il movimento lungo di essi è possibile in entrambe le direzioni: sia dal vertice A a B, sia da B ad A. Un grafo connesso è un grafo in cui almeno un percorso conduce da ciascun vertice a qualsiasi altro vertice (come nell'esempio Sopra ). Se questo non è il caso, il grafico diventa disconnesso : Inoltre, agli spigoli (archi) possono essere assegnati dei pesi - numeri che rappresentano la distanza fisica tra due vertici (o il tempo relativo di transizione tra due vertici). Tali grafici sono detti ponderati :

3. Algoritmi di ricerca del percorso (profondità, larghezza)

Una delle operazioni fondamentali che viene eseguita sui grafici è determinare tutti i vertici raggiungibili da un dato vertice. Immagina di provare a determinare come spostarti da una città all'altra con possibili trasferimenti. Alcune città possono essere raggiunte direttamente, mentre altre richiedono una deviazione attraverso altre città. Ci sono molte altre situazioni in cui può essere necessario trovare tutti i vertici verso i quali è possibile trovare un percorso da un dato vertice. Quindi, ci sono due modi principali per attraversare i grafici: attraversamento in profondità e attraversamento in larghezza , che prenderemo in considerazione. Entrambi i metodi garantiranno l'iterazione su tutti i vertici connessi. Per un'ulteriore considerazione degli algoritmi di profondità e ampiezza , prendere il seguente grafico:

Prima traversata in profondità

Questo è uno dei metodi di attraversamento del grafico più comuni. Questa strategia di ricerca in profondità consiste nell'andare "in profondità" nel grafico il più lontano possibile e, quando si raggiunge un vicolo cieco, tornare al vertice più vicino che ha vertici adiacenti che non sono stati visitati prima. Questo algoritmo memorizza le informazioni nello stack su dove tornare quando viene raggiunta una situazione di stallo. Regole per il primo attraversamento in profondità:

1. Visita un vertice adiacente, precedentemente non visitato, contrassegnalo e mettilo in pila.
2. Vai a questo vertice.
3. Ripetere il passaggio 1.
4. Se è impossibile completare il passaggio 1, tornare al vertice precedente e provare a ripetere la regola 1. Se ciò è impossibile, tornare al vertice precedente e così via, finché non troviamo un vertice dal quale possiamo continuare la traversata.
5. Continua finché tutti i vertici non sono in pila.

Diamo un'occhiata a come potrebbe apparire il codice per questo algoritmo in 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>

Il vertice appare così:

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

Eseguiamo questo algoritmo con vertici specifici e vediamo se funziona correttamente:

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

Uscita console: Poiché abbiamo una matrice di adiacenza e nel metodo walk utilizziamo un ciclo annidato all'interno di un ciclo, la complessità temporale sarà O(N²) .

Cammina in larghezza

Questo algoritmo, come l'attraversamento in profondità, è uno dei metodi più semplici e basilari per attraversare un grafico. La sua essenza è che abbiamo un certo vertice corrente, dal quale mettiamo in coda tutti i vertici adiacenti e non attraversati e selezioniamo l'elemento successivo (che è memorizzato per primo nella coda) per renderlo corrente... Se suddividiamo questo algoritmo in fasi, possiamo evidenziare le seguenti regole:

1. Visita il vertice successivo, precedentemente non visitato, adiacente al vertice corrente, contrassegnalo in anticipo e aggiungilo alla coda.
2. Se la regola n. 1 non può essere soddisfatta, rimuovi il vertice dalla coda e rendilo il vertice corrente.
3. Se le regole n. 1 e n. 2 sono impossibili, l'attraversamento è completato e tutti i vertici sono stati attraversati (se il nostro grafico è connesso).

La classe del grafico è quasi identica alla classe simile dell'algoritmo di ricerca deep-first, ad eccezione del metodo che elabora l'algoritmo e sostituisce lo stack interno con una coda:

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 è identica alla classe dell'algoritmo di ricerca in profondità . Mettiamo in azione questo algoritmo:

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

Uscita console: Ancora: abbiamo una matrice di adiacenza e utilizziamo un ciclo annidato all'interno di un ciclo, quindi O(N²) è la complessità temporale dell'algoritmo sopra.

4. Algoritmo di Dijkstra

Come accennato in precedenza, i grafici possono essere diretti o non orientati . E come ricordi, possono ancora essere ponderati . Grafici ponderati e diretti si trovano spesso nella vita reale: ad esempio, una mappa di città, dove le città sono i vertici, i percorsi tra loro sono strade, le strade possono avere traffico a senso unico: la direzione del grafico. Diciamo che sei impegnato nel trasporto merci e devi creare il percorso più breve tra due città distanti. Come lo farai? Uno dei problemi più comuni che coinvolgono i grafi pesati è il problema della scelta del percorso più breve tra due vertici. Per risolvere questo problema utilizziamo l'algoritmo di Dijkstra . Vorrei subito notare che eseguendo l'algoritmo di Dijkstra troveremo i percorsi più brevi verso tutti i vertici a partire da un dato iniziale. Quali fasi ha questo algoritmo? Proverò a rispondere a questa domanda. Fasi dell'algoritmo di Dijkstra:

• Fase 1 : ricerca del nodo la cui transizione avrà i costi minori. Ti trovi proprio all'inizio e ti chiedi dove andare: al nodo A o al nodo B. Quanto tempo ci vorrà per raggiungere ciascuno di questi nodi?
• Fase 2 : calcolo del tempo necessario per raggiungere tutti i vicini di B che non sono ancora stati interessati dall'algoritmo quando ci si sposta lungo un bordo da B. Se questo nuovo tempo risulta essere inferiore a quello vecchio, il percorso attraverso il bordo B diventerà il nuovo percorso più breve per questo vertice.
• Fase 3 : segnare il vertice B come superato.
• Passaggio 4 : vai al passaggio 1.

Ripeteremo il ciclo di queste fasi finché non saranno superati tutti i picchi. Consideriamo il seguente grafico diretto ponderato: Quindi, utilizzando l'algoritmo sopra, determineremo il percorso più breve da A a G:

1. Per il vertice A ci sono tre percorsi possibili: a B con peso 3, a C con peso 5 e a D con peso 7. Secondo il primo punto dell'algoritmo, selezioniamo il nodo con la transizione più bassa costo - cioè a B.
2. Poiché l'unico vertice vicino non attraversato per B è il vertice E , controlliamo quale sarà il percorso quando passa attraverso questo vertice. 3( AB ) + 6( BE ) = 9.

   Pertanto, notiamo che l'attuale percorso più breve verso AE = 9.

3. Poiché il nostro lavoro con il vertice B è già completato, passiamo alla selezione del vertice successivo con il peso minimo del bordo precedente.

   Dai vertici A e B questi possono essere i vertici D (7), C (5), E (6).

   C ha il peso del bordo più piccolo , quindi passiamo a questo vertice.

4. Successivamente, come prima, scopriamo il percorso più breve verso i vertici vicini quando passiamo attraverso C:
   • AD = 5( AC ) + 3( CD ) = 8, ma poiché il cammino minimo precedente AC = 7, cioè minore di questo attraverso C , lasciamo invariato il cammino minimo AD = 7.
   • CE = 5( AC ) + 4( CE ) = 9, questo nuovo cammino minimo è uguale al precedente quindi lasciamo invariato anche quello.
5. Dai vertici disponibili più vicini, E e D , selezioniamo il vertice con il peso del bordo più piccolo, cioè D (3).
6. Scopriamo il percorso più breve verso il suo vicino - F.

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

7. Dai vertici disponibili E e F più vicini , selezioniamo il vertice con il minor peso del bordo, cioè F (3).
8. Scopriamo il percorso più breve verso il suo vicino - G.

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

   In realtà qui abbiamo trovato il percorso da A a G.

   Ma per essere sicuri che sia il più corto, dobbiamo eseguire i nostri passi anche per il vertice E .

9. Poiché il vertice G non ha vertici vicini a cui condurrebbe un percorso diretto, ci rimane solo il vertice E : lo selezioniamo.
10. Scopriamo il percorso più breve per il vicino - G.

    AG = 3( AB ) + 6( BE ) + 6( EG ) = 15, questo percorso è più lungo del precedente AG(14) più corto, quindi lasciamo questo percorso invariato.

    Poiché non ci sono vertici che partono da G , non ha senso eseguire fasi per un dato vertice. Pertanto il lavoro dell’algoritmo può considerarsi concluso.

Come ho detto prima, oltre a trovare il percorso più breve per AG , abbiamo ottenuto i percorsi più brevi per tutti i vertici dal vertice A (AB, AC, AD, AE, AF) . Bene, è tempo di vedere come questo può essere implementato in Java. Innanzitutto, diamo un'occhiata alla classe dei vertici:

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 dei vertici è in realtà identica alla classe dei vertici della ricerca in profondità e in ampiezza. Per visualizzare i percorsi più brevi, abbiamo bisogno di una nuova classe che conterrà i dati di cui abbiamo bisogno:

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>

In questa classe possiamo vedere la distanza totale del percorso ed i vertici che verranno percorsi passando lungo il percorso più breve. E ora vorrei considerare la classe in cui, appunto, avviene la traversata più breve del grafico. Quindi, la classe del grafico:

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>

In realtà, questa è tutta la magia =) Bene, ora diamo un'occhiata a questo algoritmo in azione:

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 l'output nella console: La complessità temporale di questo algoritmo non è altro che O(N²) poiché abbiamo cicli annidati all'interno di un ciclo. Bene, per me oggi è tutto, grazie per l'attenzione!