Поиск в глубину. Алгоритмы графов.

19 января 2024 г.

Это краткий дополненный конспект части о поиске в ширину в книге Гид по Computer Science, Вильям Спрингер.

Основная информация

Алгоритм поиска в глубину (Deep First Search, DFS) превращает произвольный граф в дерево поиска.

1) назначаем одну из вершин графа корнем дерева
2) рекурсивно исследуем ребра каждой вершины, пока все вершины графа (любая вершина, которой можно достичь, переходя по ребрам от корня; в случае связного графа это будут все вершины) не будут добавлены в остовное дерево (дерево, которое содержит все вершины графа).

При анализе времени выполнения алгоритмов на графах обычно используются две системы обозначений:

1) обозначение числа вершин n, а числа ребер — m.

2) указать размеры множеств вершин и ребер.

Например, Для графа G множество вершин обозначается как V(G) [читается «вершины G»), а множество ребер — как E(G) (читается «ребра G»), поэтому n = |V(G)| (можно прочитать как «размер множества вершин G»), а m = |E(G)|. Если G подразумевается по умолчанию, то можно обращаться к множествам просто как V и E.

Алгоритм:

1) Начиная с исходной вершины рекурсивно исследуем один путь (ветку) до конца
2) Переходим на другой путь (на другую ветку) и тд.

Если область поиска слишком велика или бесконечна, выполняем поиск до указанной глубины.

1) создаем Стек, в котором храним посещенные вершины.
2) помещаем в стек стартовую вершину.
3) Берем вершину с конца стека и получаем все ее смежные вершины.
4) Игнорируем посещенные вершины
5) Остальные отмечем как посещенные и добавляем в стек и возвращаемся к пункту 3.

pseudocode

1// Входные данные: произвольный граф, корнем которого выбрана одна вершина, и все вершин имеют такие свойства:
2// distance (расстояние) - изначально === 0
3// marked (помечена) - изначально === false
4
5// Выходные данные: остовное дерево графа.
6
7begin 
8	let stack = [];
9	stack.push(s);
10	while stack.length > 0 do
11		let activeVertex = stack.pop(s);
12		if activeVertex.marked then
13			continue
14		end
15		activeVertex.marked = true;
16		foreach v in Adj[activeVertex] do
17			if v.marked then
18				continue
19			end
20			v.parent =  activeVertex;
21			stack.push(v);
22		end
23	end
24end
25
26//где Adj - граф, представленный в виде списка смежности.
27//s - исходная вершина.

Реализация на JavaScript

Пример реализации взят с этого сайта.

JavaScript

1class Graph {
2	constructor() {
3		this.vertices = {}; // список смежности графа
4	}
5
6	addVertex(value) {
7		if (!this.vertices[value]) {
8			this.vertices[value] = [];
9		}
10	}
11
12	addEdge(vertex1, vertex2) {
13		if (!(vertex1 in this.vertices) || !(vertex2 in this.vertices)) {
14			throw new Error("В графе нет таких вершин");
15		}
16
17		if (!this.vertices[vertex1].includes(vertex2)) {
18			this.vertices[vertex1].push(vertex2);
19		}
20		if (!this.vertices[vertex2].includes(vertex1)) {
21			this.vertices[vertex2].push(vertex1);
22		}
23	}
24
25	dfs(startVertex, callback) {
26		let list = this.vertices; // список смежности
27		let stack = [startVertex]; // стек вершин для перебора
28		// Для хранения посещенных вершин используем объект, так как в нем проще проверить наличие свойства.
29		let visited = { [startVertex]: 1 }; // посещенные вершины
30
31		function handleVertex(vertex) {
32			// вызываем коллбэк для посещенной вершины
33			callback(vertex);
34
35			// получаем список смежных вершин
36			// При добавлении смежных вершин в стек, используем метод reverse -добавляем их в обратном порядке,  для того, чтобы перебор веток происходил в том же порядке, в котором они были добавлены.
37			let reversedNeighboursList = [...list[vertex]].reverse();
38
39			reversedNeighboursList.forEach((neighbour) => {
40				if (!visited[neighbour]) {
41					// отмечаем вершину как посещенную
42					visited[neighbour] = 1;
43					// добавляем в стек
44					stack.push(neighbour);
45				}
46			});
47		}
48
49		// перебираем вершины из стека, пока он не опустеет
50		while (stack.length) {
51			let activeVertex = stack.pop();
52			handleVertex(activeVertex);
53		}
54
55		// проверка на изолированные фрагменты
56		//  Если в графе могут быть изолированные вершины или подграфы. Непосещенные вершины обрабатываем. Если их нет, то эту часть можно опустить.
57		stack = Object.keys(this.vertices);
58
59		while (stack.length) {
60			let activeVertex = stack.pop();
61			if (!visited[activeVertex]) {
62				visited[activeVertex] = 1;
63				handleVertex(activeVertex);
64			}
65		}
66	}
67}

