представление списка смежности ориентированного графа

Оба равны O(m + n), где m — количество ребер, а n — количество вершин.

Запустите набор счетчиков, по одному для каждой вершины, один для степени входа и один для степени выхода.

Сканируйте края. Для исходящей вершины каждого ребра добавьте единицу к счетчику исходящих степеней для этой вершины. Для входной вершины каждого ребра добавьте единицу к счетчику входящих градусов для этой вершины. Это O(m) операция.

Выведите счетчики исходящих и входящих степеней для каждой вершины, которая равна O(n).

Вот как вы получаете O(m + n).

Представление ориентированного графа в виде списка смежности:

Исходящая степень каждой вершины

1. Степень исхода графа вершины u равна длине Adj[u].

2. Сумма длин всех списков смежности в Adj равна |E|.

3. Таким образом, время вычисления исходящей степени каждой вершины равно Θ(V + E).

In-степень каждой вершины

1. Входящая степень вершины u равна количеству раз, которое она появляется во всех списках Adj.

2. Если мы проведем поиск по всем спискам для каждой вершины, время для вычисления степени вхождения каждой вершины составит Θ(VE).

3. В качестве альтернативы мы можем выделить массив T размера |V| и инициализировать его записи нулем.

4. Нам нужно просмотреть списки в Adj только один раз, увеличивая T[u], когда мы видим 'u' в списках.

5. Значения в T будут входными степенями каждой вершины.

6. Это можно сделать за время Θ(V + E) с дополнительным хранилищем Θ(V).

out-degree за каждые vertex:theta(E)

in-degree за каждый vertex:O(E)

E - количество ребер графа

Так как это ориентированный граф, и дан только список смежности.

Время, затрачиваемое на подсчет количества исходящих степеней, будет равно тета (M+N), где M — количество вершин, а N — количество ребер.

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

Однако, если вы поддерживаете массив размера M, вы можете выполнить подсчет степени в тета (M + N) с дополнительным пространством для хранения тета (M)

Вычисление как входной, так и исходящей степени требует тета (m + n) для графа с m вершинами и n ребрами. Причина в том, что это тета (m + n), а не O (m + n), потому что каким бы ни был граф, он должен проходить через каждую вершину m и каждое ребро n.

Для заданного представления списка смежности Adj ориентированного графа исходящая степень вершины u равна длине Adj[u], а сумма длин всех списков смежности в Adj равна |E|. Таким образом, время вычисления исходящей степени каждой вершины равно Θ(|V| + |E|).

Входящая степень вершины u равна количеству раз, которое она появляется во всех списках Adj. Если мы просматриваем все списки для каждой вершины, время для вычисления степени вхождения каждой вершины равно Θ(|V|.|E|).

(В качестве альтернативы мы можем выделить массив T размером |V| и инициализировать его элементы нулем. Тогда нам нужно только один раз просмотреть списки в Adj, увеличивая T[u], когда мы видим u в списках. Значения в T будет степенью вхождения каждой вершины. Это можно сделать за время Θ(|V| + |E|) с дополнительной памятью Θ(|V|).)