Задача раскраски (с 2 цветами), где каждая вершина имеет определенную область и нахождение минимальной области, окрашенной с использованием DFS - PullRequest
Новая
       74

Задача раскраски (с 2 цветами), где каждая вершина имеет определенную область и нахождение минимальной области, окрашенной с использованием DFS

0 голосов
/ 19 апреля 2019

У меня есть список островов / областей, изначально белый.Все вершины, соединенные друг с другом 1 ребром, должны иметь противоположные цвета.(Либо черный, либо белый).Я хочу использовать минимальное количество черного для окраски островов. Каждый остров имеет свой размер, а индекс островов начинается с 1.

Я использовал DFS и глобальный объект для отслеживания как белых, так и черных областей, а затем дал мне минимумиз двух.Предполагая, что весь граф не связан и имеет несколько компонентов.Я сбросил глобальную переменную для каждого нового компонента.Я не получаю правильных ответов, и я понятия не имею, где ошибка в моей логике.(Я почти уверен, что мой метод DFSrec верен) 

    // this will be the DFS spanning tree for 1 component
    private void DFSrec(int v,
                        boolean[] visitedArr, int[] predecessorArr) {

        visitedArr[v] = true;
        if (islandsList.get(v).colour.equals("WHITE")) {
            p.whiteArea += islandsList.get(v).area;
        } else {
            p.blackArea += islandsList.get(v).area;
        }

        for (int neighbour : adjList.get(v)) {
            if (!visitedArr[neighbour]) {
                predecessorArr[neighbour] = v;

                if (islandsList.get(v).colour.equals("WHITE")) {
                    islandsList.get(neighbour).setColour("BLACK");
                } else {
                    islandsList.get(neighbour).setColour("WHITE");
                }

                DFSrec(neighbour, visitedArr, predecessorArr);
            }
        }
    }


    // covers all components
    private int DFS(boolean[] visitedArr, int[] predecessorArr, int numIslands){
        int minArea = 0;
        for (int v = 1; v <= numIslands; v++) {
            if ( !visitedArr[v] ) {
                DFSrec(v, visitedArr, predecessorArr);
                int minAreaOfComponent = p.minArea();
                minArea += minAreaOfComponent;
                p = new Pair();
            }
        }
        return minArea;
    }

1 Ответ

0 голосов
/ 19 апреля 2019

Хорошо, ответ DFS работает.

Я только что понял, что проблема возникла, потому что Я не добавил во ВСЕ ребра , потому что график не ориентирован. Если я добавлю ребро 2 -> 3 в список, мне нужно будет добавить также и 3 -> 2.

...