самый эффективный алгоритм для установки двойного указателя

В представлении списка смежности неориентированного простого графа G = (V, E) каждое ребро (u, v) имеет две записи списка смежности: [v] в списке смежности u и [u] в списке смежности графа v. Их называют близнецами друг друга. Двойной указатель — это указатель из записи списка смежности на его двойник. Если |Е| = m и |V| = n, и размер памяти не является ограничением, какова временная сложность наиболее эффективного алгоритма для установки двойного указателя в каждой записи в каждом списке смежности?

  1. Θ(n^2)
  2. Θ(m+n)
  3. Θ(m^2)
  4. Θ(n^4)

Моя попытка:

Официальный ответ дан Θ(m+n). Двойные указатели можно настроить, отслеживая родительский узел в BFS или DFS графа.

Можете ли вы дать наиболее эффективный алгоритм для установки двойного указателя в каждой записи в каждом списке смежности?


c algorithm pointers time-complexity adjacency-list
person Community    schedule 03.03.2016    source источник
comment
Вы имеете в виду следующее: изначально списки смежности даны с неинициализированными двойными указателями - какова сложность времени для инициализации двойных указателей?   -  person Codor    schedule 03.03.2016
comment
@Codor, Можете ли вы дать алгоритм, как он задал вопрос. ИМО: это согласно BFS или DFS, верно?   -  person    schedule 03.03.2016
comment
Да, я так думаю, тогда должно быть Θ(m+n) (т.е. линейное время).   -  person Codor    schedule 03.03.2016

Ответы (2)


arrow_upward
0
arrow_downward

Поскольку память здесь не является ограничением, сначала мы создадим структуру данных для хранения адресов записей смежности для каждого списка смежности. Для более быстрого поиска мы создадим двумерный массив указателей размера (n2), которые будут указывать на записи смежности в графе. Если между u и v есть ребро, то наша структура данных A[u][v] содержит адрес элемента смежности v в списке смежности u. В противном случае он может быть NULL. Для более четкого изображения обратитесь к изображению, приведенному ниже.

person ajay kumar sah    schedule 15.01.2017
comment
см. изображение ниже Какое изображение? - person Donald Duck; 15.01.2017

arrow_upward
0
arrow_downward

Для представления графа, если мы используем матрицу, то временная сложность наиболее эффективного алгоритма для установки двойного указателя будет O(n2). Теперь, если мы используем список смежности, это будет:

2(Edges + Vertices) = 2(m+n) = O(m+n).

Поэтому вариант (B) является правильным ответом.

person aditya upadhyay    schedule 28.09.2020