Задача кратчайшего пути

Задача кратчайшего пути: Найти маршрут между двумя вершинами, имеющий наименьший вес.

В невзвешенном графе - путь с наименьшим количеством ребер.

Во взвешенном графе - путь с наименьшим суммарным весом ребер.

Взвешенные графы - каждому ребру присвоен вес. Чаще это неотрицательные целые числа. Вес - стоимость использования ребра.

Вариации задачи.

Кратчайший путь из одной вершины. Найти кратчайший путь от исходного узла ко всем остальным узлам графа. Пример: узнать кратчайший путь от пожарной части до каждой точки города.
Кратчайший путь в заданный пункт назначения. Найти кратчайший путь от каждого узла графа до данной точки назначения. Это просто задача поиска кратчайшего пути из одной вершины, для которой направление всех ребер изменено на противоположное. Например, мы можем захотеть узнать кратчайший путь до больницы из любой точки города.
Кратчайший путь между всеми парами вершин. Найти кратчайший путь между всеми парами узлов графа. В идеале наш GPS сможет построить наилучший маршрут из любой точки в любую точку.

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

1) Определяем множество вершин S, изначально пустое. Оно будет хранить вершины, расстояние до которых определено.

2) Добавляем все элементы графа в очередь с приоритетом на основе их расстояния от исходной вершины s. Сначала для s расстояние равно 0, для остальных узлов - бесконечность.

3) Удаляем из очереди наименьший элемент (первоначально s) и "ослабляем" все его ребра.

4) Продолжаем удалять наименьшие элементы и "ослаблять" ребра, пока очередь не пустая.

5) Каждому узлу присваивается длина его кратчайшего пути.

pseudocode

1// Входные данные: Граф G и исходная вершина s
2// Выходные данные: Расстояние от s до любого другого узла графа G
3// Инвариантное: S - множество узлов, для которых определены кратчайшие пути
4
5// begin 
6	// Инициализировать множество вершина S нулем
7	let S = new Set()
8	// Инициализировать очередь с приоритетами Q и поместить в нее все вершины G
9	const Q
10	while Q.length > 0 do
11		let activeVertex = Q.ExtractMin();
12		S = S.union(S, {activeVertex})
13		forEach v in Adj(activeVertex) do
14			Relax(activeVertex, v, w)
15		end
16	end
17end
18
19//где Adj - граф, представленный в виде списка смежности.
20//s - исходная вершина.

"Ослабление" ребра в этом случае значит, что:

1) Берем приоритет текущего узла u, прибавляем к нему расстояние w до нового узла v и сравниваем сумму с текущим приоритетом.

2) Если сумма меньше нынешнего значения v.d - мы нашли более короткий путь к v и можем заменить старое значение.

3) Помечаем u как нового родителя v.

pseudocode | Ослабление ребра

1// Входные данные: Смежные вершины u и v и вес ребра w между ними
2// Выходные данные: v.d - вес найденного кратчайшего пути от s до v; Если путь проходитт через ребро от  u до v, 
3// то родительскому элементу v присванивается значение u
4
5begin 
6	if(v.d > u.d + w(u, v)) then
7		v.d = u.d + w(u,v)
8		v.parent = u
9	end
10end

Когда узел удаляется из очереди с приоритетом, мы знаем, что нашли кратчайший путь к этому узлу - любой более короткий путь должен был бы пройти через уже обработанные узлы.

Это жадный алгоритм, но алгоритм Дейкстры гарантировано возвращает оптимальное решение. Его сложность O(N^2).

"Ослабление ребра" - постоянное время. Для все ребер в сумме O(m).

