Що запитують на співбесіді: огляд алгоритмів, частина 2

Ця стаття є продовженням мого невеликого огляду алгоритмів. Ось посилання на першу частину . Раніше ми розглядали різні алгоритми сортування масивів і так званий жадібний алгоритм . Сьогодні ж ми поговоримо про графи та алгоритми, пов'язані з ними. Граф — одна з найбільш гнучких та універсальних структур у програмуванні. Граф G зазвичай задається за допомогою пари множин G = (V, R) , де:

• V - безліч вершин;
• R - безліч ліній, що з'єднують пари вершин.

Звичайні сполучні лінії називають ребрами : Лінії зі стрілками - дугами : Як правило, граф представляють за допомогою схеми, на якій деякі вершини з'єднані ребрами (дугами). Графи, пов'язані між собою дугами, що безпосередньо вказують напрям, називають спрямованими . Якщо ж графи з'єднані ребрами, тобто без зазначення напряму можливого руху, вони стають ненаправленими . Це означає, що переміщення по них можливі в обох напрямках: як від вершини А до В, так і від В до А. Зв'язковий граф - граф, в якому від кожної вершини до будь-якої іншої вершини веде хоча б один шлях (як на прикладі вище ). Якщо це не так, граф стає незв'язним: Також ребрам (дугам) можуть присвоюватися ваги - числа, що становлять фізичну відстань між двома вершинами (або відносний час переходу між двома вершинами). Такі графи і називають зваженими :

3. Алгоритми пошуку шляху (глибина, ширина)

Однією з основних операцій, які виконуються з графами, є визначення всіх вершин, досяжних від заданої вершини. Уявіть, що ви намагаєтеся визначити, як можна дістатися від одного міста до іншого з можливими пересадками. До одних міст можна дістатися безпосередньо, до інших потрібно їхати в обхід через інші міста. Існує багато інших ситуацій, у яких може знадобитися знаходження всіх вершин, яких можна знайти шлях від заданої вершини. Так ось, існує два основних способи обходу графів: обхід у глибину та обхід у ширину , які ми й розглянемо. Обидва способи забезпечать перебір всіх зв'язкових вершин. Для подальшого розгляду алгоритмів у глибину та ширину візьмемо наступний граф:

Обхід углиб

Це один із найпоширеніших методів обходу графа. Ця стратегія пошуку в глибину полягає в тому, щоб йти «вглиб» графа наскільки це можливо, а досягнувши глухого кута, повертатися до найближчої вершини, яка має суміжні раніше не відвідані вершини. Цей алгоритм зберігає в стеку інформацію про те, куди слід повернутися при досягненні “глухого кута”. Правила обходу в глибину:

1. Відвідати суміжну, раніше не відвідану вершину, помітити її та занести у стек.
2. Перейти на цю вершину.
3. Повторити етап 1.
4. Якщо виконання пункту 1 неможливе, повернутися до попередньої вершини і спробувати повторити правило 1. Якщо це неможливо — повернутися до вершини до неї, і так далі, доки не знайдемо вершину, з якої можна продовжити обхід.
5. Продовжувати доти, доки всі вершини не опиняться у стеку.

Давайте поглянемо, як може виглядати код для даного алгоритму 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>

Вершина має вигляд:

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

Запустимо цей алгоритм з конкретними вершинами та подивимося на коректність роботи:

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

Висновок у консолі: Оскільки ми маємо матрицю суміжності й у методі проходу ми використовуємо цикл, вкладений цикл, то тимчасова складність буде O(N²) .

Обхід завширшки

Даний алгоритм, як і обхід у глибину, є одним із найпростіших і базових методів обходу графа. Його суть у тому, що у нас є певна поточна вершина, з якої ми всі суміжні, непройдені вершини, заносимо в чергу і вибираємо наступний елемент (який зберігається першим у черзі), щоб його зробити поточним… Якщо розбити цей алгоритм на етапи, можна виділити такі правила:

1. Завітати до наступної, раніше не відвіданої вершини, суміжної з поточною вершиною, помітити її заздалегідь і занести в чергу.
2. Якщо виконання правила #1 неможливе — витягти вершину з черги і зробити її поточною вершиною.
3. Якщо правило #1 і #2 неможливо, обхід закінчено, проте вершини пройдені (якщо граф в нас зв'язковий).

Клас графа практично ідентичний аналогічному класу з алгоритму пошуку в глибину, за винятком методу, що обробляє алгоритм та заміни внутрішнього стека на чергу:

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>

Клас Vertex ідентичний класу з алгоритму пошук у глибину . Давайте наведемо цей алгоритм у дію:

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

Виведення в консоль: Знову ж таки: ми маємо матрицю суміжності і використовуємо цикл, вкладений у цикл, тому O(N²) — тимчасова складність наведеного алгоритму.

4. Алгоритм Дейкстри

