Что возвращает (pset [i] == i)? я: (PSET [I] = findSet (PSET [I])); имею в виду?
Я реализую алгоритм Крускала, и я нашел этот код:
int findSet(int i)
{
return (pset[i]==i)? i:(pset[i]=findSet(pset[i]));
}
и я не знаю, что на самом деле значит любая помощь, пожалуйста? 🙂
Решение
?:это условный оператор в C ++. Это эквивалентно if-then-else заявление. Так что этот код эквивалентен:
int findSet(int i)
{
if (pset[i]==i)
{
return i;
}
else
{
pset[i]=findSet(pset[i]));
return pset[i];
}
}
В алгоритме Крускала это находит множество, представляющее его аргумент (то есть корень дерева предков).
Другие решения
Я думаю, что троичный оператор (? 🙂 сбивает вас с толку, давайте заменим его на if-else
int findSet(int i)
{
if (pset[i]==i)
return i;
else
{
pset[i]=findSet(pset[i]);
return pset[i];
}
}
Надеюсь, теперь это более понятно для вас.
Это выглядит как найти союз Реализация алгоритма (метод поиска).
Например
pset это массив с индексами родителей, например:
pset [] = {0, 2, 3, 0}
Итак, мы знаем, что родительский индекс индекса 1 (pset1) равен 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);
Прочитайте некоторые статьи о непересекающейся структуре данных множества.