Questions tagged [breadth-first-search]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
16 views

Check if any path starting from a vertex in set A and reaching a vertex in set B is long at least k in $\Theta(G)$

I am trying to verify whether it exists a path from $a \in A$ to $b \in B$ whose length is $\ge k$ in $\Theta(G)$. This is what I have done: ...
1
vote
0answers
17 views

Time to form a complete graph from n vertices given that only k vertices can be used at a time [closed]

I know this problem is related to the greedy algorithm and max edges incomplete graph but can't come up with a solution. Problem You are given two numbers n and k: n >= k n is the total # of ...
0
votes
1answer
54 views

Translating the in-order index of a node in a complete, balanced binary tree into the level-order index

Consider the topmost part of a complete, balanced binary tree of all 64-bit numbers, exemplified here. As highlighted by the lack of a 7*2^64/8 term it is not ...
1
vote
1answer
30 views

Algorithm for finding strongest connection for a user on social network

I am working on Problem 6-1 from MIT's Fall 2011 6.006 course. The problem reads as: Problem 6-1. [30 points] I Can Haz Moar Frendz? Alyssa P. Hacker is interning at RenBook (人书 / 人書 in Chinese), a ...
0
votes
2answers
35 views

Is the best known algorithm for the shortest path problem for an undirected and unweighted graph $O(E)$ or $O(E+V)$?

I'm a bit confused by Wikipedia's tables of algorithms for the shortest path problem. For an unweighted graph with $E$ edges and $V$ vertices, it gives the best algorithm as breadth-first search, with ...
0
votes
1answer
25 views

How does BFS guarantee the minimum path for this problem?

https://leetcode.com/problems/bus-routes/ You are given an array routes representing bus routes where routes[i] is a bus route that the ith bus repeats forever. For ...
1
vote
1answer
59 views

Number of sentences and sentential forms generated by a grammar

In this question, I'm considering only "finite grammars". A finite grammar can only produce a finite number of distinct sentences. The following grammar is finite in my definition: ...
0
votes
1answer
75 views

Shortest Path with a twist

We are given a Graph G where, s ∈ V and t ∈ V. w:E such that w represents the time from u to v. We have to calculate shortest path between s to t with a twist. The twist is the turbocharger which can ...
1
vote
1answer
46 views

Prove $|d_{s}(u)-d_{s}(v)|\leq1$ in BFS

Trying to prove the following problem: Given a graph $G=(V,E)$ and vertex $s\in V$, prove that: $\forall (u,v)\in E,\ |d_{s}(u)-d_{s}(v)|\leq1$ where $d_s(v)$ is the shortest path from $s$ to $v$ in ...
4
votes
2answers
90 views

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 ...
0
votes
0answers
29 views

BFS Traversal over a graph question

Starting from a random node, which of these series can be a BFS traversal (L to R)? 1 MNOPQR 2 NQMPOR 3 QMNPRO 4 QMNPOR Now, I understand that my answer (1- MNOPQR) is wrong because I got confused ...
0
votes
0answers
98 views

Find every path that passes through certain edges

I'm faced with the following problem: Given Directed and unweighted graph, where each edge E has two attributes Goal Find every path through the 3 (or more) given edges in a specific order ...
2
votes
1answer
141 views

Name of BFS variant with multiple queues with different priorities

Is there a name for the following variant of BFS that operates on trees with non-root starting point?: Instead of a single queue that all neighbor nodes are added to when processing a node, two ...
1
vote
1answer
50 views

BFS for transforming one word to another

I'm having a hard time understand the reasoning in the solution of 18.7 in Elements of programming interviews (EPI): Let $s$ and $t$ be stings and $D$ a dictionary, i.e., a set of strings. Define $s$ ...
0
votes
1answer
103 views

Minimum amount of time for two enemies to reach their destinations?

Given an undirected, unweighted, and connected graph $G = (V, E)$, what is the minimum amount of time it takes for party $X$ to go from $s_x$ to $t_x$ and party $Y$ to go from $s_y$ to $t_y$? At each ...
2
votes
0answers
41 views

How to find more than 1 successive shortest paths between two vertices in unweighted and undirected graph using BFS?

I have tried to find and print more than one successive shortest paths between two vertices in the undirected graph. Using BFS as DFS will not be optimal in this case, as it can go deep into the stack....
1
vote
0answers
28 views

Why does this BFS solution work for this question about euclidean distance and what's its complexity?

Given a matrix of 1s and 0s where 0 represents houses and 1 represents stores, find the square of minimum Euclidean distance of every house to nearest store. Return it as a vector of vector. ...
2
votes
1answer
53 views

“Visited” vs “Seen” Positions in Breadth-First Search

I'm struggling to understand why there is such a radical difference in the execution time and number of steps required by two seemingly similar algorithms for Breadth-First Search in a 2d grid. In ...
0
votes
0answers
58 views

Graphs which favour BFS over DFS and vice versa

I am trying to figure out what kinds of graphs are better suited to BFS and which are better suited to DFS. However i'm struggling to visualise what kind of graphs favour which search. Could someone ...
0
votes
1answer
80 views

Why MIT lecture breadth-first search algorithm is so complicated?

I watched a video for BFS from MIT and the algorithm the lecturer presented was really complicated compared to what I came up. My solution seems to work fine and walk through the vertices in the ...
2
votes
0answers
2k views

Comparing classical tree-search algorithms (BFS,DFS,A*,IDS) - when to use one or the other?

I have a question about classical tree-search algorithms as I will have an exam soon and this is the type of questions they might be asking. Although I know how to compare the complexities, optimality,...