Кто-то может объяснить простыми словами мне, каков направленный граф без петель?

Кто-то может объяснить простыми словами мне, каков направленный граф без петель? Я считал Википедию, но она действительно не заставляет меня видеть ее использование в программировании.

96
задан Mark Amery 29 September 2019 в 17:05
поделиться

6 ответов

граф = структура, состоящая из узлов, которые соединены друг с другом ребрами

, направленными = соединения между узлами (ребрами) имеют направление: A -> B не то же самое, что B -> A

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

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

165
ответ дан 24 November 2019 в 05:31
поделиться

В нескольких ответах были приведены примеры использования графиков (например, сетевое моделирование), и вы спросили: «При чем здесь программирование?».

Ответ на этот подвопрос заключается в том, что он не имеет ничего общего с программированием. Это связано с решением проблем.

Так же, как связанные списки - это структуры данных, используемые для определенных классов проблем, графы полезны для представления определенных отношений. Связанные списки, деревья, графики и другие абстрактные структуры связаны с программированием только в том смысле, что вы можете реализовать их в коде. Они существуют на более высоком уровне абстракции. Это не о программировании, а о применении структур данных для решения проблем.

14
ответ дан 24 November 2019 в 05:31
поделиться

Направленные ациклические графы (DAG) обладают следующими свойствами, которые отличают их от других графов:

  1. Их ребра показывают направление.
  2. У них нет циклов.

Что ж, сейчас я могу придумать одно применение - DAG (известный как Wait-For-Graphs - дополнительные технические подробности ) удобны при обнаружении тупиковых ситуаций, поскольку они иллюстрируют зависимости среди набора процессов и ресурсов (оба являются узлами в DAG). Взаимоблокировка может произойти при обнаружении цикла.

13
ответ дан 24 November 2019 в 05:31
поделиться

Направленный ациклический граф полезен, когда вы хотите представить ... ориентированный ациклический граф! Канонический пример - генеалогическое древо или генеалогия.

-5
ответ дан 24 November 2019 в 05:31
поделиться

Я полагаю, вы уже знаете базовую терминологию графов; в противном случае вам следует начать со статьи по теории графов .

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

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

Несколько приложений:

  • Таблицы; это объясняется в статье DAG .
  • Контроль версий : если вы посмотрите на диаграмму на этой странице, вы увидите, что эволюция кода с контролем версий является направленным (на этой диаграмме он идет «вниз») и ациклическим (никогда не возвращается "вверх").
  • Семейное древо: оно направленное (вы - ребенок ваших родителей, а не наоборот) и ациклическое (ваши предки никогда не могут быть вашим потомком).
11
ответ дан 24 November 2019 в 05:31
поделиться

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

4
ответ дан 24 November 2019 в 05:31
поделиться
Другие вопросы по тегам:

Похожие вопросы: