Apa sing ditakoni ing wawancara: review algoritma, bagean 2

Artikel iki minangka lanjutan saka review singkat babagan algoritma. Punika link menyang bagean pisanan . Sadurunge, kita ndeleng macem-macem algoritma ngurutake array lan algoritma sing diarani rakus . Dina iki kita bakal ngomong babagan grafik lan algoritma sing ana gandhengane. Grafik minangka salah sawijining struktur sing paling fleksibel lan serbaguna ing pemrograman. Grafik G biasane ditemtokake nggunakake pasangan set G = (V, R) , ing ngendi:

• V - set saka vertex;
• R yaiku kumpulan garis sing nyambungake pasangan vertex.

Garis penghubung sing umum diarani pinggiran : Garis nganggo panah - busur : Biasane, grafik diwakili nggunakake diagram sing sawetara vertex disambungake kanthi pinggir (busur). Grafik sing disambungake karo busur sing langsung nuduhake arah kasebut diarani diarahake . Yen grafik disambungake kanthi pinggiran, yaiku, tanpa nuduhake arah gerakan sing bisa ditindakake, mula ora diarahake . Iki tegese gerakan bebarengan bisa ing loro arah: loro saka vertex A kanggo B, lan saka B kanggo A. Grafik sing disambungake minangka grafik sing paling ora siji path ndadékaké saka saben vertex menyang vertex liyane (kaya ing conto). ndhuwur). Yen ora, grafik dadi pedhot : Uga, pinggiran (busur) bisa diwenehi bobot - angka sing nuduhake jarak fisik antarane rong vertex (utawa wektu relatif transisi antarane rong vertex). Grafik kasebut diarani bobot :

3. Algoritma telusuran path (jero, jembar)

Salah sawijining operasi dhasar sing ditindakake ing grafik yaiku kanggo nemtokake kabeh vertex sing bisa digayuh saka vertex tartamtu. Mbayangno yen sampeyan nyoba nemtokake cara pindhah saka kutha menyang kutha liyane kanthi kemungkinan transfer. Sawetara kutha bisa tekan langsung, dene liyane mbutuhake detour liwat kutha liyane. Ana akeh kahanan liyane sing sampeyan kudu nemokake kabeh vertex sing sampeyan bisa nemokake dalan saka vertex tartamtu. Dadi, ana rong cara utama kanggo nglintasi grafik: depth-first traversal lan breadth-first traversal , sing bakal kita nimbang. Loro-lorone cara bakal njamin iterate liwat kabeh vertex disambungake. Kanggo pertimbangan luwih saka algoritma depth-first lan breadth-first , njupuk grafik ing ngisor iki:

Depth First Traversal

Iki minangka salah sawijining metode traversal grafik sing paling umum. Strategi panelusuran depth -first iki kalebu "jero" menyang grafik sabisa, lan nalika tekan buntu, bali menyang verteks paling cedhak sing nduweni verteks jejer sing durung dibukak sadurunge. Algoritma iki nyimpen informasi ing tumpukan babagan ngendi bali nalika deadlock tekan. Aturan kanggo depth first traversal:

1. Dolan maring vertex jejer, sadurunge ora dibukak, tandha lan sijine ing tumpukan.
2. Pindhah menyang pucuk iki.
3. Baleni langkah 1.
4. Yen ora bisa ngrampungake langkah 1, bali menyang vertex sadurunge lan coba mbaleni aturan 1. Yen iki ora mungkin, bali menyang vertex sadurunge, lan sateruse, nganti kita nemokake vertex saka ngendi kita bisa nerusake traversal.
5. Terusake nganti kabeh simpul ana ing tumpukan.

Ayo goleki kaya apa kode kanggo algoritma iki ing Jawa:

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>

Ndhuwur katon kaya:

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

Ayo mbukak algoritma iki kanthi simpul tartamtu lan deleng yen bisa digunakake kanthi bener:

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

Output konsol: Amarga kita duwe matriks adjacency lan ing cara mlaku kita nggunakake loop nested ing loop, kerumitan wektu bakal O(N²) .