Поиск элемента с наименьшим приоритетом O(n) и выполняется O(n) раз - в сумме O(N^2). Итого O(n2 + m), где m ≤ n2.

Пример на JavaScript

Пример алгоритма взят из этой статьи.

JavaScript

1function findNearestVertex(distances, visited) {
2	let minDistance = Infinity;
3	let nearestVertex = null;
4
5	Object.keys(distances).forEach((vertex) => {
6		if (!visited[vertex] && distances[vertex] < minDistance) {
7			minDistance = distances[vertex];
8			nearestVertex = vertex;
9		}
10	});
11
12	return nearestVertex;
13}
14
15function dijkstra(graph, startVertex) {
16	let visited = {};
17	let distances = {}; // кратчайшие пути из стартовой вершины
18	let previous = {}; // предыдущие вершины
19	let vertices = Object.keys(graph); // список вершин графа
20
21	// по умолчанию все расстояния неизвестны (бесконечны)
22	vertices.forEach((vertex) => {
23		distances[vertex] = Infinity;
24		previous[vertex] = null;
25	});
26
27	// расстояние до стартовой вершины равно 0
28	distances[startVertex] = 0;
29
30	function handleVertex(vertex) {
31		// расстояние до вершины
32		let activeVertexDistance = distances[vertex];
33		// смежные вершины (с расстоянием до них)
34		let neighbours = graph[activeVertex];
35		// для всех смежных вершин пересчитать расстояния
36		neighbours.forEach((item) => {
37			const neighbourVertex = item[0];
38			const neighbourWeight = item[1];
39			// известное на данный момент расстояние
40			let currentNeighbourDistance = distances[neighbourVertex];
41			// вычисленное расстояние
42			let newNeighbourDistance = activeVertexDistance + neighbourWeight;
43			if (newNeighbourDistance < currentNeighbourDistance) {
44				distances[neighbourVertex] = newNeighbourDistance;
45				previous[neighbourVertex] = vertex;
46			}
47		});
48
49		// пометить вершину как посещенную
50		visited[vertex] = 1;
51	}
52
53	// ищем самую близкую вершину из необработанных
54	let activeVertex = findNearestVertex(distances, visited);
55
56	// продолжаем цикл, пока остаются необработанные вершины
57	while (activeVertex) {
58		handleVertex(activeVertex);
59		activeVertex = findNearestVertex(distances, visited);
60	}
61
62	return { distances, previous };
63}

Создадим следующий граф и воспользуемся алгоритмом:

JavaScript

1class Graph {
2	constructor() {
3		this.vertices = {}; // список смежности графа
4	}
5
6	addVertex(value) {
7		if (!this.vertices[value]) {
8			this.vertices[value] = [];
9		}
10	}
11
12	addEdge(vertex1, vertex2, weight) {
13		if (!(vertex1 in this.vertices) || !(vertex2 in this.vertices)) {
14			throw new Error("В графе нет таких вершин");
15		}
16
17		if (!this.vertices[vertex1].includes(vertex2)) {
18			this.vertices[vertex1].push([vertex2, weight]);
19		}
20		if (!this.vertices[vertex2].includes(vertex1)) {
21			this.vertices[vertex2].push([vertex1, weight]);
22		}
23	}
24}
25
26const graph = new Graph();
27
28graph.addVertex("S");
29graph.addVertex("B");
30graph.addVertex("C");
31graph.addVertex("D");
32graph.addVertex("E");
33graph.addVertex("F");
34
35graph.addEdge("S", "B", 14);
36graph.addEdge("S", "D", 24);
37graph.addEdge("B", "C", 8);
38graph.addEdge("B", "F", 4);
39graph.addEdge("B", "E", 86);
40graph.addEdge("C", "D", 55);
41graph.addEdge("C", "F", 1);
42graph.addEdge("D", "E", 7);
43graph.addEdge("F", "E", 13);
44
45console.log(dijkstra(graph.vertices, "S"));
46// {
47//   distances: { S: 0, B: 14, C: 19, D: 24, E: 31, F: 18 },
48//   previous: { S: null, B: 'S', C: 'F', D: 'S', E: 'F', F: 'B' }
49// }

Поиск в глубину. Алгоритмы графов.

Основная информация

Алгоритм:

Реализация на JavaScript

Задача кратчайшего пути

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

Пример на JavaScript

Другие посты