Представление графов. Матрица смежности Граф: 4 1 67 23 8 5 01010100 10000110 00001001 10000100 00100001 11010010 01000100 00101000 1 2 3 4 5 6 7 8 1 2. - презентация

1 Представление графов. Матрица смежности Граф: Удобно: Добавлять и удалять ребра Проверять смежность вершин Неудобно: Добавлять и удалять вершины Работать с разреженными графами

2 Представление графов. Матрица инцидентности Граф: Удобно: Менять нагрузку на ребра Проверять инцидентность Неудобно: Добавлять и удалять вершины Работать с разреженными графами

3 Представление графов. Списки смежности Граф: Удобно: Искать вершины, смежные с данной Добавлять ребра и вершины Неудобно: Проверять наличие ребра Удалять ребра и вершины Работать с разреженными графами

4 Представление графов. Список ребер Граф: Удобно: Добавлять и удалять ребра Упорядочивать ребра по возрастанию нагрузки Неудобно: Определять смежность вершин и ребер Осуществлять перебор инцидентных заданной вершине ребер Представлять сильно разреженные графы

5 Обходы графов. Рекурсивная процедура Обход вершин и дуг графа, достижимых из заданной вершины (v): 1.Пометить вершину (v) как пройденную вперед 2.Цикл по дугам (e), инцидентным вершине (v) 1)Пометить дугу (e) как пройденную вперед 2)Если конец дуги (u) не отмечен, то обойти достижимые из (u) вершины и дуги (рекурсивный вызов) 3)Пометить дугу (e) как пройденную назад 3.Пометить вершину (v) как пройденную назад Задачи, которые можно решить с помощью этой процедуры: 1.Определить вершины, достижимые из заданной; 2.Обойти все вершины и дуги графа в определенной последовательности («в глубину»); 3.Определить некоторые характеристики связности графа; … и многие другие

6 Обходы графов. Рекурсивная процедура public class Graph { public static class Arc { public Arc(int to, double weight, Arc next) { this.to = to; this.weight = weight; this.next = next; } private int to; private double weight; private Arc next; } private int nVert; private Arc[] list; public Graph(int nVert) { this.nVert = nVert; list = new Arc[nVert]; } private static void traverseDepthComponent (int i, Graph g, GraphVisitor visitor, boolean[] visited) { visitor.visitVertexIn(i); visited[i] = true; for (Iterator arcs = g.adjacentArcs(i); arcs.hasNext(); ) { Graph.Arc arc = (Graph.Arc)arcs.next(); visitor.visitArcForward(i, arc, visited[arc.getTo()]); if (!visited[arc.getTo()]) { traverseDepthComponent(arc.getTo(), g, visitor, visited); } visitor.visitArcBackward(i, arc); } visitor.visitVertexOut(i); } public abstract class GraphVisitor { public void visitArcForward(int from, Graph.Arc arc, boolean retArc) {} public void visitArcBackward(int from, Graph.Arc arc) {} public void visitVertexIn(int v) {} public void visitVertexOut(int v) {} public void visitComponentStart(int start) {} }

7 Топологическая сортировка вершин ориентированного графа без циклов. DAG – Directed Acyclic Graph – ориентированный граф без циклов Интерпретация: вершины – элементарные работы; дуги – зависимость работ друг от друга. Задача: выстроить работы в последовательности, в которой никакая следующая задача не может зависеть от предыдущей (дуги направлены только вперед)

8 Топологическая сортировка вершин ориентированного графа без циклов «Наивный» алгоритм нумерации вершин: 1.Находим какую-либо вершину, в которую не входят дуги, нумеруем ее. 1 2.Помечаем дуги, выходящие из помеченной вершины, как «не существующие». 3.Повторяем шаги (1) и (2), пока не будут занумерованы все вершины Оценка времени работы алгоритма. 1.Построение очереди с приоритетами из вершин графа n log n 2.Выборка вершин из очереди n log n 3.Коррекция очереди при пометке дуг m log n Итого: (m+2n) log n Проверка ацикличности графа. Граф содержит цикл, если на шаге (1) не удается найти вершину, в которую не входят дуги.

9 Топологическая сортировка вершин ориентированного графа без циклов «Эффективный» алгоритм нумерации вершин: 1.Производим обход графа с помощью рекурсивной процедуры обхода, начиная с произвольной вершины. 2.Нумеруем каждую вершину при «прохождении ее назад» максимальным из номеров (то есть нумерация происходит в порядке убывания номеров). 3.Повторяем шаги (1) и (2), пока не останется непройденных вершин Оценка времени работы алгоритма = время обхода = (m+n). Проверка ацикличности графа. Граф содержит цикл, если при проходе по «обратной дуге» попадаем в еще непомеченную («синюю») вершину.

10 Обходы графов. Общая процедура с использованием структуры хранения вершин Начинаем с произвольной выбранной вершины v. 2.Помещаем вершину v в контейнер: Collection cont = new Collection(); cont.add(v); 3.Цикл while (!cont.empty()) 1)Выбрать вершину и пометить ее: mark(current = cont.get()); 2)Просмотреть все инцидентные ребра i.Если ребро ведет в непомеченную вершину u (прямая дуга на ребре), cont.add(v); ii.Иначе, если ребро идет в вершину из контейнера (обратная дуга на ребре) или в помеченную вершину (встречная дуга), то ничего не делаем. Контейнер: Граф: Используя различные контейнеры, с помощью этой процедуры можно решать разнообразные задачи: Обходы вершин и дуг графа в различном порядке (итерация) Поиск маршрутов, в том числе, минимальных и многие другие…

