Мост
Описание
Мост (bridge) - это ребро, удаление которого увеличивает число компонент связности. Такие ребра также известны как разрезающие ребра (cut-edge), разрезающие дуги (cut arc) или перешейки (isthmus). Эквивалентное определение - ребро является мостом в том и только в том случае, если оно не содержится ни в одном цикле.
Граф с 6 мостами (выделены красным)
Неориентированный связный граф, не имеющий мостов
Деревья и леса
Граф с n вершинами может содержать не более n-1 мостов, поскольку добавление еще одного ребра неминуемо приведет к появлению цикла. Графы, имеющие в точности n-1 мостов, известны как деревья, а графы, в которых любое ребро является мостом - это леса.
Связь с вершинной связностью
Мосты тесно связаны с концепцией шарниров (см. предыдущий раздел) - вершин, которые входят в любой путь, соединяющий некоторые две вершины. Две конечные вершины моста являются шарнирами, если они не имеют степень 1, хотя ребра, не являющиеся мостами, тоже могут с обоих концов иметь шарниры. Аналогично графам без мостов, которые реберно двусвязны, графы без шарниров вершинно двусвязны.
Реализация
Существует несколько алгоритмов для поиска мостов в графе. В нашей реализации мы в очередной раз прибегнем с старому-доброму поиску в глубину:
// algorithms/graphs/bridges.js
import depthFirstSearch from './depth-first-search'
// Метаданные узла
class VisitMetadata {
constructor({ discoveryTime, lowDiscoveryTime }) {
// Время исследования
this.discoveryTime = discoveryTime
// Наименьшее время исследования
this.lowDiscoveryTime = lowDiscoveryTime
}
}
// Функция принимает граф
export default function graphBridges(graph) {
// Посещенные узлы
const visited = {}
// Мосты
const bridges = {}
// Время, необходимое для исследования текущего узла
// (измеряется в количестве посещений узлов)
let discoveryTime = 0
const startNode = graph.getAllNodes()[0]
// Обработчики для DFS
const callbacks = {
// Обработчик вхождения в узел
enterNode: ({ currentNode }) => {
// Увеличиваем время исследования
discoveryTime += 1
// Помещаем текущий узел в посещенные
visited[currentNode.getKey()] = new VisitMetadata({
discoveryTime,
lowDiscoveryTime: discoveryTime,
})
},
// Обработчик выхода из узла
leaveNode: ({ currentNode, previousNode }) => {
if (!previousNode) return
// Обновляем `lowDiscoveryTime` наименьшим временем соседних узлов
visited[currentNode.getKey()].lowDiscoveryTime = currentNode
.getNeighbors()
.filter((n) => n.getKey() !== previousNode.getKey())
.reduce((minTime, n) => {
const lowTime = visited[n.getKey()].lowDiscoveryTime
return lowTime < minTime ? lowTime : minTime
}, visited[currentNode.getKey()].lowDiscoveryTime)
// Сравниваем минимальное время исследования.
// Если текущее время меньше, чем время предыдущего узла,
// обновляем `lowDiscoveryTime` предыдущего узла
const currentLDT = visited[currentNode.getKey()].lowDiscoveryTime
const previousLDT = visited[previousNode.getKey()].lowDiscoveryTime
if (currentLDT < previousLDT) {
visited[previousNode.getKey()].lowDiscoveryTime = currentLDT
}
// Сравниваем текущее минимальное время исследования со временем предка.
// Проверяем наличие короткого пути.
// Если мы не можем добраться до текущего узла иначе, чем через предка,
// значит, ребро между текущим узлом и его предком является мостом
const parentLDT = visited[previousNode.getKey()].discoveryTime
if (parentLDT < currentLDT) {
const bridge = graph.findEdge(previousNode, currentNode)
bridges[bridge.getKey()] = bridge
}
},
// Обработчик определения допустимости обхода следующего узла
allowTraverse: ({ nextNode }) => {
// Запрещаем обход посещенных узлов
return !visited[nextNode.getKey()]
},
}
// Запускаем поиск в глубину
depthFirstSearch(graph, startNode, callbacks)
return bridges
}
Тесты
Запускаем тесты:
npm run test ./algorithms/graphs/__tests__/bridges
