c++ - 返回什么 (pset[i]==i)？i:(pset[i]=findSet(pset[i])); 意思是？

Question

我正在实现 Kruskal 算法，我发现了这段代码：

   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];
    }
}

在 Kruskal 的算法中，这找到了代表其参数的集合（即其祖先树的根）

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

它看起来像查找联合算法实现（查找方法）。

例如 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则为真并返回 i，否则我们通过执行遍历结构：

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

任务是加快下一个查询 find(i); 阅读一些关于不相交集数据结构的文章。