數(shù)據(jù)結(jié)構(gòu)–并查集的進(jìn)一步優(yōu)化
Find操作的優(yōu)化(壓縮路徑)
壓縮路徑 ? ? F i n d 操作，先找到根節(jié)點(diǎn)，再將查找路徑上所有結(jié)點(diǎn)都掛到根結(jié)點(diǎn)下 \color{red}壓縮路徑 -- Find操作，先找到根節(jié)點(diǎn)，再將查找路徑上所有結(jié)點(diǎn)都掛到根結(jié)點(diǎn)下 壓縮路徑??Find操作，先找到根節(jié)點(diǎn)，再將查找路徑上所有結(jié)點(diǎn)都掛到根結(jié)點(diǎn)下文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-550205.html
int Find(int S[], int x)
{
return S[x] == x ? x : S[x] = Find(S, x);
}
每次Find操作，先找根，再“壓縮路徑”，可使樹的高度不超過(guò) O ( α ( n ) ) O(\alpha(n)) O(α(n))。 α ( n ) \alpha(n) α(n)是一個(gè)增長(zhǎng)很緩慢的函數(shù)，對(duì)于常見的n值，通常 α ( n ) ≤ 4 \alpha(n)≤4 α(n)≤4，因此優(yōu)化后并查集的Find、Union操作時(shí)間開銷都很低文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-550205.html
并查集的優(yōu)化
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)--并查集的進(jìn)一步優(yōu)化的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
