الكونت ديغرافس منفصلة

Question

لدي boolean[][] 2د-مجموعة تسمى matrix, ، الذي يشفر رسما بيانيا موجها بحيث إذا matrix[i][j] == true, ، ثم فيرتكس j متصل إلى قمة الرأس i (العكس ليس صحيحا بالضرورة).
أحاول إنشاء طريقة جافا التي ستحدد عدد الرسوم البيانية الموجهة منفصلة لدي.

لذلك من أجل مثال, ، إذا كان الرأس 0 متصلا بالرأس 1 ، وكان الرأس 2 متصلا بالرأس 3 (<code>[{{0,0,0,0},{1,0,0,0},{0,0,0,0},{0,0,1,0}}]</code> would be the 2D array), ، وأود أن يكون 2 ديغرافس منفصلة.

إذا لم تكن هناك اتصالات ، فإن عدد الرسوم البيانية المنفصلة يساوي عدد الرؤوس.

Answer 1

ابدأ بقائمة بجميع العقد في الشجرة.النظر في هذه العقد غير المرغوب فيها.

ثم كرر العملية التالية حتى تختفي قائمة العقد غير المرغوب فيها.

1. قم بإنشاء مجموعة فارغة ، "مجموعة العقدة" ، لتمثيل العقد التي تعيش في الرسم البياني للعقدة الحالية.
2. قم بإجراء بحث يبدأ من العقدة الحالية.لكل عقدة تصادفها في البحث ، قم بإزالتها من قائمة العقدة غير المرغوب فيها ، ثم:(1) إذا كانت العقدة موجودة بالفعل في مجموعة عقدة أخرى ، فقم بدمج مجموعة العقدة الحالية ومجموعة العقدة الأخرى وإيقاف البحث من تلك العقدة ، أو (2) إذا كانت هذه العقدة موجودة بالفعل في مجموعة العقدة الحالية ، أوقف البحث من تلك العقدة ، أو (3) إذا لم تر تلك العقدة من قبل ، فأضفها إلى مجموعة العقدة الحالية.

بمجرد اكتمال هذه العملية ، تتوافق مجموعات العقدة مع العقد الموجودة بشكل فريد في كل رسم بياني منفصل ، وبالتالي فإن عدد مجموعات العقدة هو القيمة التي تبحث عنها.

Answer 2

يبدو أنك لا تحتاج إلى اتصال قوي ، لذلك خوارزمية فعالة جدا ل غابات منفصلة سوف تقوم بهذه المهمة.بعد مرحلة الاتحاد ، سيكون عليك فقط حساب العقد مع الوالد = الذات

سكرتير خاص. سيدجويك ليكشن حول هذا الموضوع

Answer 3

public int countDisjointSubgraphs() {
    int len = matrix.length;
    int[] nodes = new int[len];
    for (int i = 0 ; i < len ; i++) nodes[i] = i;
    for (int i = 0 ; i < len ; i++) {
        for (int j = 0 ; j < len ; j++) {
            if (matrix[i][j] || matrix[j][i])
                for (int k = 0 ; k < len ; k++)
                    if (nodes[k] == nodes[i]) nodes[k] = j;
        }
    }
    ArrayList<Integer> list = new ArrayList<Integer>();
    for (int i : nodes)
        if (list.indexOf(i) < 0) list.add(i);
    return list.size();
}