## python – Is this BFS solution ‘slow’ – LeetCode #688

I’m learning competitive programming and came across this question on LeetCode : 688. Knight Probability in Chessboard

On an n x n chessboard, a knight starts at the cell (row, column) and
attempts to make exactly k moves. The rows and columns are 0-indexed,
so the top-left cell is (0, 0), and the bottom-right cell is (n – 1, n-1).

A chess knight has eight possible moves it can make, each move is two cells in a cardinal direction,
then one cell in an orthogonal direction. Each time the knight is to move, it chooses one of eight > possible moves uniformly at random (even if the piece would go off the chessboard) and moves there.

The knight continues moving until it has made exactly k moves or has moved off the chessboard.

Return the probability that the knight remains on the board after it has stopped moving.

I wrote following BFS solution for it

``````from collections import deque

class Solution:
def knightProbability(self, N: int, K: int, r: int, c: int) -> float:
i = 0
pos_moves = deque(((r, c, 1)))  # (r, c, prob)
self.moves_memo = {}
while i < K and len(pos_moves):
increase_i_after = len(pos_moves)
for j in range(increase_i_after):
move = pos_moves.popleft()

for next_move in self.get_pos_moves(N, move(0), move(1), move(2)):
pos_moves.append((next_move(0), next_move(1), next_move(2)))

i += 1

ans = 0
for m in pos_moves:
ans += m(2)

return ans/len(pos_moves) if len(pos_moves) > 0 else 0

def get_pos_moves(self, n, r, c, prev_p):
# Returns a list of possible moves
if (r, c) in self.moves_memo:
pos_moves = self.moves_memo((r, c))
else:
pos_moves = deque(())
if r+2 < n:
if c+1 < n:
pos_moves.append((r+2, c+1, 0))
if c-1 >= 0:
pos_moves.append((r+2, c-1, 0))
if r+1 < n:
if c+2 < n:
pos_moves.append((r+1, c+2, 0))
if c-2 >= 0:
pos_moves.append((r+2, c-2, 0))
if r-2 >= 0:
if c+1 < n:
pos_moves.append((r-2, c+1, 0))
if c-1 >= 0:
pos_moves.append((r-2, c-1, 0))
if r-1 >= 0:
if c+2 < n:
pos_moves.append((r-1, c+2, 0))
if c-2 >= 0:
pos_moves.append((r-1, c-2, 0))

self.moves_memo((r, c)) = pos_moves

l = len(pos_moves)
if l == 0:
return pos_moves
else:
for move in pos_moves:
move(2) = prev_p*l/8

return pos_moves

``````

For n = 8, K = 30, r = 6, c = 4, this solution exceeds time limits. I am not able to figure out why is this solution less time efficient than this. I’m looking for reasons why my code is ‘slow’. Thank you!

## python – Implementing BFS for Adj List

I am trying to implement a BFS to get the path from a starting vertex using the code below, where can I go from here?

``````class Node:
def __init__ (self, value):
self.vertex = value
self.next = None

class Graph:
def __init__(self, vertices):
self.vx = vertices
self.graph = (None) * self.vx
# This is connection for 1st node
node = Node(node2)
node.next = self.graph(node1)
self.graph(node1) = node

# This is connection for 2nd node
node = Node(node1)
node.next = self.graph(node2)
self.graph(node2) = node

def print(self):
for i in range(len(self.graph)):
print(i, ":", end="")
a = self.graph(i)
while a:
print(" " ,(a.vertex), end="")
a = a.next
print("n",end="")

# First Graph
graph = Graph(8)
``````

So for example if I input 2 I want the path to be able to go to 0.
Meaning it’ll have 2 > 0

## python – BFS search crawler

I have tried to make a simple crawler that goes through hashtag pages and gets their url printing converting them into a ego graph. My issue is that i would rather preform a BFS search crawl on the hashtags instead but i really don’t know where to start. The goal is to have a list of visited visited hashtags and add new visited hashtags to that list without counting duplicates. Anyone got any tips for simple improvements to the code i already have to be able to accomplish this?
This is what i have so far

``````from selenium import webdriver
from selenium.webdriver.common.by import By
from selenium.webdriver.support.ui import WebDriverWait
from selenium.webdriver.support import expected_conditions as EC
from selenium.webdriver import ActionChains
from selenium.webdriver.common.keys import Keys
import re
import networkx as nx
import matplotlib.pyplot as plt
import time

# Program for creating a twitter hashtag network. Does not go in depth, only creates an ego network
# for one particular hashtag.

def scrolldown():
for i in range(5):
ActionChains(driver).send_keys(Keys.PAGE_DOWN).perform()
time.sleep(.3)

nodes = ()
edges = ()

driver = webdriver.Chrome(executable_path="driver/chromedriver")

