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

5 января 2024 г.

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

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

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

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

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

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

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

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

Алгоритм:

1) Исследуем все вершины, примыкающие к корню (на расстоянии k от корня. Сам корень обозначается s (source — «источник»));
2) Исследуем все вершины, смежные с соседями корня, которые еще не были исследованы (на расстоянии k + 1) и т.д.

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

Время выполнения - O(n + m).

инициализация трех свойств (упомянутых выше) - постоянное время для каждой вершины. В сумме - O(n).
каждая вершина добавляется в очередь, удаляется из очереди, и каждое из свойств изменяется не более одного раза — каждая из операций O(1) времени, в сумме O(n).
перебираем всех соседей каждой вершины, чтобы проверить, отмечены ли они - O(m)

Место в памяти - O(n + m)

хранения графа - n + m места в памяти,
очередь занимает O(n) места

По отношению к размеру входных данных работает за линейное время.

pseudocode

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

Реализация на 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	bfs(startVertex, callback) {
26		let list = this.vertices; // список смежности
27		let queue = [startVertex]; // очередь вершин для перебора
28		let visited = { [startVertex]: 1 }; // посещенные вершины
29
30		function handleVertex(vertex) {
31			// вызываем коллбэк для посещенной вершины
32			callback(vertex);
33
34			// получаем список смежных вершин
35			let neighboursList = list[vertex];
36
37			neighboursList.forEach((neighbour) => {
38				if (!visited[neighbour]) {
39					visited[neighbour] = 1;
40					queue.push(neighbour);
41				}
42			});
43		}
44
45		// перебираем вершины из очереди, пока она не опустеет
46		while (queue.length) {
47			let activeVertex = queue.shift();
48			handleVertex(activeVertex);
49		}
50
51		queue = Object.keys(this.vertices);
52
53		// Повторяем цикл для незатронутых вершин
54		while (queue.length) {
55			let activeVertex = queue.shift();
56			if (!visited[activeVertex]) {
57				visited[activeVertex] = 1;
58				handleVertex(activeVertex);
59			}
60		}
61	}
62}
63
64const graph = new Graph();
65
66graph.addVertex("A");
67graph.addVertex("B");
68graph.addVertex("C");
69graph.addVertex("D");
70graph.addVertex("E");
71graph.addVertex("F");
72graph.addVertex("G");
73graph.addVertex("H");
74
75graph.addEdge("A", "B");
76graph.addEdge("A", "C");
77graph.addEdge("C", "D");
78graph.addEdge("C", "E");
79graph.addEdge("A", "F");
80graph.addEdge("F", "G");
81
82graph.bfs('A', v => console.log(v));
83
84// A
85// B
86// C
87// F
88// D
89// E
90// G
91// H

Пример для реализации дерева.

JavaScript

1// Возьмем простой пример реализации очереди.
2class Queue {
3	constructor() {
4		this.arr = [];
5	}
6	enqueue(value) {
7		this.arr.push(value);
8	}
9	dequeue() {
10		return this.arr.shift();
11	}
12	isEmpty() {
13		return this.arr.length == 0;
14	}
15}
16
17class BinaryTreeNode {
18	constructor(value) {
19		this.left = null;
20		this.right = null;
21		this.parent = null;
22		this.value = value;
23	}
24
25	get height() {
26		let leftHeight = this.left ? this.left.height + 1 : 0;
27		let rightHeight = this.right ? this.right.height + 1 : 0;
28		return Math.max(leftHeight, rightHeight);
29	}
30
31	//При вставке важно обновить все затронутые ссылки: left или right для родительского узла и parent для дочернего. Если у родителя уже был потомок, его свойство parent нужно обнулить.
32
33	setLeft(node) {
34		if (this.left) {
35			this.left.parent = null;
36		}
37		if (node) {
38			this.left = node;
39			this.left.parent = this;
40		}
41	}
42
43	setRight(node) {
44		if (this.right) {
45			this.right.parent = null;
46		}
47		if (node) {
48			this.right = node;
49			this.right.parent = this;
50		}
51	}
52}
53
54function traverseBF(root, callback) {
55	let nodeQueue = new Queue();
56	nodeQueue.enqueue(root);
57
58	while (!nodeQueue.isEmpty()) {
59		let currentNode = nodeQueue.dequeue();
60
61		// Вызываем коллбэк для самого узла
62		callback(currentNode);
63
64		// Добавляем в очередь левого потомка
65		if (currentNode.left) {
66			nodeQueue.enqueue(currentNode.left);
67		}
68
69		// Добавляем в очередь правого потомка
70		if (currentNode.right) {
71			nodeQueue.enqueue(currentNode.right);
72		}
73	}
74}
75
76let aNode = new BinaryTreeNode('a');
77
78let bNode = new BinaryTreeNode('b');
79aNode.setLeft(bNode);
80
81let cNode = new BinaryTreeNode('c');
82aNode.setRight(cNode);
83
84let dNode = new BinaryTreeNode('d');
85bNode.setRight(dNode);
86
87let eNode = new BinaryTreeNode('e');
88cNode.setLeft(eNode);
89
90let fNode = new BinaryTreeNode('f');
91cNode.setRight(fNode);
92
93traverseBF(aNode, (node) => console.log(node.value));
94
95// a
96// b
97// c
98// d
99// e
100// f

Применение поиска в ширину

Полезен для всех задач, где нужен поиск кратчайших путей.

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

Примеры задач

Навигационные системы

Задача построения маршрутов с помощью GPS.

Если картографическая система хранит данные о локальной области в виде графа, вершины которого - адреса (или пересечения), а ребра — улицы (или, точнее, короткие отрезки улиц), то она может выполнять поиск в ширину для дерева, источник которого — ваше текущее местоположение.

Проверка, является ли граф двудольным

Граф не двудольный - если существует ребро между данной вершиной и уже отмеченной вершиной, расстояние которой либо такое же, либо меньше в степени 2. Этим вершинам будет присвоен один и тот же цвет.

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

Двудо́льный граф или бигра́ф в теории графов — это граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет вершину из одной части с какой-то вершиной другой части, то есть не существует рёбер между вершинами одной и той же части графа

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