Nano Hash - криптовалюты, майнинг, программирование

проверка ориентированного графа на мосты

я ищу быстрый алгоритм, чтобы просто определить, содержит ли данный ориентированный граф мост или нет ...
не беспокоит расположение этого моста .. только то, содержит ли граф его или нет.

graph algorithm
14.10.2011

Ответы:


1

В случае ориентированного графа, аналогично мостам для неориентированного графа, мы называем ребро сильным мостом, если его удаление увеличивает количество сильносвязных компонент графа. Чтобы проверить, есть ли в ориентированном графе сильные мосты, вам нужно запустить алгоритм, подробно описанный в статье: Джузеппе Ф. Итальяно, Луиджи Лаура, Федерико Сантарони: Поиск сильных мостов и сильных точек сочленения за линейное время . Теор. вычисл. науч. 447: 74-84 (2012) http://dx.doi.org/10.1016/j.tcs.2011.11.011

14.06.2013

2

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

Запустите на графе алгоритм сильно связанных компонентов Tarjan . если результат отличается, то на вашем графике есть мост.

14.10.2011
  • я знаю об этом алгоритме ... но я подумал, что будет более простой способ сделать это, так как мне не нужно местоположение моста ... я просто хочу проверить, сильно ли он связан или нет ... 14.10.2011
  • @AhmadIbrahem Я считаю, что это самый быстрый способ сделать это: en.wikipedia.org/wiki/Strongly_connected_component 14.10.2011
  • @SaeedAmiri Если граф сильно связан, все ребра содержатся в цикле. 14.10.2011
  • Что если есть параллельные направленные ребра, не входящие ни в один цикл? Я не думаю, что эти ребра можно классифицировать как мост. 30.01.2021

    • 3

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

    22.12.2011
  • Да, но сложность этого O(E*E), тогда как это можно сделать за O(E) 25.11.2020
    • Новые материалы
    Кластеризация: более глубокий взгляд
    Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
    Как написать эффективное резюме
    Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
    Частный метод Python: улучшение инкапсуляции и безопасности
    Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
    Как я автоматизирую тестирование с помощью Jest
    Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
    Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
    Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
    Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
    В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
    Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
    В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..