def find_hashtag(hashtag, oldhashtag):
driver.get(url)

WebDriverWait(driver, 30).until(
EC.presence_of_all_elements_located(

scrolldown()

a = driver.find_elements_by_tag_name('a')
blacklist = f"(?!{hashtag.lower()})(?!{hashtag.upper()})(?!{hashtag.capitalize()})"
regex = re.compile(full)

if regex.match(url) is not None:
nodes.append(hashtag_text)
edges.append((f"#{hashtag}", hashtag_text))

find_hashtag("Trondheim")
find_hashtag("Stavanger")

print(edges)

G = nx.Graph()
nx.draw(G, with_labels=True)
name = "testGraph"
nx.write_graphml(G, f"{name}.graphml")
plt.show()

driver.quit()
``````

## Unity BFS visualization – materials wont update

I made some bfs visualization in unity. It consists of area of square planes which will change color as they are visited.
My code is:

``````using System;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class BFS : MonoBehaviour
{
public GameObject blockArea;
(int, int)() moves = new (int, int)(4) { (1, 0), (0, 1), (-1, 0), (0, -1) };

public void bfs()
{
List<(int, int)> starts = new List<(int, int)>();
List<(int, int)> goals = new List<(int, int)>();

GameObject()() blocks = blockArea.GetComponent<Area>().area;
int()() area = new int(blocks.Length + 2)();

for (int i = 0; i < area.Length; i++)
{
area(i) = new int(blocks(0).Length + 2);
for (int j = 0; j < area(i).Length; j++)
{
if (i == 0 || j == 0 || i == area.Length - 1 || j == area(i).Length - 1)
{
area(i)(j) = 1;
}
else
{
area(i)(j) = blocks(i - 1)(j - 1).GetComponent<Block>().state;
if (area(i)(j) == 2)
{
}
else if (area(i)(j) == 3)
{
}
}
}
}

ExecuteBFS(ref area, ref blocks, ref starts, ref goals);
}

(int, int) AddTuple((int, int) first, (int, int) second)
{
return (first.Item1 + second.Item1, first.Item2 + second.Item2);
}

void ExecuteBFS(ref int()() area, ref GameObject()() blocks, ref List<(int, int)> starts, ref List<(int, int)> goals)
{
for (int s = 0; s < starts.Count; s++)
{
Queue<(int, int)> q = new Queue<(int, int)>();
q.Enqueue(starts(s));

while (q.Count != 0 && q.Peek() != goals(0))
{
(int, int) cor = q.Dequeue();

for (int i = 0; i < moves.Length; i++)
{
(int, int) newCor = AddTuple(cor, moves(i));
if (area(newCor.Item1)(newCor.Item2) == 3)
{
//showPath
goals.Remove(newCor);
if (goals.Count == 0)
{
//stats
return;
}
}
else if (area(newCor.Item1)(newCor.Item2) == 0)
{
//coordinate in process
blocks(newCor.Item1 - 1)(newCor.Item2 - 1).GetComponent<Block>().SetState(5);
area(newCor.Item1)(newCor.Item2) = 5;

q.Enqueue(newCor);

//delay
MyDelay(0.01f);
//coordinate visited
blocks(newCor.Item1 - 1)(newCor.Item2 - 1).GetComponent<Block>().SetState(4);
area(newCor.Item1)(newCor.Item2) = 4;
}
}
}
//stats
}
}

public static void MyDelay(float seconds)
{
DateTime dt = DateTime.Now + TimeSpan.FromSeconds(seconds);

do { } while (DateTime.Now < dt);
}
``````

and

``````using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class Block : MonoBehaviour
{
public Material() materials;
//0 - empty
//1 - wall
//2 - start
//3 - goal
//4 - visited
//5 - current
public int state;

void Start()
{
state = 0;
GetComponent<MeshRenderer>().material = materials(state);
}

void OnMouseDown()
{
SetState(Area.selectedState);
}

public void SetState(int s)
{
state = s;
GetComponent<MeshRenderer>().material = materials(state);
}
}
``````

When I start the pathfind search, the whole unity freeze and after some time depending on delay, it starts responding and the visited planes are colored. But it wont color them one by one as they are visited. Where is the problem? Thanks!

## c++ – Checking whether a graph is 2-colorable with BFS

I’m trying to check whether a graph is 2-colorable or not using BFS algorithm. The program works for every graph I have checked so far, but using count variable seems wrong for some reason. What could I improve? Also, is it possible to represent a graph of string vertices without using map<>? Here’s the code:

``````#include<iostream>
#include <list>
#include <string>
#include <map>

using namespace std;

class Graph
{
int V; //Number of vertices
map<string, int> strMap;
public:
Graph(int V);
void BFS(string s);
};

Graph::Graph(int V)
{
this->V = V;
strMap = { {"a",0},{"b",1},{"c",2},{"d",3} ,{"e",4} };
}

{
}

void Graph::BFS(string s)
{
// Marking every vertex with 0;
int* color = new int(V);
for (int i = 0;i < V;i++) {
color(i) = 0;
}

//Queue for bfs
list<string> queue;

// Enqueuing current node and setting the color
int col = 1;
color(strMap.at(s)) = col;
queue.push_back(s);
int n;

// 'i' will be used to get all adjacent
// vertices of a vertex
list<string>::iterator i;
/*count the number of times the while loop executes,because it seems to
loop infinitely if the number of vertices is even and the graph is cyclic
*/
int count = 0;
while (!queue.empty() && count<V)
{
//dequeue front vertex
s = queue.front();
queue.pop_front();
//change color
col = col * -1;

//Iterate over every child node of s,if child node's color is the same as parent node's,quit
list<string>::iterator i;
{

if (color(strMap.at(s)) == color(strMap.at(*i))) {
cout << "graph is not 2-colorable";
return;
}
else {
color(strMap.at(*i)) = col;
queue.push_back(*i);
}
}
count++;
}
//if the program doesn't exit till this point,that means it traversed
//the whole graph and didn't find the vertex with different colored neighbor
cout << "graph is 2 colorable";
}
int main()
{
Graph g(5);
//starting vertex
g.BFS("a");

return 0;
}

``````

## Plus Size Traveling Spirit BFS

I’m traveling next week on Spirit and I chose a big front seat. I’m 5’4 and a US size 20. I’m worried that I will need a seat belt extender and from what I’ve heard they don’t offer that in the BFS’. Does anyone have experience with this? I’ve flown spirit and haven’t ever needed an extension but I gained a couple covid lbs. Thanks in advanced!

## trees – Can Edge Belong to a cycle if it is part of multiple BFS products

Given a simple connected undirected graph. with V vertices and E edges.
Let e be some edge from E.

If I perform |V| different BFS runs – meaning started each time from a different vertex – and in every run e is part of the Spanning tree produced from the run.
Can it be belonging to some cycle?

The multiple answers I have to choose from are:

1. it does not belong to any cycle
2. e might belong to a cycle but if it belongs to an odd-length cycle, then it must belong to an even-length cycle.
3. e might belong to a cycle but if it belongs to an even-length cycle, then it must belong to an odd-length cycle.
4. None of the above.

My claim is, because BFS is deterministic and because we performed |V| BFS on the graph, each time from a different vertex. if e was on some cycle, and it doesn’t matter even-length or odd length, one of the vertices on the cycle would have caught up with it and remove it.

The only way that it belongs to every Spanning tree, is if it’s un replaceable, meaning it’s the only thing connecting two vertices.

Am I right? is there any formal proof th

## Bfs forgets to sign my checklist and gave me back unsigned without any reciept

The vfs guy forgot to sign my checklist after i signed it and gave back to me unsigned, then he didn’t gave me any reciept to collect my passport later on. Is there a problem? Its been 15 days i never got any email even the one that i have submitted everything and the process is began.

## algorithm – all possible paths in undirected graph using BFS without recursion (only iterative solution) thru python

could someone pls help reviewing below code?
code is supposed to find all possible paths of an undirected graph using BFS without recursion but it only prints one path (‘C’, ‘B’, ‘D’) instead of
((‘C’, ‘A’, ‘D’), (‘C’, ‘A’, ‘B’, ‘D’), (‘C’, ‘B’, ‘D’), (‘C’, ‘B’, ‘A’, ‘D’))

``````graph = {
'A': ('B', 'D', 'C'),
'B': ('A', 'C', 'D'),
'C': ('B', 'A'),
'D': ('B', 'A')
}

def bfs(graph, start, end):
# maintain a queue of paths
queue = ()
visited = {}
level = {} # distance dictionary
parent = {}
for node in graph.keys():
visited(node) = False
parent(node) = None
level(node) = -1 # inf
# push the first path into the queue
queue.append((start))
all_paths = ()
while len(queue) > 0:
# get the first path from the queue
path = queue.pop(0)
# get the last node from the path
node = path(-1)
# path found
if node == end:
all_paths.append(path)
print(all_paths)
continue
new_path = list(path)
queue.append(new_path)

return all_paths

print (bfs(graph, 'C', 'D'))
``````

## graphs – BFS complexity Why is the complexity

I’m having a hard time understand the reasoning in the solution of 18.7 in Elements of programming interviews (EPI):

``````The number of vertices is d, the number of words in the dictionary. The number of edges is, in the worst-case O(d²). The time complexity is that of BFS, namely O(d+d²) = O(d²). If the string length n is less than d then the maximum number of edges out of a vertex is O(n), implying an O(nd) bound.