11 Использование стека для обхода графа. Если в качестве промежуточной структуры хранения при обходе использовать стек, то получается обход в глубину Граф: Можно также получить дерево обхода в глубину, если отмечать каждую прямую или обратную дугу Стек:

12 Использование очереди для обхода графа. Если в качестве промежуточной структуры хранения при обходе использовать очередь, то получается обход в ширину Граф: 1 Можно также получить дерево обхода в ширину, если отмечать каждую прямую дугу Очередь:

13 Поиск кратчайших путей в ненагруженном графе Граф: Очередь: Алгоритм обхода графа с помощью очереди позволяет построить дерево кратчайших путей из заданной вершины и вычислить их длины. n π d

14 Программа обхода графа с использованием контейнера. public static void traverseWithContainer(Graph g, GraphVisitor visitor, int start, ContainerFactory factory) { // Инициализация int n = g.vertices(); // Число вершин графа Container container = factory.createContainer(n); // Создание контейнера container.push(start); // Инициализация контейнера boolean[] inQueue = new boolean[n]; boolean[] passed = new boolean[n]; inQueue[start] = true; visitor.visitVertexIn(start); while (!container.isEmpty()) { int current = container.pull(); passed[current] = true; visitor.visitVertexOut(current); for (Iterator arcs = g.adjacentArcs(current); arcs.hasNext(); ) { Graph.Arc arc = (Graph.Arc)arcs.next(); int end = arc.getTo(); if (passed[end]) visitor.visitArcBackward(current, arc); else { visitor.visitArcForward(current, arc, inQueue[end]); if (!inQueue[end]) { container.push(end); inQueue[end] = true; visitor.visitVertexIn(end); }

15 Программа поиска кратчайших путей в ненагруженном графе. public static void findMinPaths(Graph g, // Исходный граф int start, // Стартовая вершина final int[] tree, // Результирующее дерево final int[] dist) // Массив расстояний { dist[start] = 0; tree[start] = 0; traverseWithContainer(g, new GraphVisitor() { // Коррекция пути производится при первом проходе по дуге вперед public void visitArcForward(int from, Graph.Arc arc, boolean retArc) { if (!retArc) { int end = arc.getTo(); dist[end] = dist[from] + 1; tree[end] = from; } }, start, new QueueFactory()); }

16 Алгоритмы поиска кратчайших путей в нагруженном графе. Кратчайший путь между двумя вершинами – это путь с минимальным суммарным весом составляющих этот путь ребер Кратчайший путь между двумя вершинами существует, если в графе нет цикла с суммарным отрицательным весом Кратчайшие пути из вершины (10): VДлинаПуть через , , 8 или 3, , 8

17 Алгоритм релаксации ребра при поиске кратчайших путей Пусть уже найдены оценки кратчайших путей для вершин, соединенных ребром. 9 6 d[8] = 6; d[7] = 9 Релаксация ребра (u, v): if (d[u] + w(u,v) < d[v]) d[v] = d[u] + w(u,v); Релаксация ребра (7, 8): > 6 Релаксация ребра (8, 7): < 9 d[7] = 8 8 Инициализация: d[start] = 0; d[i] = Последовательная релаксация ребер приведет к нахождению кратчайших путей. В каком порядке и сколько раз производить релаксацию ребер?

18 Алгоритм Дейкстры поиска кратчайших путей. Запустить алгоритм обхода графа, в качестве контейнера выбрать очередь с приоритетами. Приоритет – текущая величина найденного расстояния от начальной вершины. Релаксации подвергаются прямые и обратные ребра Очередь n π d

19 Программа для реализации алгоритма Дейкстры поиска кратчайших путей. public static void DijkstraPath(Graph g, int start, final int[] tree, final double[] dist) { for (int i = 0; i < g.vertices(); i++) { dist[i] = Double.MAX_VALUE; } dist[start] = 0; traverseWithContainer(g, new DepthVisitor() { public void visitArcForward(int from, Graph.Arc arc, boolean retArc) { if (dist[from] + arc.getWeight() < dist[arc.getTo()]) { dist[arc.getTo()] = dist[from] + arc.getWeight(); tree[arc.getTo()] = from; } }, start, new SimplePrioQueueFactory(dist)); } Время работы алгоритма (max): время обхода графа (n + m) плюс время на организацию работы очереди с приоритетами (n log n)

20 Кратчайшие пути в ориентированном графе 1.Если в ориентированном графе нет дуг с отрицательным весом, то алгоритм Дейкстры работает точно так же, как и в случае неориентированных графов. 2.Если в ориентированном графе нет циклов с отрицательным весом, то можно применить алгоритм Беллмана – Форда n π d И так далее… В конце концов получится… 3 12

21 n π d Кратчайшие пути в ориентированном графе 3.Если в ориентированном графе нет циклов, то можно провести топологическую сортировку вершин, после чего выполнить релаксацию исходящих дуг в порядке возрастания номеров вершин Один из вариантов применения алгоритма: нахождение критического пути.

22 Транзитивное замыкание графа отношения. Ориентированный ненагруженный граф представляет отношение на множестве его вершин: R : V V u R v есть дуга, ведущая из u в v Отношение транзитивно, если u, v, w: u R v, v R w u R w Транзитивное замыкание отношения – пополнение отношения новыми парами так, чтобы пополненное отношение стало транзитивным (необходимо добавить минимальное число таких пар) Отношение не транзитивно Отношение транзитивно Задача нахождения транзитивного замыкания на языке графов: провести новую дугу из u в v, если в исходном графе существовал путь из u в v.

23 Транзитивное замыкание графа отношения. Алгоритм «умножения матриц» Пусть матрица G ( l ) представляет собой граф путей длиной l (то есть в матрице единица находится в ячейке (u,v), если в исходном графе существовал путь из u в v длиной не больше l ). Тогда матрица G (1) – это матрица смежности исходного графа G, G (n) – матрица смежности его транзитивного замыкания (очевидно, что если в графе существует путь длины, большей n, то существует и путь, длины не большей n). Алгоритм нахождения транзитивного замыкания: если удается вычислить G ( l+1 ) по G ( l ), то можно, начав с матрицы G, за n шагов получить матрицу G (n).

24 Транзитивное замыкание графа отношения. Алгоритм «умножения матриц». Пусть матрица G ( l ) представляет собой граф путей длиной l (то есть в матрице G ( l ) единица находится в ячейке (u,v), если в исходном графе существовал путь из u в v длиной не больше l ). Тогда что такое матрица G ( l+1 ) ? uv l +1 w l G ( l+1 ) [u,v] = 1, если найдется w такое, что G ( l ) [u,w] = 1 и G [w,v] = 1. G ( l+1 ) [u,v] = G ( l ) [u,w] × G [w,v] (умножение и сложение понимаются в смысле логических операций «и» и «или») public static boolean[][] multiply (boolean[][] matr1, boolean[][] matr2) { int n = matr1.length; boolean[][] matr = new boolean[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { matr[i][j] = false; for (int k = 0; k < n; k++) { matr[i][j] ||= matr1[i][k] && matr2[k][j]; }}} return matr; } public static boolean[][] transClosure(boolean[][] G) { boolean[][] Gl = G; for (int l = 1; l < n; l++) { Gl = multiply(Gl, g); } } Алгоритм умножения матриц:

25 Транзитивное замыкание графа отношения. Алгоритм Флойда – Уоршалла Алгоритм умножения матриц требует порядка n 4 простых логических операций. Алгоритм Флойда – Уоршалла требует лишь n 3 простых операций и не требует дополнительной памяти под промежуточные матрицы. Пусть матрица G ( l ) представляет собой граф путей, проходящих через промежуточные вершины с номерами от 0 до l -1 (то есть в матрице G ( l ) единица находится в ячейке (u,v), если в исходном графе существовал путь из u в v, проходящий только через вершины из множества {0,… l -1}, u и v в это множество не входят). Тогда что такое матрица G ( l+1 ) ? uv {0,1,… l } uv {0,1,… l -1 } 1) G ( l+1 ) [u,v] = 1, если G ( l ) [u,v] == 1 uv {0,1,… l -1 } 2) G ( l+1 ) [u,v] = 1, если G ( l ) [u,l] == 1 && G ( l ) [l,v] == 1 l {0,1,… l -1 } G (l+1) [u,v] = G (l) [u,v] || G (l) [u,l] && G (l) [l,v]

26 Транзитивное замыкание графа отношения. Алгоритм Флойда – Уоршалла G (l+1) [u,v] = G (l) [u,v] || G (l) [u,l] && G (l) [l,v] При u = l всегда G (l+1) [u] = G (l) [u] public static boolean[][] transClosure (boolean[][] G) { int n = G.length; for (int l = 0; l < n; l++) { // Формирование матрицы G(l+1): for (int u = 0; u < n; u++) { if (G[u][l]) { for (int v = 0; v < n; v++) { G[u][v] ||= G[l][v]; } return G; } Алгоритм Флойда – Уоршалла нахождения транзитивного замыкания графа отношения.

27 Применение алгоритма Флойда – Уоршалла для поиска кратчайших путей Пусть матрица G ( l ) представляет собой граф кратчайших путей, проходящих через промежуточные вершины с номерами от 0 до l -1. То есть в матрице G ( l ) в ячейке (u,v) находится длина кратчайшего пути из u в v, если он существовал, проходящий только через вершины из множества {0,… l -1}, u и v в это множество не входят. Если пути из u в v не было, то в соответствующей ячейке матрицы будет значение. G ( l+1 ) [u,v] = min(G ( l ) [u,l] + G ( l ) [l,v], G ( l ) [u,v]) uv {0,1,… l -1 } l public static double[][] minPathsMatrix (double[][] G) { int n = G.length; for (int l = 0; l < n; l++) { // Формирование матрицы G(l+1): for (int u = 0; u < n; u++) { if (G[u][l] < Double.MAX_VALUE) { for (int v = 0; v < n; v++) { if (G[l][v] < Double.MAX_VALUE) G[u][v] = Math.min(G[u][l] + G[l][v], G[u][v]); } return G; }

28 Применение алгоритма Флойда – Уоршалла для поиска кратчайших путей Помимо длин путей необходимо найти еще и матрицу направлений (аналог дерева предшествования для случая поиска путей из одной вершины). P [u,v] = p, где p – первая вершина на кратчайшем пути из u в v. Находим последовательность P (0), P (1),… P (n). P (0) [u,v] = v, если G [u,v] < и не определено, если G [u,v] =. P ( l +1) [u,v] = P ( l ) [u,v], если не было коррекции кратчайшего пути. P ( l +1) [u,v] = P ( l ) [u, l ], если была коррекция кратчайшего пути. public static int[][] minPathsMatrix (double[][] G) { int n = G.length; int P[][] = new int[n][n]; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) { if (G[i][j] < Double.MAX_VALUE) P[i][j] = j; } for (int l = 0; l < n; l++) { // Формирование матриц G(l+1), P(l+1): for (int u = 0; u < n; u++) { if (G[u][l] < Double.MAX_VALUE) { for (int v = 0; v < n; v++) { if (G[l][v] < Double.MAX_VALUE) { if (G[u][l] + G[l][v] < G[u][v]) { G[u][v] = G[u][l] + G[l][v]; P[u][v] = P[u][l]; } } } } } } return P; }

29 Построение минимального скелета нагруженного графа. Алгоритм Прима Запускаем алгоритм обхода графа, начиная с произвольной вершины. В качестве контейнера выбираем очередь с приоритетами. Приоритет – текущая величина найденного расстояния до уже построенной части опорного дерева. Релаксации (как в Алгоритме Дейкстры) подвергаются прямые и обратные ребра n π 0 d В результате работы получили список ребер опорного дерева (скелета) вместе с нагрузками на все ребра.

30 Построение минимального скелета нагруженного графа. Алгоритм Крускала Строим список ребер, упорядоченный по возрастанию нагрузки Строим лес из изолированных вершин 3.Добавляем ребра по порядку, следя за тем, чтобы концы ребер лежали в разных деревьях