In [1]:

    

import numpy as np
import pandas as pd


    

In [ ]:

    




    

In [ ]:

    

BFS (G, s)                   
//Where G is the graph and s is the source node
      let Q be queue.
      Q.enqueue( s ) //Inserting s in queue until all its neighbour vertices are marked.

      mark s as visited.
      while ( Q is not empty)
           //Removing that vertex from queue,whose neighbour will be visited now
           v  =  Q.dequeue( )

          //processing all the neighbours of v  
          for all neighbours w of v in Graph G
               if w is not visited 
                        Q.enqueue( w )             //Stores w in Q to further visit its neighbour
                        mark w as visited.


    

In [30]:

    

graph = { 'A': ['B', 'C'],
          'B': ['A', 'C'],
          'C': ['B', 'D', 'E' ,'F'],
          'D': ['E'],
          'E': ['C'],
          'F': ['B', 'D'],
          'G': ['H'],
          'H': ['G']}


    

In [16]:

    

def BFS(graph, start):
    queue = []
    visited = set()
    queue.append(start)
    while queue:
        node = queue.pop(0)
        visited.add(node)
        for adjacent in graph[node]:
            if adjacent not in visited:
                queue.append(adjacent)
                visited.add(adjacent)
                
    print(visited)


    

In [81]:

    

from operator import itemgetter, attrgetter
def BFS(graph, start):
    queue = list()
    most = dict()
    visited = set()
    queue.append(start)
    while queue:
        node = queue.pop(0)
        visited.add(node)
        if node in most:
            most[node][0] = len(graph[node])
        else:
            most[node] = [len(graph[node]), 0];
        for adjacent in graph[node]:
            #LOGICA DO QUE A GENTE QUER
            if adjacent in most:
                    most[adjacent][1] += 1;
            else:
                most[adjacent] = [0, 1];
            if adjacent not in visited:
                #RESTO DA BFS
                queue.append(adjacent)
                visited.add(adjacent)
    print(most)
    #SORT MOST EM [0] e depois em [1]
    print(sorted(most.values(), key=itemgetter(0))[::-1]);


    

In [82]:

    

BFS(graph, 'A')


    

    




{'A', 'C', 'B', 'D', 'F', 'E'}
{'F': [2, 1], 'A': [2, 1], 'C': [4, 3], 'B': [2, 3], 'E': [1, 2], 'D': [1, 2]}
[[4, 3], [2, 3], [2, 1], [2, 1], [1, 2], [1, 2]]

In [ ]:

    

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

def BFS(graph, start, end):
    parent = {}
    queue = []
    queue.append(start)
    while queue:
        node = queue.pop(0)
        if node == end:
            return backtrace(parent, start, end)
        for adjacent in graph.get(node, []):
            parent[adjacent] = node 
            queue.append(adjacent)

def backtrace(parent, start, end):
    path = [end]
    while path[-1] != start:
        path.append(parent[path[-1]])
    path.reverse()
    return path

print (BFS(graph, 'A', 'E'))


    

In [ ]:

    

BFS(G,s)
1.  for each vertex u ∈ G.V - {s}
2.     u.color == WHITE
3.     u.d = INF
4.     u.pi = NIL
5.  s.color = GRAY
6.  s.d = 0
7.  s.pi = NIL
8.  Q = ∅
9.  ENQUEUE(Q,s)
10. while Q ≠ ∅
11.    u = DEQUEUE(Q)
12.    for each v ∈ G.Adj[u]
13.       if v.color == WHITE
14.          v.color = GRAY
15.          v.d = u.d + 1
16.          v.pi = u
17.          ENQUEUE(Q,v)
18.    u.color = BLACK


    

In [ ]:

    

# G que tem a propriedade V, vértices
def BFS(G, s):
    for each vertex in G[V] - [s]:


    

In [ ]:

    

def bfs(graph, root):
    S = set()
    Q = list()
    
    S.add(root)
    Q.append(root)
    
    while len(Q) is not 0:
        current = Q.pop()
        if current