Первый поиск в ширину - путаница - PullRequest
Новая
       25

Первый поиск в ширину - путаница

0 голосов
/ 27 мая 2019

Чтобы понять ширину первого поиска, я посмотрел множество видео. Затем я нашел код Python на GeeksForGeeks

Я заметил, однако, что когда я удалил строку g.addEdge(2, 0) из кода, выходы были ограничены 2, 3

Правильно ли это, или метод BFS должен также перемещаться вверх и, следовательно, находить узлы 0 и 1? Если это так, я был бы прав, думая, что метод defaultdict не идеален для BFS?

Это код от GeeksForGeeks 

from collections import defaultdict 

class Graph: 
    def __init__(self):  
        self.graph = defaultdict(list) 

    def addEdge(self,u,v): 
        self.graph[u].append(v) 

    def BFS(self, s): 
        visited = [False] * (len(self.graph)) 
        queue = [] 
        queue.append(s) 
        visited[s] = True

        while queue: 
            s = queue.pop(0) 
            print (s, end = " ") 
            for i in self.graph[s]: 
                if visited[i] == False: 
                    queue.append(i) 
                    visited[i] = True
g = Graph() 
g.addEdge(0, 1) 
g.addEdge(0, 2) 
g.addEdge(1, 2) 
g.addEdge(2, 0)
g.addEdge(2, 3) 
g.addEdge(3, 3) 
g.BFS(2)
...