algoritmo bfs en ejemplo de código python

Nuestro equipo redactor ha estado por horas buscando para darle resolución a tus búsquedas, te ofrecemos la solución por esto nuestro deseo es que te sea de gran ayuda.

Ejemplo 1: bfs python

graph ='5':['3','7'],'3':['2','4'],'7':['8'],'2':[],'4':['8'],'8':[]

visited =[]# List for visited nodes.
queue =[]#Initialize a queuedefbfs(visited, graph, node):#function for BFS
  visited.append(node)
  queue.append(node)while queue:# Creating loop to visit each node
    m = queue.pop(0)print(m, end =" ")for neighbour in graph[m]:if neighbour notin visited:
        visited.append(neighbour)
        queue.append(neighbour)# Driver Codeprint("Following is the Breadth-First Search")
bfs(visited, graph,'5')# function calling

Ejemplo 2: bfs en python 3

graph ='A':['B','C'],'B':['D','E'],'C':['F'],'D':[],'E':['F'],'F':[]

visited =[]# List to keep track of visited nodes.
queue =[]#Initialize a queuedefbfs(visited, graph, node):
  visited.append(node)
  queue.append(node)while queue:
    s = queue.pop(0)print(s, end =" ")for neighbour in graph[s]:if neighbour notin visited:
        visited.append(neighbour)
        queue.append(neighbour)# Driver Code
bfs(visited, graph,'A')

Ejemplo 3: python amplitud primera búsqueda

# tree level-by-level traversal. O(n) time/spacedefbreadthFirstSearch(root):
    q =[root]while q:
        current = q.pop(0)print(current)if current.left isnotNone: q.append(current.left)if current.right isnotNone: q.append(current.right)

Ejemplo 4: programa Python de primer recorrido de amplitud

classGraph:def__init__(self):# dictionary containing keys that map to the corresponding vertex object
        self.vertices =defadd_vertex(self, key):"""Add a vertex with the given key to the graph."""
        vertex = Vertex(key)
        self.vertices[key]= vertex
 
    defget_vertex(self, key):"""Return vertex object with the corresponding key."""return self.vertices[key]def__contains__(self, key):return key in self.vertices
 
    defadd_edge(self, src_key, dest_key, weight=1):"""Add edge from src_key to dest_key with given weight."""
        self.vertices[src_key].add_neighbour(self.vertices[dest_key], weight)defdoes_edge_exist(self, src_key, dest_key):"""Return True if there is an edge from src_key to dest_key."""return self.vertices[src_key].does_it_point_to(self.vertices[dest_key])def__iter__(self):returniter(self.vertices.values())classVertex:def__init__(self, key):
        self.key = key
        self.points_to =defget_key(self):"""Return key corresponding to this vertex object."""return self.key
 
    defadd_neighbour(self, dest, weight):"""Make this vertex point to dest with given edge weight."""
        self.points_to[dest]= weight
 
    defget_neighbours(self):"""Return all vertices pointed to by this vertex."""return self.points_to.keys()defget_weight(self, dest):"""Get weight of edge from this vertex to dest."""return self.points_to[dest]defdoes_it_point_to(self, dest):"""Return True if this vertex points to dest."""return dest in self.points_to
 
 
classQueue:def__init__(self):
        self.items =[]defis_empty(self):return self.items ==[]defenqueue(self, data):
        self.items.append(data)defdequeue(self):return self.items.pop(0)defdisplay_bfs(vertex):"""Display BFS Traversal starting at vertex."""
    visited =set()
    q = Queue()
    q.enqueue(vertex)
    visited.add(vertex)whilenot q.is_empty():
        current = q.dequeue()print(current.get_key(), end=' ')for dest in current.get_neighbours():if dest notin visited:
                visited.add(dest)
                q.enqueue(dest)
 
 
g = Graph()print('Menu')print('add vertex ')print('add edge  ')print('bfs ')print('display')print('quit')whileTrue:
    do =input('What would you like to do? ').split()
 
    operation = do[0]if operation =='add':
        suboperation = do[1]if suboperation =='vertex':
            key =int(do[2])if key notin g:
                g.add_vertex(key)else:print('Vertex already exists.')elif suboperation =='edge':
            src =int(do[2])
            dest =int(do[3])if src notin g:print('Vertex  does not exist.'.format(src))elif dest notin g:print('Vertex  does not exist.'.format(dest))else:ifnot g.does_edge_exist(src, dest):
                    g.add_edge(src, dest)else:print('Edge already exists.')elif operation =='bfs':
        key =int(do[1])print('Breadth-first Traversal: ', end='')
        vertex = g.get_vertex(key)
        display_bfs(vertex)print()elif operation =='display':print('Vertices: ', end='')for v in g:print(v.get_key(), end=' ')print()print('Edges: ')for v in g:for dest in v.get_neighbours():
                w = v.get_weight(dest)print('(src=, dest=, weight=) '.format(v.get_key(),
                                                             dest.get_key(), w))print()elif operation =='quit':break

Si sostienes alguna vacilación y forma de ascender nuestro crónica puedes dejar una referencia y con mucho gusto lo leeremos.

---

---

Utiliza Nuestro Buscador