Найти число связанных компонентов в неориентированном графе с помощью Union Find - PullRequest
Новая
       30

Найти число связанных компонентов в неориентированном графе с помощью Union Find

0 голосов
/ 15 марта 2020

Я некоторое время смотрел на этот алгоритм, но не мог определить, что я пропустил.

Logi c:

  1. Инициировать все изолированные компоненты
  2. union frm, чтобы компонент в каждом ребре и декремент # компонентов, если эти компоненты еще не подключены ,

Вопрос: как получилось, что я получил -48 при выполнении этого конкретного теста? 

    def countComponents(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: int
        """
        roots = [i for i in range(n)]  # track disconnected components

        # n isolated islands
        for u, v in edges:

            root1 = self.findRoot(roots, u)
            root2 = self.findRoot(roots, v)

            if root1 != root2:
                roots[root1] = root2
                n -= 1
        #print(roots)
        return n

    def findRoot(self, roots, id):
        oid=id
        if roots[id] != id:
            # roots[id] = roots[roots[id]]
            id=roots[id]

        roots[oid]=id # path compression
        return id

Контрольный пример: 

n=100
edges=[[6,27],[83,9],[10,95],[48,67],[5,71],[18,72],[7,10],[92,4],[68,84],[6,41],[82,41],[18,54],[0,2],[1,2],[8,65],[47,85],[39,51],[13,78],[77,50],[70,56],[5,61],[26,56],[18,19],[35,49],[79,53],[40,22],[8,19],[60,56],[48,50],[20,70],[35,12],[99,85],[12,75],[2,36],[36,22],[21,15],[98,1],[34,94],[25,41],[65,17],[1,56],[43,96],[74,57],[19,62],[62,78],[50,86],[46,22],[10,13],[47,18],[20,66],[83,66],[51,47],[23,66],[87,42],[25,81],[60,81],[25,93],[35,89],[65,92],[87,39],[12,43],[75,73],[28,96],[47,55],[18,11],[29,58],[78,61],[62,75],[60,77],[13,46],[97,92],[4,64],[91,47],[58,66],[72,74],[28,17],[29,98],[53,66],[37,5],[38,12],[44,98],[24,31],[68,23],[86,52],[79,49],[32,25],[90,18],[16,57],[60,74],[81,73],[26,10],[54,26],[57,58],[46,47],[66,54],[52,25],[62,91],[6,72],[81,72],[50,35],[59,87],[21,3],[4,92],[70,12],[48,4],[9,23],[52,55],[43,59],[49,26],[25,90],[52,0],[55,8],[7,23],[97,41],[0,40],[69,47],[73,68],[10,6],[47,9],[64,24],[95,93],[79,66],[77,21],[80,69],[85,5],[24,48],[74,31],[80,76],[81,27],[71,94],[47,82],[3,24],[66,61],[52,13],[18,38],[1,35],[32,78],[7,58],[26,58],[64,47],[60,6],[62,5],[5,22],[60,54],[49,40],[11,56],[19,85],[65,58],[88,44],[86,58]]

1 Ответ

2 голосов
/ 15 марта 2020

Ошибка заключается в функции findRoot. В настоящее время вы проверяете, является ли предоставленный узел (id) родителем самого себя, т. Е. Представительным элементом его набора. Если это не так, вы предполагаете, что его родитель является представителем, и возвращаете его. Но это не обязательно так, даже если вы используете сжатие путей.

Скажем, у вас есть 4 узла A, B, C и D. Края: A -> B, B -> C, A -> D.

Сначала вы устанавливаете родителя A на B, а затем родителя B на C. Это хорошо до здесь. Но когда вы приходите к обработке последнего фронта, вы звоните findRoot(..., A). Он проверяет, что A не является своим родителем, и поэтому возвращает своего родителя B. Но представительный элемент множества A даже не B, это C. Вы можете видеть, что B также не является его родителем. Счетчик компонентов здесь не ошибается, но вы можете увидеть, как он может давать неправильные результаты.

Единственное необходимое изменение - это то, что вы должны продолжать искать репрезентативный элемент, а не просто возвращаться после 1 проверки .

Ваш новый метод будет выглядеть следующим образом: 

def findRoot(self, roots, id):
    oid=id
    while roots[id] != id: # Keep looking for the representative
        id=roots[id]

    roots[oid]=id
    return id

Это изменение приведет к подсчету 6 подключенных компонентов во ваших входных данных. Подтверждено с помощью DFS.

Чтобы реализовать сжатие пути, установите родительское значение каждого из узлов, с которыми вы столкнулись в этом l oop, до конечного значения.

...