Union-Find، ساختارهای داده – انجمن DEV

Summarize this content to 400 words in Persian Lang

ساختار داده Union-Find

class UnionFind {
private:
vectorint> parent;
vectorint> rank;

public:
// Constructor to initialize Union-Find with n elements
UnionFind(int n) {
parent.resize(n);
rank.resize(n, 0);
for (int i = 0; i n; ++i) {
parent[i] = i; // Each element is its own parent initially
}
}

// Find the representative or root of the set containing ‘vertex’
int find(int vertex) {
if (parent[vertex] != vertex) {
parent[vertex] = find(parent[vertex]); // Path compression
}
return parent[vertex];
}

// Union the sets containing ‘u’ and ‘v’
void unite(int u, int v) {
int rootU = find(u);
int rootV = find(v);

if (rootU != rootV) {
// Union by rank
if (rank[rootU] > rank[rootV]) {
parent[rootV] = rootU;
} else if (rank[rootU] rank[rootV]) {
parent[rootU] = rootV;
} else {
parent[rootV] = rootU;
rank[rootU]++;
}
}
}
};

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

توضیح کلاس Union-Find

را اتحادیه-یافتن ساختار داده، همچنین به عنوان Disjoint Set Union (DSU) شناخته می شود، برای مدیریت و ادغام مجموعه های غیرمجاز به طور موثر استفاده می شود. این به ویژه در سناریوهای مربوط به اجزای متصل و تشخیص چرخه در نمودارها مفید است.

اجزای کلیدی

آرایه والد:

هدف: والد یا نماینده هر مجموعه را پیگیری می کند.

مقداردهی اولیه: هر عنصر در ابتدا والد خودش است.

عملیات را پیدا کنید: برای یافتن نماینده یک مجموعه حاوی یک عنصر خاص. این عملیات شامل فشرده‌سازی مسیر برای سریع‌تر کردن درخواست‌های آینده است.

آرایه رتبه:

هدف: برای پیگیری عمق درخت (یا رتبه) برای عملیات اتحادیه استفاده می شود. این به کم عمق نگه داشتن درخت کمک می کند و عملیات Find را بهینه می کند.

عملیات اتحادیه: برای ادغام دو مجموعه. ریشه مجموعه با رتبه بالاتر، والد ریشه مجموعه با رتبه پایین تر می شود. اگر رتبه ها مساوی باشند، یک ریشه والد دیگری می شود و رتبه آن افزایش می یابد.

عملیات

پیدا کردن:

تابع: find(int vertex)

جزئیات: نماینده مجموعه حاوی راس را برمی گرداند. فشرده سازی مسیر را برای ساختن آینده پیاده سازی می کند find عملیات سریعتر وقتی یک find عملیات انجام می شود، والد هر گره را در طول مسیر به روز می کند تا مستقیماً به ریشه اشاره کند، بنابراین ساختار را صاف می کند.

اتحاد. اتصال:

تابع: void unite(int u, int v)

جزئیات: مجموعه های حاوی دو عنصر مشخص شده را ادغام می کند. از اتحاد بر اساس رتبه برای حفظ تعادل درخت استفاده می کند. این به کارآمد نگه داشتن عملیات کمک می کند و پیچیدگی زمانی را کاهش می دهد.

موارد استفاده

اجزای متصل: برای تعیین و ادغام اجزای متصل در یک نمودار استفاده می شود.

تشخیص چرخه: در الگوریتم هایی مانند الگوریتم حداقل درخت پوشا Kruskal برای تشخیص چرخه ها مفید است.

ساختار Union-Find برای سناریوهایی کارآمد است که در آن شما نیاز به ادغام مکرر مجموعه ها و پرس و جوی نماینده هر مجموعه دارید. این به طور گسترده در اتصال به شبکه، پردازش تصویر و سایر زمینه هایی که اتصال پویا یک نگرانی کلیدی است استفاده می شود.

class UnionFind {
private:
    vectorint> parent;
    vectorint> rank;

public:
    // Constructor to initialize Union-Find with n elements
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i  n; ++i) {
            parent[i] = i; // Each element is its own parent initially
        }
    }

    // Find the representative or root of the set containing 'vertex'
    int find(int vertex) {
        if (parent[vertex] != vertex) {
            parent[vertex] = find(parent[vertex]); // Path compression
        }
        return parent[vertex];
    }

    // Union the sets containing 'u' and 'v'
    void unite(int u, int v) {
        int rootU = find(u);
        int rootV = find(v);

        if (rootU != rootV) {
            // Union by rank
            if (rank[rootU] > rank[rootV]) {
                parent[rootV] = rootU;
            } else if (rank[rootU]  rank[rootV]) {
                parent[rootU] = rootV;
            } else {
                parent[rootV] = rootU;
                rank[rootU]++;
            }
        }
    }
};