<jupyter_start><jupyter_text><jupyter_code>!git clone https://github.com/lmcanavals/algorithmic_complexity.git 2>/dev/null
from algorithmic_complexity.aclib import graphstuff as gs
import numpy as np
import networkx as nx
G = [[0, 0, 0, 1, 1, 0, 0, 0],
     [0, 0, 0, 1, 0, 1, 1, 0],
     [0, 0, 0, 0, 1, 1, 1, 0],
     [1, 1, 0, 0, 0, 0, 0, 1],
     [1, 0, 1, 0, 0, 0, 1, 0],
     [0, 1, 1, 0, 0, 0, 1, 1],
     [0, 1, 1, 0, 1, 1, 0, 0],
     [0, 0, 0, 1, 0, 1, 0, 0]]
G = np.array(G)
gs.as_gv(nx.from_numpy_matrix(G))
def bfsAM(G, s):
  n = len(G)
  queue = [s]
  path = [-1]*n
  visited = [False]*n
  visited[s] = True

  while queue:
    u = queue[0]
    for v in range(n):
      if G[u][v] == 1 and not visited[v]:
        visited[v] = True
        path[v] = u
        queue.append(v)

    del queue[0]

  return path
path = bfsAM(G, 5)
print(path)
gs.path2gv(path)<jupyter_output>[3, 5, 5, 1, 2, -1, 5, 5]<jupyter_text>Time complexity of BFS for Adjacency Matrix is $O(V^2)$ V being the number of vertices.  BFS for simple Adjavenct List<jupyter_code>G = [[3, 4],
     [3, 5, 6],
     [4, 5, 6],
     [0, 1, 7],
     [0, 2, 6],
     [1, 2, 6, 7],
     [1, 2, 4, 5],
     [3, 5]]
def bfsAL(G, s):
  n = len(G)
  queue = [s]
  path = [-1]*n
  visited = [False]*n
  visited[s] = True

  while queue:
    u = queue[0]
    for v in G[u]:
      if not visited[v]:
        visited[v] = True
        path[v] = u
        queue.append(v)

    del queue[0]

  return path
path = bfsAL(G, 5)
print(path)
gs.path2gv(path)<jupyter_output>[3, 5, 5, 1, 2, -1, 5, 5]<jupyter_text>Time complexity of BFS for Adjacency Matrix is $O(V + E)$ V being the number of vertices and E is the numeber of edges.<jupyter_code>%%file 1.adjlist
0 3 4
1 3 5 6
2 4 5 6
3 0 1 7
4 0 2 6
5 1 2 6 7
6 1 2 4 5
7 3 5
G = nx.read_adjlist('1.adjlist')
gs.as_gv(G)<jupyter_output><empty_output><jupyter_text>BFS on networkx graph<jupyter_code>def bfs(G, s):
  queue = [s]
  for u in G.nodes:
    G.nodes[u]['visited'] = False
    G.nodes[u]['π'] = -1
  G.nodes[s]['visited'] = True
  while queue:
    u = queue[0]

    for v in G.neighbors(u):
      if not G.nodes[v]['visited']:
        G.nodes[v]['visited'] = True
        G.nodes[v]['π'] = u
        queue.append(v)

    del queue[0]
bfs(G, '5')
path = [0]*G.number_of_nodes()
for v, info in G.nodes.data():
  path[int(v)] = int(info['π'])

print(path)
gs.path2gv(path)<jupyter_output>[3, 5, 5, 1, 2, -1, 5, 5]
{'fraction_non_alphanumeric': 0.18301731244847486, 'fraction_numerical': 0.06801319043693323, 'mean_word_length': 2.6717095310136156, 'pattern_counts': {'":': 0, '<': 14, '<?xml version=': 0, '>': 15, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '52784', 'license': 'CC0-1.0', 'n_tokens_mistral': 1240, 'n_tokens_neox': 1108, 'n_words': 335, 'path': 'notebooks/al_bfs.ipynb', 'repo_name': 'AgustinAMaita/DataSet', 'size': '2426'}