Як говорилося раніше, графи можуть бути спрямованими та неспрямованими . І як ви пам'ятаєте, вони ще можуть бути зваженими . Зважені, спрямовані графи часто трапляються й у реальному житті: наприклад, карта міст, де міста — вершини, шляхи з-поміж них — дороги, дороги може мати односторонній рух — напрям графа. Допустимо, ви займаєтеся вантажоперевезеннями і потрібно скласти найкоротший шлях між двома віддаленими містами. Як ви це зробите? Однією з найпоширеніших завдань, що з виваженими графами, є завдання вибору найкоротшого шляху між двома вершинами. Для вирішення даної задачі ми використовуємо алгоритм Дейкстри. Хотілося б відразу зазначити, що, виконавши алгоритм Дейкстри, ми дізнаємося про найкоротші шляхи до всіх вершин від заданої початкової. Які ж етапи має цей алгоритм? Спробую відповісти на це запитання. Етапи алгоритму Дейкстри:

• Етап 1 : пошук вузла, перехід до якого становитиме найменшу вартість. Ви стоїте на самому початку і думаєте, куди вирушити: до вузла А або до вузла В . Скільки часу знадобиться, щоб дістатися кожного з цих вузлів?
• Етап 2 : обчислення, скільки часу потрібно , щоб дістатися до всіх ще не порушених алгоритмом сусідів при переході по ребру з . Якщо ж цей новий час виявиться меншим за старий, шлях через ребро B і стане новим найкоротшим шляхом для цієї вершини.
• Етап 3 : помічаємо вершину B як пройдену.
• Етап 4 : перейти до етапу 1.

Цикл цих етапів ми повторюватимемо доти, доки всі вершини не будуть пройдені. Давайте розглянемо наступний зважений спрямований граф: Отже, за допомогою наведеного вище алгоритму ми визначимо найкоротший шлях від A до G:

1. Для вершини A є три можливі шляхи: B з вагою 3, С з вагою 5 і D з вагою 7. Згідно з першим пунктом алгоритму вибираємо вузол з найменшою вартістю переходу — тобто до B .
2. Так як єдиною непройденою вершиною-сусідом для B буде вершина Е , ми перевіряємо, який буде шлях при проходженні через цю вершину. 3( AB ) + 6( BE ) = 9.

   Таким чином, ми відзначаємо, що поточний найкоротший шлях до AE = 9.

3. Оскільки наша робота з вершиною B вже закінчена, переходимо до вибору наступної вершини з мінімальною вагою ребра до неї.

   З вершин A та B це можуть бути вершини D (7), C (5), E (6).

   Найменша вага ребра має З , тому до цієї вершини і перейдемо.

4. Далі, як і раніше, з'ясовуємо найкоротший шлях до сусідніх вершин при проході через С:
   • AD = 5( AC ) + 3( CD ) = 8, але оскільки попередній найкоротший шлях AC = 7, тобто менше, ніж цей через З , ми так і залишаємо найкоротший шлях AD = 7, без змін.
   • CE = 5( AC ) + 4( CE ) = 9, цей новий найкоротший шлях дорівнює колишньому тому ми залишаємо його без зміни теж.
5. З найближчих доступних вершин, E і D вибираємо вершину з найменшою вагою ребра, тобто D (3).
6. З'ясовуємо найкоротший шлях до його сусіда – F .

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

7. З найближчих доступних вершин E і F вибираємо вершину з найменшою вагою ребра до неї, тобто F (3).
8. З'ясовуємо найкоротший шлях до його сусіда G .

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

   Власне, ось ми знайшли шлях від A до G .

   Але щоб переконатися, що він найкоротший, ми повинні прогнати наші етапи і для вершини E .

9. Оскільки вершина G не має сусідніх вершин, до яких вів би спрямований шлях, у нас залишається тільки вершина E : вибираємо її.
10. З'ясовуємо найкоротший шлях до сусіда - G.

    AG = 3( AB ) + 6( BE ) + 6( EG ) = 15, цей шлях довший за колишній найкоротший AG(14), тому даний шлях ми залишаємо без змін.

    Оскільки вершин, які від G , немає, проганяти етапи цієї вершини немає сенсу. Тому роботу алгоритму вважатимуться закінченою.

Як я й казав раніше, окрім з'ясування найкоротшого шляху для AG , ми отримали найкоротші шляхи до всіх вершин від вершини A (AB, AC, AD, AE, AF) . Що ж, настав час подивитися, яким чином це можна продати на Java. Для початку розглянемо клас вершини:

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

Клас вершини фактично ідентичний класу вершини з пошуку глибину і ширину. Щоб відобразити найкоротші шляхи, нам знадобиться новий клас, який міститиме необхідні нам дані:

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

У цьому класі ми можемо бачити загальну дистанцію колії та вершини, які будуть пройдені при проході найкращим шляхом. А зараз хотілося б розглянути клас, у якому, власне, і відбувається найкоротший обхід графа. Отже, клас графа:

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

Власне, ось і вся магія =) Ну а тепер, погляньмо на даний алгоритм у дії:

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

І висновок у консолі: Тимчасова складність даного алгоритму — ніщо інше як O(N²) , оскільки ми маємо цикли, вкладені в цикл. Що ж, на цьому у мене сьогодні все, дякую за увагу!