Questions tagged [breadth-first-search]
In graph theory, breadth-first search (BFS) is a graph search algorithm that begins at the root node and explores all the neighboring nodes. Then for each of those nearest nodes, it explores their unexplored neighbor nodes, and so on, until it finds the goal.
2,180
questions
0
votes
1
answer
31
views
BFS Node counter
I'm new to Python and I have the BFS algorithm code below, this prints out the visited node
graph = {
'A' : ['B','C'],
'B' : ['D', 'E'],
'C' : ['F'],
'D' : [],
'E' : ['F'],
'F' : []
}
...
-1
votes
0
answers
15
views
Leetcode 785. Is Graph Bipartite? [closed]
I am not sure why my code is failing a test case here:
Test Case = [[1,3],[0,2],[1,3],[0,2]]
Expected answer is true, I am getting false.
I have tried to use a piece of code I have learned (BFS). The ...
-2
votes
0
answers
20
views
Depth first search, breadth first search [closed]
I need someone to explain 2 questions attached here. Thank you
Depth first search
Breadh first search
0
votes
1
answer
19
views
Visit State Check BFS 8-Puzzle
I have implemented the Breadth-First Search for 8-Puzzle however I want to make it more efficient by keeping an account of the visited states/nodes.
If the state has not been visited
then append it to ...
0
votes
0
answers
30
views
Read a text file which consists of the edges of the Graph and perform BFS, DFS, and Shortest Path Algorithm (Dijkstra) in Java
I've been stuck in the addEdge method of my Graph class where instead of having only one "A" Vertex in my Arraylist, it creates a new one for another edge.
For example here is my text file:
...
-1
votes
0
answers
35
views
Generating a maze and finding the shortest path. Python [closed]
I have a project where I am expected to generate a maze using turtle and find the shortest path, I am struggling to generate it. Can someone please assist me
I generated the maze but I hard coded it, ...
0
votes
1
answer
49
views
8-Puzzle BFS output trouble in Python
This is an 8 puzzle and uses bfs and dfs to solve find the solution and prints out the path to the goal. I am having trouble poping and appending the children so that it can find the solution. My ...
1
vote
1
answer
42
views
Find all paths to one ultimate parent based on a dataset showing 1-1 parent child ownership using recursion in Python
I have the following example dataset with 3 columns, child entity, parent entity, ownership percentage of parent in that child:
Child Parent Ownership
A B 50%
C D ...
0
votes
2
answers
75
views
How to calculate the space complexity of the given code
I have written the code for checking whether a path exists between 2 vertices of a undirected, connected graph or not. I have stored my graph in an adjacency matrix. I am mentioning only my function ...
0
votes
0
answers
7
views
During top-down interaction testing, why would one want to integrate the modules in a depth-first manner rather than a breadth-first manner?
During top-down interaction testing, why would one want to integrate the modules in a depth-first manner rather than a breadth-first manner?
During top-down interaction testing, why would one want to ...
0
votes
1
answer
27
views
How to include parents nodes in a Map structure where key is string and value is an array (Javascript)
I am trying to traverse a tree and create a Map data structure that holds only the first parent of the elements . key{child element} : value {array of 1st parents}
My code
global.parentMap = new Map()...
-2
votes
1
answer
33
views
Is that a valid BFS? [closed]
I recently wrote a function to traverse a graph, along those lines:
def traverse(batch: list[str], seen: set[str]):
if not batch:
return
new_batch = []
for node in batch:
...
-1
votes
1
answer
40
views
Number of holes in a 2d array (Python)
Consider a binary 2d array. I'm trying to count the number of connected zeros such that the shape created by these zeros is surrounded entirely by 1s (and hence, not on the boundary). I only need to ...
1
vote
1
answer
55
views
Is is still considered a BFS algorithm if I modify it A little bit?
So I'm trying to create a program that finds the shortest path from nodeA to nodeB, however, I want to block certain nodes so that it would find another path. I'm not really aiming for an optimal code ...
1
vote
2
answers
56
views
Simple Breadth First Search not finding target
This is a standard BFS finding the path through a 2D array maze of 1s and 0s to find a 9.
when dequeue-ing, node coordinates are stored as a string to a hashMap. Items are only added to the queue if ...
2
votes
1
answer
39
views
BFS through matrix maze stuck in loop
This code finds a path through a binary matrix to a location with '9'.
Each iteration, dequeues a root and checks if all children are in bound and contain '0'. If so, that child is added to the queue....
-2
votes
1
answer
60
views
implementation bfs algorithm in python
I have written this piece of code to start a bfs traversal from element x in a given graph(from input) and finally print the number of visited vertices. but it doesn't work.:(
for example for the ...
0
votes
0
answers
37
views
Traverse a Python AST breadth first
I have a Python AST that I'd like to traverse breadth first. ast.walk appears to do the trick, but from its documentation
ast.walk(node)
Recursively yield all descendant nodes in the tree starting at ...
0
votes
1
answer
22
views
Stop recursive calls for tree generation with BFS
I was tasked to write a program that finds the shortest path between a knight and a target tile in a chess board. The task specified to store knight's possible moves in a tree and find paths to the ...
1
vote
0
answers
21
views
I'm getting Runtime Error when submitting answer to online judge. What could be the cause?
Link to the problem : https://vjudge.net/problem/UVA-1665
This is my code so far it works on my end with the sample input provided by the problem statement, i already tried to change the class name ...
-2
votes
1
answer
18
views
Here I solve Word Ladder-2 Leetcode-126 Question In python
import queue
from string import ascii_lowercase
from collections import deque
def findSequences( startWord, targetWord, wordList):
set1={}
for i in range(len(wordList)):
...
0
votes
1
answer
55
views
Find Path in a Maze with bfs
I have a maze which consists of a dictionary (path), the maze has a dimension of (8,8).
In the dictionary is decleared if it's possible to move up, down, left or right.
Now I want to find the path ...
0
votes
1
answer
52
views
Finding the lightest path to one vertex from all others in a graph
Can someone describe the best possible step-by-step solution for this?
Let 𝐺 = (𝑉, 𝐸) be a weighted graph with a weight function 𝑤: 𝐸→ℝ+
Given a subset of vertices 𝑈 belonging to 𝑉 and vertex �...
-2
votes
1
answer
45
views
i have problem solving this problem, can anyone help me it's called the keys and rooms problem on leetcode
There are n rooms labeled from 0 to n - 1 and all the rooms are locked except for room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key.
When you ...
0
votes
2
answers
45
views
How to make good use of BFS for sub milisecond execution?
I have an implementation of BFS that works just fine, but seems to get really CPU heavy, even at low depth (sub ms for a depth of 4 but 10 ms for a depth of 10). I'm quite confident that this ...
0
votes
1
answer
22
views
How to execute all squares the knight will stop on along the way while going from the one position to another?
I've been doing Knights Travails project, and I just can't come up with a solution like I want: (should show the shortest possible way to get from one square to another by outputting all squares the ...
0
votes
2
answers
72
views
Shortest path in an unweighted graph, using user input in C++
As I was practicing C++ today, I came across a code which finds the shortest path in an unweighted graph using BFS and outputs the length of the path and the vertices it travelled through.
I attempted ...
0
votes
0
answers
38
views
How can I make a minimum moves algorithm more efficient?
There are 6 different tile colors that are arranged on a 2D rectangular grid. What is the minimum number of adjacent swaps (horizontal and vertical, not diagonal) that will result in no same colored ...
0
votes
0
answers
30
views
Finding the optimal directed graph of affected nodes with dependencies
I have a set of nodes that represent values that affect each other. I want to find the logical best path of cascading calculation so that each node is calculated only a single time after all of the ...
0
votes
2
answers
65
views
BFS (Breadth First Search) Algorithm in Java -> Cannot implement bfs by not getting node's siblings
I have a problem about getting all siblings from the main node and implementing the process n Breadth First Search algorithm written by Java.
How can I implement that?
I shared my code snippets shown ...
-1
votes
1
answer
116
views
Python code to do breadth-first discovery of a non-binary tree
My problem: I have a known root node that I'm starting with and a specific other target node that I'm trying to find the shortest path to. I'm trying to write Python code to implement the Iterative ...
1
vote
1
answer
71
views
Stuck on Python "KeyError: <exception str() failed>" in BFS code of a water jug scenario
Intended Function of code: Takes a user input for the volume of 3 jars(1-9) and output the volumes with one of the jars containing the target length. jars can be Emptied/Filled a jar, or poured from ...
0
votes
0
answers
51
views
Find out the time complexity and space complexity for the BFS, DFS, IDS, if the solution depth d=5
Let branching factor b=10, Ns=10,000 nodes can be generated per second, St= a node requires 1,000
bytes of storage. Find out the time complexity and space complexity for the BFS, DFS, IDS, if the
...
2
votes
2
answers
65
views
BFS (Breadth First Search) - Not calculating the shortest Path in Java
I have a problem in calculating the shortest path through BFS algorithm in Java.
When I tried to define a path from Node 0 to Node 7 , I got this result. (0 -> 2 -> 3 -> 4 -> 5)
How can I ...
1
vote
0
answers
34
views
Why is the following code not returning True(comparing the symmetry of a binary Tree)
I am comparing the symmetry in a binary tree which means I am checking if the left sub tree is equal to the right sub tree or not
The code is failing for the following input using BFS approach:
Input ...
2
votes
1
answer
76
views
Finding mapping from set of start nodes to set of destination nodes in a grid
We are given a N x M size grid. Each cell represents height of cell.
You can travel to north/south/east/west of a cell if the neighbouring cell has a lower height.
All cells in first row are ...
0
votes
1
answer
15
views
python - collect full path till leaf on organization tree
I got organizations tree stored as json
{
"name": "amos",
"direct_reports": [
{
"name": "bart",
"...
1
vote
2
answers
35
views
How to search a tree that is object based?
I have a tree, and I want find the correct node and insert data into the object.
const resultTree = {
grand_parent: {
parent: {
child: {},
},
sibling: {
cousin: {},
},
}...
0
votes
0
answers
17
views
Issues on Depth Frist search
I tried to do a DFS for the below graph. But when I printed the visited list, I found it is different from the popped out elements from the queue. In the below example, the visited list will come out ...
1
vote
0
answers
41
views
Is there a faster way than bfs to get the shortest path length in a 2d grid
I had this question in an assessment where I was given parameters of a max path length and a 2d grid of characters where 'o' = space you can travel on and 'x' = obstacle where you cant.
The goal of ...
0
votes
0
answers
54
views
print out the shortest path in BFS in c++
I came across a problem in a game described below. You are given an n by n matrix with 0 and 1. The only operation that you can do is to "press" one value in the matrix and the rows and ...
0
votes
1
answer
93
views
Is BFS and DFS Guaranteed To Find The Shortest Path For a Given Graph?
Wondering, if for given G graph, considering cost of the edges are labeled. Not specifying whether they are the same for each edge, or not. Is BFS or DFS known to find the shortest path using the ...
0
votes
0
answers
37
views
Best data structres to store a series of moves for a board game
I have a board game called red swap blue.
The goal is to implement dfs and bfs in this game to solve it.
As a board game you know at every point of the game there are many choice to take one.
As in ...
0
votes
0
answers
29
views
Deleting current Position in a BST
Hello I currently both the working and not working solutions below for the problem
Given the root of a BINARY TREE:
Collect all the leaf nodes.
Remove all the leaf nodes.
Repeat until the tree is ...
-1
votes
2
answers
95
views
Calculate the lowest cost of running several resource collectors on an undirected acyclic graph
We have an undirected acyclic graph where there is only a single path between two connected nodes that may look something like this.
Simple guide to the image:
Black numbers: Node id's (note that ...
-2
votes
2
answers
41
views
How to return all paths with Breadth First Search without printing?
I am trying to print all paths from source= 2 to destination = 3 with a graph that has the following edges:
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(0, 3)
g.addEdge(2, 0)
g.addEdge(2, 1)
g....
0
votes
0
answers
21
views
Python variable and data structure scope
if matrix[row][col] == 0:
continue # continue if it is a water cell
matrix[row][col] = 0 # mark the cell visited by making it a water cell
This is a snippet from the program ...
0
votes
0
answers
48
views
Breadth First Search: Shortest Reach, How To Solve with Python?
Description
Consider an undirected graph consisting of n nodes where each node is labeled from 1 to n and the edge between any two nodes is always of length 6. We define node s to be the starting ...
0
votes
0
answers
87
views
Topological Sort Algorithm Comparison for DAG: BFS vs DFS
I was comparing two topological sort algorithm based on DFS and BFS respectively. I have found out that for higher number of edges (around 50000 or more) BFS is faster than DFS. But I have read ...
0
votes
1
answer
32
views
What's the meaning of "explored" in DFS
I am tring to complete this tree where Iteration is clear, but i don't undertand how to find [tag:explored ] (on the table) or what is explored. I did't find any solution so can anyone explain what is ...