Вычисление исходящего и входящего списка смежности

Вопрос

Рассчитайте временную сложность при расчете исходящей и входящей степени списка смежности.

Мой подход/сомнение

Пусть Adj[] будет массивом размера V, где V=No. вершин в ориентированном графе для представления списка смежности.

Я знаю это ,

Степень исхода вершины u (u принадлежит V) на самом деле является длиной Adj[u]

а также

Степень вершины u (u принадлежит V) на самом деле является количеством вершин u в списке Adj.

В обоих случаях я думаю, что временная сложность должна быть тета (V * E).

Где V=нет. вершин

  E=no. of edges

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

Тогда почему это Thrta (V+E)

Пожалуйста, поправьте меня, где я ошибаюсь?

Спасибо!


graph algorithm degrees
person laura    schedule 05.07.2017    source источник
comment
Проверьте этот ответ для вашего запроса, связанного с получением степени. stackoverflow.com/questions/22930344 /   -  person smasher    schedule 18.10.2017

Ответы (2)


arrow_upward
1
arrow_downward

Допустим, у нас есть V вершин и E ребер.
Как в двунаправленном, так и в однонаправленном графе для каждого ребра Ei мы получаем две вершины V1, V 2. Мы можем легко получить направление ребра и обновить счетчик исходящих и входящих степеней определенной вершины.

Пример:

Вершины: 1, 2, 3, 4
Ребра: 1 -> 2, 2 -> 4, 3 -> 1, 2 -> 3
Исходящая степень: 0 0 0 0
Входящая степень: 0 0 0 0

Проход 1:
Край 1 -> 2
Исходящая степень: 1 0 0 0
Входящая степень: 0 1 0 0

Проход 2:
Край 2 -> 4
Исходящая степень: 1 1 0 0
Входящая степень: 0 1 0 1

Проход 3:
Край 3 -> 1
Исходящая степень: 1 1 1 0
Входящая степень: 1 1 0 1

Проход 4:
Край 2 -> 3
Исходящая степень: 1 2 1 0
Входящая степень: 1 1 1 1

Итак, здесь нам нужно запустить цикл через каждое ребро и каждую вершину ровно один раз, что приведет к сложности (V + E).

person Community    schedule 05.07.2017

arrow_upward
0
arrow_downward

мы можем выделить массив arr[] размера |V| и инициализировать его записи нулем. Тогда нам нужно только один раз просмотреть списки в Adj, увеличивая значение arr [u], когда мы видим u в списках.

Значения в arr[] будут исходящими степенями каждой вершины. Это можно сделать за время Θ (|V| + |E|) с дополнительной памятью Θ (|V|).

person Rajinder    schedule 05.07.2017