Проблема непересекающихся множеств

Я пытаюсь написать реализацию алгоритма Крускала с использованием непересекающихся наборов. Я думаю, что у меня это почти работает, но я не могу заставить часть кода работать правильно. Код должен проверить, находится ли узел на графе уже в наборе, к которому он пытается быть добавлен; в противном случае вы не хотите его добавлять. Вот код, который я использую:

public static boolean difSets(int index1, int index2, ArrayList<Node> sets[], Node nodes[])
{
    int setnum1 = 0;
    int setnum2 = 0;
    for(int i = 0; i < nodes.length; i++)
    {
        for(int j = 0; j < sets[i].size(); j++)
        {
            if(nodes[index1].getX() == sets[i].get(j).getX() && nodes[index1].getY() == sets[i].get(j).getY());
                setnum1 = i;
            if(nodes[index2].getX() == sets[i].get(j).getX() && nodes[index2].getY() == sets[i].get(j).getY());
                setnum2 = i;
        }
    }
    if(setnum1 == setnum2)
        return false;
    else
        return true;
}

Небольшая информация: этот метод определяет, находятся ли два узла уже в одном наборе. Массив узлов содержит все точки на графике (узел — это класс, который просто хранит значения x и y и может их извлекать. Наборы — это массив списков массивов узлов. В начале задачи каждый узел будет в сам по себе ArrayList, к концу все они должны быть в одном и том же ArrayList.Индексы 1 и 2 соответствуют узлу в массиве Nodes.

К сожалению, этот код не дает мне правильного результата; Я смотрел на это больше часа и не могу понять, в чем проблема, поэтому я надеялся, что кто-то здесь может мне помочь.

Заранее спасибо.


java disjoint-sets kruskals-algorithm
person gmaster    schedule 08.02.2013    source источник
comment
Вероятно, я бы реорганизовал это, чтобы использовать docs.oracle.com /javase/6/docs/api/java/util/Set.html   -  person Luis    schedule 08.02.2013
comment
Из вашего кода я понимаю, что длина массива узлов всегда такая же, как у одного из массивов наборов. Что произойдет, когда вы начнете объединять наборы, разве это не должно уменьшить размер массива наборов?   -  person Bogdan    schedule 08.02.2013
comment
Я просто оставил нулевые наборы в пробелах, а не уменьшил их. Циклы просто игнорировали это, потому что .size() возвращал 0. Оглядываясь назад, можно сказать, что это, вероятно, было слишком сложной реализацией непересекающихся множеств.   -  person gmaster    schedule 12.02.2013

Ответы (1)


arrow_upward
0
arrow_downward

Решил это. Одна из многих вещей в java, которая просто не имеет для меня никакого смысла.

public static boolean difSets(int index1, int index2, ArrayList<Node> sets[], Node nodes[])
{
    int setnum1 = 0;
    int setnum2 = 0;
    int x1 = nodes[index1].getX();
    int y1 = nodes[index1].getY();
    int x2 = nodes[index2].getX();
    int y2 = nodes[index2].getY();
    for(int i = 0; i < nodes.length; i++)
    {
        for(int j = 0; j < sets[i].size(); j++)
        {
            int x3 = sets[i].get(j).getX();
            int y3 = sets[i].get(j).getY();
            if(x1 == x3 && y1 == y3)
                setnum1 = i;
            if(x2 == x3 && y2 == y3)
                setnum2 = i;
        }
    }
    if(setnum1 == setnum2)
        return false;
    else
        return true;
}

По сути, это должно быть точно так же, как у меня было раньше. Тем не менее...

person gmaster    schedule 08.02.2013
comment
Я не знаю, как выглядит ваш класс Node, но я предполагаю, что getX() и getY() возвращают Integers. Если это так, то == в строках 9 и 11 проверяет равенство ссылок, а не равенство значений. В этом случае вы могли бы вместо этого использовать метод equals или, как вы сделали в этом решении, распаковать по крайней мере одно значение в каждом сравнении с int. - person Jakob; 16.06.2017