Ця стаття є продовженням мого невеликого огляду алгоритмів. Ось посилання на першу частину . Раніше ми розглядали різні алгоритми сортування масивів і так званий жадібний алгоритм . Сьогодні ж ми поговоримо про графи та алгоритми, пов'язані з ними. Граф — одна з найбільш гнучких та універсальних структур у програмуванні. Граф G зазвичай задається за допомогою пари множин G = (V, R) , де:
- V - безліч вершин;
- R - безліч ліній, що з'єднують пари вершин.
3. Алгоритми пошуку шляху (глибина, ширина)
Однією з основних операцій, які виконуються з графами, є визначення всіх вершин, досяжних від заданої вершини. Уявіть, що ви намагаєтеся визначити, як можна дістатися від одного міста до іншого з можливими пересадками. До одних міст можна дістатися безпосередньо, до інших потрібно їхати в обхід через інші міста. Існує багато інших ситуацій, у яких може знадобитися знаходження всіх вершин, яких можна знайти шлях від заданої вершини. Так ось, існує два основних способи обходу графів: обхід у глибину та обхід у ширину , які ми й розглянемо. Обидва способи забезпечать перебір всіх зв'язкових вершин. Для подальшого розгляду алгоритмів у глибину та ширину візьмемо наступний граф:Обхід углиб
Це один із найпоширеніших методів обходу графа. Ця стратегія пошуку в глибину полягає в тому, щоб йти «вглиб» графа наскільки це можливо, а досягнувши глухого кута, повертатися до найближчої вершини, яка має суміжні раніше не відвідані вершини. Цей алгоритм зберігає в стеку інформацію про те, куди слід повернутися при досягненні “глухого кута”. Правила обходу в глибину:- Відвідати суміжну, раніше не відвідану вершину, помітити її та занести у стек.
- Перейти на цю вершину.
- Повторити етап 1.
- Якщо виконання пункту 1 неможливе, повернутися до попередньої вершини і спробувати повторити правило 1. Якщо це неможливо — повернутися до вершини до неї, і так далі, доки не знайдемо вершину, з якої можна продовжити обхід.
- Продовжувати доти, доки всі вершини не опиняться у стеку.
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();
}
}
Висновок у консолі:
Відгуки: A B E C D F G
Оскільки ми маємо матрицю суміжності й у методі проходу ми використовуємо цикл, вкладений цикл, то тимчасова складність буде O(N²) .
Обхід завширшки
Даний алгоритм, як і обхід у глибину, є одним із найпростіших і базових методів обходу графа. Його суть у тому, що у нас є певна поточна вершина, з якої ми всі суміжні, непройдені вершини, заносимо в чергу і вибираємо наступний елемент (який зберігається першим у черзі), щоб його зробити поточним… Якщо розбити цей алгоритм на етапи, можна виділити такі правила:- Завітати до наступної, раніше не відвіданої вершини, суміжної з поточною вершиною, помітити її заздалегідь і занести в чергу.
- Якщо виконання правила #1 неможливе — витягти вершину з черги і зробити її поточною вершиною.
- Якщо правило #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();
}
}
Виведення в консоль:
Відгуки: A B C D E F G
Знову ж таки: ми маємо матрицю суміжності і використовуємо цикл, вкладений у цикл, тому O(N²) — тимчасова складність наведеного алгоритму.
4. Алгоритм Дейкстри
Як говорилося раніше, графи можуть бути спрямованими та неспрямованими . І як ви пам'ятаєте, вони ще можуть бути зваженими . Зважені, спрямовані графи часто трапляються й у реальному житті: наприклад, карта міст, де міста — вершини, шляхи з-поміж них — дороги, дороги може мати односторонній рух — напрям графа. Допустимо, ви займаєтеся вантажоперевезеннями і потрібно скласти найкоротший шлях між двома віддаленими містами. Як ви це зробите? Однією з найпоширеніших завдань, що з виваженими графами, є завдання вибору найкоротшого шляху між двома вершинами. Для вирішення даної задачі ми використовуємо алгоритм Дейкстри. Хотілося б відразу зазначити, що, виконавши алгоритм Дейкстри, ми дізнаємося про найкоротші шляхи до всіх вершин від заданої початкової. Які ж етапи має цей алгоритм? Спробую відповісти на це запитання. Етапи алгоритму Дейкстри:- Етап 1 : пошук вузла, перехід до якого становитиме найменшу вартість. Ви стоїте на самому початку і думаєте, куди вирушити: до вузла А або до вузла В . Скільки часу знадобиться, щоб дістатися кожного з цих вузлів?
- Етап 2 : обчислення, скільки часу потрібно , щоб дістатися до всіх ще не порушених алгоритмом сусідів при переході по ребру з . Якщо ж цей новий час виявиться меншим за старий, шлях через ребро B і стане новим найкоротшим шляхом для цієї вершини.
- Етап 3 : помічаємо вершину B як пройдену.
- Етап 4 : перейти до етапу 1.
- Для вершини A є три можливі шляхи: B з вагою 3, С з вагою 5 і D з вагою 7. Згідно з першим пунктом алгоритму вибираємо вузол з найменшою вартістю переходу — тобто до B .
- Так як єдиною непройденою вершиною-сусідом для B буде вершина Е , ми перевіряємо, який буде шлях при проходженні через цю вершину. 3( AB ) + 6( BE ) = 9.
Таким чином, ми відзначаємо, що поточний найкоротший шлях до AE = 9.
- Оскільки наша робота з вершиною B вже закінчена, переходимо до вибору наступної вершини з мінімальною вагою ребра до неї.
З вершин A та B це можуть бути вершини D (7), C (5), E (6).
Найменша вага ребра має З , тому до цієї вершини і перейдемо.
- Далі, як і раніше, з'ясовуємо найкоротший шлях до сусідніх вершин при проході через С:
- AD = 5( AC ) + 3( CD ) = 8, але оскільки попередній найкоротший шлях AC = 7, тобто менше, ніж цей через З , ми так і залишаємо найкоротший шлях AD = 7, без змін.
- CE = 5( AC ) + 4( CE ) = 9, цей новий найкоротший шлях дорівнює колишньому тому ми залишаємо його без зміни теж.
- З найближчих доступних вершин, E і D вибираємо вершину з найменшою вагою ребра, тобто D (3).
- З'ясовуємо найкоротший шлях до його сусіда – F .
AF = 7( AD ) + 3( DF ) = 10
- З найближчих доступних вершин E і F вибираємо вершину з найменшою вагою ребра до неї, тобто F (3).
- З'ясовуємо найкоротший шлях до його сусіда G .
AG = 7( AD ) + 3( DF ) + 4( FG ) = 14
Власне, ось ми знайшли шлях від A до G .
Але щоб переконатися, що він найкоротший, ми повинні прогнати наші етапи і для вершини E .
- Оскільки вершина G не має сусідніх вершин, до яких вів би спрямований шлях, у нас залишається тільки вершина E : вибираємо її.
- З'ясовуємо найкоротший шлях до сусіда - G.
AG = 3( AB ) + 6( BE ) + 6( EG ) = 15, цей шлях довший за колишній найкоротший AG(14), тому даний шлях ми залишаємо без змін.
Оскільки вершин, які від G , немає, проганяти етапи цієї вершини немає сенсу. Тому роботу алгоритму вважатимуться закінченою.
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();
}
}
І висновок у консолі:
Елементи мають найкоротші шляхи з точки A: A = 0 B = 3 (A -> B) C = 5 (A -> C) D = 7 (A -> D) E = 9 (A -> B -> E) F = 10 (A -> D -> F) G = 14 (A -> D -> F -> G)
Тимчасова складність даного алгоритму — ніщо інше як O(N²) , оскільки ми маємо цикли, вкладені в цикл. Що ж, на цьому у мене сьогодні все, дякую за увагу!
ПЕРЕЙДІТЬ В ПОВНУ ВЕРСІЮ