Mlaku ing jembaré

Algoritma iki, kaya depth-first traversal, minangka salah sawijining cara sing paling gampang lan paling dhasar kanggo ngliwati grafik. Intine yaiku kita duwe vertex saiki tartamtu, saka ngendi kita sijine kabeh jejer, vertex untraversed menyang antrian lan pilih unsur sabanjuré (sing disimpen pisanan ing antrian) kanggo nggawe saiki ... Yen kita break algoritma iki menyang tahapan, kita bisa nyorot aturan ing ngisor iki:

1. Dolan maring simpul sabanjure, sing sadurunge ora dibukak ing jejere vertex saiki, tandhani luwih dhisik lan tambahake menyang antrian.
2. Yen aturan # 1 ora bisa kawujud, mbusak vertex saka antrian lan nggawe vertex saiki.
3. Yen aturan # 1 lan # 2 ora mungkin, traversal wis rampung lan kabeh vertex wis dilewati (yen grafik kita disambungake).

Kelas grafik meh padha karo kelas sing padha saka algoritma telusuran paling jero, kajaba metode sing ngolah algoritma lan ngganti tumpukan internal kanthi antrian:

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>

Kelas Vertex identik karo kelas saka algoritma telusuran paling jero . Ayo tumindak algoritma iki:

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

Output konsol: Maneh: kita duwe matriks adjacency lan nggunakake loop nested ing loop, supaya O(N²) minangka kerumitan wektu saka algoritma ndhuwur.

4. Algoritma Dijkstra

Kaya sing wis kasebut sadurunge, grafik bisa diarahake utawa ora diarahake . Lan yen sampeyan ngelingi, dheweke isih bisa ditimbang . Diboboti, diarahake graphs asring ditemokaké ing urip nyata: contone, peta kutha, ngendi kutha iku vertex, dalan antarane dalan, dalan bisa duwe lalu lintas siji-arah - arah grafik. Contone, sampeyan lagi melu transportasi kargo lan sampeyan kudu nggawe rute paling cedhak antarane rong kutha sing adoh. Kepiye carane sampeyan nindakake iki? Salah sawijining masalah sing paling umum nglibatake grafik bobot yaiku masalah milih jalur paling cedhak ing antarane rong simpul. Kanggo ngatasi masalah iki, kita nggunakake algoritma Dijkstra . Aku pengin langsung nyathet yen kanthi nglakokake algoritma Dijkstra, kita bakal nemokake dalan paling cendhak kanggo kabeh simpul saka wiwitan sing diwenehake. Apa tahapan algoritma iki? Aku bakal nyoba njawab pitakonan iki. Tahap-tahap algoritma Dijkstra:

• Tahap 1 : telusuran simpul, transisi sing bakal dadi biaya paling murah. Sampeyan lagi ngadeg ing wiwitan lan mikir menyang ngendi: menyang simpul A utawa menyang simpul B. Suwene suwene tekan saben simpul kasebut?
• Tahap 2 : ngitung wektu sing dibutuhake kanggo tekan kabeh tanggane B sing durung kena pengaruh algoritma nalika pindhah menyang pinggiran B. Yen wektu anyar iki dadi kurang saka sing lawas, jalur liwat pinggiran B bakal dadi jalur paling cedhak anyar kanggo vertex iki.
• Tahap 3 : tandha titik B minangka lulus.
• Langkah 4 : Pindhah menyang Langkah 1.

Kita bakal mbaleni siklus tahapan kasebut nganti kabeh puncak wis liwati. Ayo nimbang grafik diarahake bobot ing ngisor iki: Dadi, nggunakake algoritma ing ndhuwur, kita bakal nemtokake jalur paling cedhak saka A nganti G:

1. Kanggo vertex A ana telung dalan sing bisa ditindakake: menyang B kanthi bobot 3, menyang C kanthi bobot 5 lan menyang D kanthi bobot 7. Miturut titik pisanan saka algoritma, kita milih simpul kanthi transisi paling murah. biaya - yaiku, kanggo B.
2. Wiwit siji-sijine simpul tetanggan sing ora bisa dilewati kanggo B yaiku simpul E , kita mriksa apa dalan sing bakal ditindakake nalika ngliwati vertex iki. 3( AB ) + 6( BE ) = 9.

   Dadi, kita nyathet yen jalur paling cedhak saiki menyang AE = 9.

3. Wiwit karya kita karo vertex B wis rampung, kita nerusake kanggo milih vertex sabanjuré karo bobot minimal saka pinggiran sadurunge iku.

   Saka simpul A lan B iki bisa dadi simpul D (7), C (5), E (6).

   C nduweni bobot pinggir paling cilik , mula kita pindhah menyang verteks iki.

4. Sabanjure, kaya sadurunge, kita nemokake dalan paling cedhak menyang simpul tetanggan nalika ngliwati C:
   • AD = 5 ( AC ) + 3 ( CD ) = 8, nanging wiwit dalan paling cedhak sadurunge AC = 7, yaiku kurang saka siji iki liwat C , kita ninggalake dalan paling cendhak AD = 7 ora diganti.
   • CE = 5( AC ) + 4( CE ) = 9, path paling cedhak anyar iki padha karo sing sadurunge supaya kita ninggalake iku uga ora diganti.
5. Saka vertex sing paling cedhak, E lan D , kita milih vertex kanthi bobot pinggir paling cilik, yaiku, D (3).
6. Kita nemokake dalan sing paling cedhak karo pepadhamu - F.

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

7. Saka simpul paling cedhak sing kasedhiya E lan F , kita milih vertex kanthi bobot paling sithik ing pinggiran, yaiku, F (3).
8. Kita nemokake dalan sing paling cedhak kanggo pepadhamu - G.

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

   Bener, ing kene kita nemokake dalan saka A nganti G.

   Nanging kanggo mesthekake yen iku paling cendhak, kita kudu mbukak langkah kita kanggo vertex E uga .

9. Wiwit vertex G ora duwe vertex tetanggan sing dalan diarahake, kita mung duwe vertex E kiwa : kita pilih.
10. Kita nemokake dalan sing paling cedhak kanggo pepadhamu - G.

    AG = 3 ( AB ) + 6 ( BE ) + 6 ( EG ) = 15, dalan iki luwih dawa tinimbang AG paling cedhak sadurungé (14), supaya kita ninggalake dalan iki ora diganti.

    Amarga ora ana vertex sing anjog saka G , ora ana gunane kanggo mbukak tahapan kanggo vertex tartamtu. Mulane, karya algoritma bisa dianggep lengkap.

Kaya sing wis dakkandhakake sadurunge, saliyane nemokake jalur paling cendhak kanggo AG , kita entuk jalur paling cedhak kanggo kabeh simpul saka vertex A (AB, AC, AD, AE, AF) . Nah, wektune dideleng kepiye carane iki bisa dileksanakake ing Jawa. Pisanan, ayo goleki kelas 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;
   }
}

Kelas vertex sejatine identik karo kelas vertex saka telusuran depth-first lan breadth-first. Kanggo nampilake dalan paling cendhak, kita butuh kelas anyar sing bakal ngemot data sing dibutuhake:

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>

Ing kelas iki kita bisa ndeleng total kadohan saka path lan vertex sing bakal ditutupi nalika liwat dalan paling cendhak. Lan saiki aku pengin nimbang kelas sing, ing kasunyatan, traversal paling cendhak saka grafik dumadi. Dadi, kelas grafik:

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>

Bener, iku kabeh keajaiban =) Saiki, ayo deleng algoritma iki ing tumindak:

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

Lan output ing console: Kompleksitas wektu algoritma iki ora luwih saka O(N²) amarga kita duwe puteran sing dipasang ing loop. Inggih, iku kabeh kanggo kula dina iki, matur nuwun kanggo manungsa waé!