Блог

Приведенный ниже код должен выполнять 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()