Я решал эту проблему с CLRS, которая просила выяснить неотвратность каждой вершины графа G(V,E). Я нашел решение O(|E|), так как нам нужно только сканировать все края, чтобы узнать степень всех вершин.Список пристрастий indegree
Но большинство решений, которые я нашел в Интернете, говорят, что это O(|V|+|E|). Как так? Каким образом вершины учитывают время?
Если мы предположим, что реализация орграфа использует объекты для вершин, и каждая вершина имеет связанный список преемников и никаких дополнительных структур данных, то будет невозможно выполнить итерацию ребер напрямую.
Если орграф подключен, то каждый vertext имеет как минимум один связанный ребро. Это означает, что итерация по краям через итерацию по вершинам занимает O(|E|). Итерация по вершинам не увеличивает время работы, в котором преобладает количество ребер.
Если диграф составляет не, то итерация по вершинам не обязательно будет определяться количеством ребер; даже отдельные вершины должны обрабатываться только для того, чтобы узнать, что у них нет связанных исходящих дуг, что можно сделать в O(|V|+|E|) времени.
В целом, граница времени выполнения O(|V|+|E|) верна в любом случае; однако для связанного орграфа (или реализации, которая допускает прямую итерацию по краям независимо от количества вершин), можно получить более узкую временную границу O(|E|).