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

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

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

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

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

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

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

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

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

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

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

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

Например, предположим, что у вас есть вычислительный конвейер, который можно настраивать во время выполнения. В качестве примера можно привести вычисления A,B,C,D,E,F и G, которые зависят друг от друга: A зависит от C, C зависит от E и F, B зависит от D и E, а D зависит от F. Это можно представить в виде DAG. После того, как у вас есть DAG в памяти, вы можете написать алгоритмы, чтобы:

• убедиться, что вычисления оцениваются в правильном порядке (топологическая сортировка)
• если вычисления могут выполняться параллельно, но каждое вычисление имеет максимальное время выполнения, вы можете вычислить максимальное время выполнения всего набора

среди многих других вещей.

Вне сферы прикладного программирования, любой приличный инструмент автоматической сборки (make, ant, scons и т.д.) будет использовать DAGs для обеспечения правильного порядка сборки компонентов программы.

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

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

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

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

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

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

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