Что возвращает (pset[i]==i)? я:(PSET [I]=findSet(PSET [I])); имею в виду?

Question

Я реализую алгоритм Крускала, и я нашел этот код:

   int findSet(int i)
   {
    return (pset[i]==i)? i:(pset[i]=findSet(pset[i]));
   }

и я не знаю, что на самом деле значит любая помощь, пожалуйста?:)

Answer 1

?:является условным оператором в C++. Это эквивалентно if-then-else заявление. Так что этот код эквивалентен:

int findSet(int i)
{
    if (pset[i]==i)
    { 
        return i;
    }
    else
    {
        pset[i]=findSet(pset[i]));
        return pset[i];
    }
}

В алгоритме Крускала он находит множество, представляющее его аргумент (т. Е. Корень дерева предков).

Answer 2

Я думаю, что троичный оператор (?:) сбивает вас с толку, давайте заменим его на if-else

int findSet(int i)
{
  if (pset[i]==i)
    return i;
  else 
  {
    pset[i]=findSet(pset[i]);
    return pset[i];
  }      
}

Надеюсь, теперь это более понятно для вас.

Answer 3

Похоже, реализация алгоритма поиска объединения (метод find).

Например, pset - это массив с индексами родителей, например: pset[] = { 0, 2, 3, 0 }

Итак, мы знаем, что родитель индекса 1 (pset 1) равен 2, родитель 2 равен 3, родитель 3 равен 0, а 0 является корнем (потому что parent[0] == 0, более общий parent[i] == i). Алгоритм find(i) всегда возвращает значение корня, поэтому в этом примере всегда 0. В этом алгоритме, когда мы находим корень, тогда (pset[i]==i) ? i Значение true, и я возвращаюсь, в противном случае мы просматриваем структуру путем выполнения:

pset[i]=findSet(pset[i]));

Назначение - ускорить поиск следующего запроса (i); Прочитайте некоторые статьи о непересекающейся структуре данных множества.