DFS с использованием смежной матрицы не работает - PullRequest
Новая
       12

DFS с использованием смежной матрицы не работает

0 голосов
/ 07 марта 2019

Код ниже должен выполнять DFS в графе. Я использую матрицы смежности из-за производительности. Мой псевдо-алгоритм выглядит следующим образом:

1) выбрать начальный узел i

2) добавить узел к visited

3) удалить узел из unvisited

4) Для каждого оставшегося узла j в unvisited проверьте, существует ли ребро (i,j) в матрице смежности, если да, переходите к 1) и используйте j в качестве начального узла.

Я использую наборы, а не списки, чтобы отслеживать посещенные / не посещенные из-за сложности времени, связанной со списками (для удаления из списка требуется O (n), а из наборов - O (1)).

Код не выполняется с учетом простейшего графа (n = 3, [1,2], [2,3] [1,2]). Возвращает ошибку. 

File "solution.py", line 51, in dfs
    self.unvisited.remove(start)
KeyError: 2

Как я могу сделать эту работу?

Полный код: 

class GraphMat:
    def __init__(self,n):
        self.size = n
        self.adjMat = [[False for i in range(n)] for j in range(n)]
        self.visited = set()
        self.unvisited = set([i for i in range(n)])
        self.path = []

    def allVisited(self):
        return len(self.unvisited) == 0

    def getFirstUnv(self):
        return next(iter(self.unvisited))

    def addEdge(self,u,v):
        self.adjMat[u-1][v-1] = True
        self.adjMat[v-1][u-1] = True

    def p(self):
        for i in self.adjMat:
            print i
        print '\n'

    def getUnvisited(self):
        return self.unvisited

    def dfs(self,start):
        print 'Visiting %d'%start

        self.path.append(start)
        print self.path
        self.visited.add(start)
        self.unvisited.remove(start)
        arr = [i for i in self.unvisited if self.adjMat[start][i]]
        print arr
        if len(arr) == 0:
            return
        for i in arr:
            self.dfs(i)

def main():
    g = GraphMat(3)
    for i in [[1,2],[1,3],[2,3]]:
        g.addEdge(i[0],i[1])
    g.dfs(0)


main()
...