Блог

Я пытаюсь вывести дерево BFS, используя связанный список. Однако у меня возникли проблемы с реализацией алгоритма. Я застрял на том, как внедрить график связанного списка в алгоритм. Я не слишком уверен, как я могу создать матрицу массива false и true, а затем выполнить итерацию по ней, чтобы найти ложные узлы в соответствии с выбранным дочерним узлом. Вывод, который я должен получать, таков

 0: 1 3 1: 2 4 3: 4:  

Код:

 class Node:  def __init__(self, value):  self.vertex = value  self.next = None   class AdjGraph:  def __init__(self, data):  self.data = data  self.graph = [None] * self.data   # Add edges  def addEdge(self, vertice, edge):  currNode = self.graph[vertice]  newNode = Node(edge)    if currNode == None:  self.graph[vertice] = newNode   return    while currNode != None:  if currNode.next == None:  currNode.next = newNode  break  currNode = currNode.next   # Implement BFS Graph  def bfs(self, s):  # Set discovered[s] = true, discovered[v] = false for all other v  discovered = [False] * self.graph  discovered[s] = True  # Intialize L[0] to consist of the single element s  layer = []  layer.append(s)  # Set the counter i = 0  i = 0  # Set the current BFS tree T = None  T = None   # While L[i] is not empty  while layer:  # Initialize an empty list L[i 1]  empty_list = layer[i 1]  print (s, end = " ")  # For each node u is an element of L[i]  for u in layer[i]:  # Consider each edge (u, v) incident to u  if discovered[v] == False:  # Set discovered[v] = true  discovered[v] = True  # Add edge (u, v) to the tree T  T.append  # Add v to the list L[i 1]  empty_list.append(v)   # Print the graph  def printGraph(self):  adj_list = "Adjacency List"  for i in range(self.data):  adj_list  = "nnNode "   str(i)   ": "  temp = self.graph[i]  while temp:  adj_list  = str(temp.vertex)   " "  temp = temp.next  print(adj_list)   g = AdjGraph(5) g.addEdge(0, 1) g.addEdge(0, 3) g.addEdge(1, 0) g.addEdge(1, 2) g.addEdge(1, 3) g.addEdge(1, 4) g.addEdge(2, 1) g.addEdge(2, 4) g.addEdge(3, 0) g.addEdge(3, 1) g.addEdge(3, 4) g.addEdge(4, 1) g.addEdge(4, 2) g.addEdge(4, 3) g.bfs(0)  

В вашем bfs коде много проблем. Я не буду перечислять их все, но:

• [False] * self.graph не имеет смысла, так как self.graph это не число
• layer[i 1] не существует при первой оценке
• for u in layer[i] не работает как layer[i] номер узла ( s ) и не подлежит повторению
• empty_list получает значения, но они никогда не используются.
• T.append ничего не делает.
• Хотя есть попытка ввести данные T , они никогда не используются.
• Значение i никогда не меняется.
• bfs изменяет только локальные переменные и ничего не возвращает. Таким образом, после того, как он был вызван, нет ничего, что отличалось бы от того, что было до его вызова, за исключением номеров узлов, которые печатаются. Но я полагаю, что это было сделано только для целей отладки, так как оно не соответствует формату вывода.

Как я упоминал в комментариях, поскольку ожидаемый результат соответствует дереву поиска, которое формируется с помощью поиска по ширине (BFS), результат может отличаться в зависимости от порядка добавления узлов и порядка посещения узлов.

Пример графика выглядит следующим образом:

 0-----1   /|   / |   3--4--2  

BFS, который начинается в узле 0, может создать любое из этих деревьев поиска:

 0-----1 0-----1   |     |     3 4 2 3--4 2  

Это зависит от порядка, в котором развернуты узлы 1 и 3. Первое дерево является результатом, когда узел 1 расширяется первым, в то время как второе дерево является результатом, когда узел 3 расширяется первым.

Теперь, поскольку вы хотите работать со связанными списками, я должен также упомянуть, что добавление узла в связанный список более эффективно выполняется в начале списка, чем в конце (если вы также не поддерживаете хвостовую ссылку). Поэтому я бы предложил не currNode использовать цикл, а добавить новый узел в начале списка. Таким образом, петли не будет. Это, конечно, влияет на порядок узлов, которые оказываются в списке.

Следующий код удалит из графика ребра, которые не используются в дереве BFS. Таким образом, вы можете использовать свою printGraph функцию для вывода результата.

Код:

 class Node:  def __init__(self, value, nxt=None):  self.vertex = value  self.next = nxt   class AdjGraph:  def __init__(self, size):  self.size = size  self.graph = [None] * self.size   def addEdge(self, vertex, edge):  # Prepend the new node to the linked list  self.graph[vertex] = Node(edge, self.graph[vertex])    def bfs(self, s):  discovered = [False] * self.size  discovered[s] = True  layer = [s]   while layer:  empty_list = []  for u in layer:  keep = None # this will be the new (filtered) list for self.graph[u]  v = self.graph[u]  while v:  nxt = v.next  if not discovered[v.vertex]:  discovered[v.vertex] = True  empty_list.append(v.vertex)  # Prepend v to the keep linked list  v.next = keep  keep = v  v = nxt  self.graph[u] = keep  layer = empty_list # start working with the next layer   def printGraph(self):  adj_list = "Adjacency List"  for i in range(self.size):  adj_list  = "nNode "   str(i)   ": "  temp = self.graph[i]  while temp:  adj_list  = str(temp.vertex)   " "  temp = temp.next  print(adj_list)   g = AdjGraph(5) g.addEdge(0, 1) g.addEdge(0, 3) g.addEdge(1, 0) g.addEdge(1, 2) g.addEdge(1, 3) g.addEdge(1, 4) g.addEdge(2, 1) g.addEdge(2, 4) g.addEdge(3, 0) g.addEdge(3, 1) g.addEdge(3, 4) g.addEdge(4, 1) g.addEdge(4, 2) g.addEdge(4, 3) g.bfs(0) g.printGraph()  

Выход:

 Adjacency List Node 0: 1 3  Node 1: 2  Node 2:  Node 3: 4  Node 4: