В математике, информатика и цифровая электроника, граф зависимостей - это ориентированный граф, представляющий зависимости нескольких объектов друг от друга. Из графа зависимостей можно вывести порядок оценки или отсутствие порядка оценки, учитывающего заданные зависимости.
Для данного набора объектов и транзитивное отношение с моделирование зависимости «a зависит от b» («a сначала нужно оценить b»), граф зависимостей - это граф с и T является переходным сокращением R.
Например, предположим, что это простой калькулятор. Этот калькулятор поддерживает присвоение постоянных значений переменным и присвоение суммы ровно двух переменных третьей переменной. Учитывая несколько уравнений, например «A = B + C; B = 5 + D; C = 4; D = 2;», тогда и . Вы можете вывести это отношение напрямую: A зависит от B и C, потому что вы можете добавить две переменные тогда и только тогда, когда вам известны значения обеих переменных. Таким образом, B необходимо рассчитать до того, как можно будет рассчитать A. Однако значения C и D известны сразу, потому что они числовые литералы.
В графе зависимостей циклы зависимостей (также называемые циклическими зависимостями ) приводят к ситуации, в которой не существует допустимого порядка оценки, потому что нет объектов в цикле могут быть оценены в первую очередь. Если граф зависимостей не имеет циклических зависимостей, он формирует направленный ациклический граф, и порядок оценки может быть найден с помощью топологической сортировки. Большинство алгоритмов топологической сортировки также способны обнаруживать циклы на своих входах; однако может быть желательно выполнить обнаружение цикла отдельно от топологической сортировки, чтобы обеспечить соответствующую обработку обнаруженных циклов.
Предположим, простой калькулятор из прошлого. Система уравнений «A = B; B = D + C; C = D + A; D = 12;» содержит циклическую зависимость, образованную A, B и C, так как B должен быть оценен до A, C должен быть оценен до B, а A должен быть оценен до C.
A правильный порядок оценки - это нумерация объектов, образующих узлы зависимости. график так, чтобы выполнялось следующее уравнение:
Может быть более одного правильного порядка оценки. Фактически, правильная нумерация - это топологический порядок, а любой топологический порядок - это правильная нумерация. Таким образом, любой алгоритм, который выводит правильный топологический порядок, получает правильный порядок оценки.
Снова представьте себе простой калькулятор сверху. Учитывая систему уравнений «A = B + C; B = 5 + D; C = 4; D = 2;», правильным порядком оценки будет (D, C, B, A). Однако (C, D, B, A) также является правильным порядком оценки.
Графы зависимостей используются в:
Зависимость графики являются одним из аспектов: