Skip to main content

Questions tagged [breadth-first-search]

The tag has no usage guidance.

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

Why is the time complexity of bidirectional breadth first search still considered O(V + E)?

I understand that if the branching factor of the graph is b and distance of goal vertex from source is d, then the time complexity is O(b^d). I also understand why that would be O(b^d/2) using ...
3 votes
1 answer
88 views

The existence of a (nearly) quadratic time algorithm for 2-steps shortest path or smallest triangle

I am interested in two problems, which seem to be related, solving each will advance me in other possible directions. In both problems, $G=(V,E)$ is a positively-weighted undirected graph. Denote its ...
2 votes
1 answer
92 views

Find best path in an alternating graph

I am trying to solve the following problem: Given a directed graph, there is a robot in the start and it needs to reach the destination. Each movement takes 1 second, and every second the graph ...
0 votes
0 answers
16 views

How to get the iterator of the ancestor nodes during DFS or BFS?

I am able to solve this by myself, but somebody may already know the answer, so saving manpower, instead of me probably trying several variants. What is an easy way during either DFS or BFS of a DAG ...
4 votes
2 answers
530 views

How to represent BFS and DFS between adjacency matrix and list?

I'm trying to figure out how to best represent BFS (Breadth First Search) and DFS (Depth First Search) on a graph, specifically between being represented as an adjacency matrix and an adjacency list. ...
2 votes
1 answer
63 views

DFS (Depth-first search) vs BFS (Breadth-first search) Space Optimizations

Problem I am currently digging deep into some optimizations on the classical iterative approaches to both DFS and BFS algorithms. The material I'm currently using at my University presents both ...
1 vote
1 answer
31 views

Proving that Breadth-First Search (BFS) results in a bipartition of a tree

In my studies of discrete mathematics, I've learned that a tree graph is inherently bipartite. I'm interested in finding an algorithmic approach to determine its bipartition. It seems to me that ...
1 vote
1 answer
194 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 ...
2 votes
1 answer
247 views

An efficient way to find a pair of unrelated edges

I'm writing a program which uses an undirected graph to represent certain social connections, and I'm trying to check whether or not it's contains a specific induced subgraph. Given a dense an ...
1 vote
0 answers
190 views

Why in Edmonds Karp or Ford Fulkerson Algorithm the time complexity of BFS or DFS respectively is O(E) rather than O(V+E)?

For these algorithms, the time complexity of BFS and DFS is O(E). I have gone through many websites and even the algorithm books, but I never got a clear idea of why it is O(E). It just says it's O(E) ...
0 votes
0 answers
45 views

Confusion about Lemma for Breadth-first search (BFS) proof of correctness

I'm working my way through the graph section of Introduction to Algorithms by CLRS (3E,4E) and I came across the following proof: 3E: Lemma 22.2 Let $G = (V, E)$ be a directed or undirected graph, and ...
0 votes
0 answers
138 views

Prove that BFS computes the shortest path from one vertex to another

I read in Algorithms in C by Sedgewick that we can easily prove by induction that breadth-first search algorithm computes the shortest path from one vertex to another (unweighted graphs or weighted ...
1 vote
0 answers
300 views

Goal-testing when node is "Generated" vs when node is "Expanded" contradiction (breadth-first search)

In my textbook "AI: A Modern Approach" it states that we expand a node to generate it's children. So I understand the definition of those two words as: Expand - Generate/create all the new ...
0 votes
0 answers
42 views

Algorithm for detecting if H is a induced subgraph of G in O(n)

Say that I am given a graph $H$ and a graph $G$ where the maximum degree of $G$ is known. How can I use BFS to find out if $H$ is an induced subgraph of $G$ in $O(n)$ time? My current take is the ...
1 vote
2 answers
35 views

Special arcs - graph traversal

question is: given an unwighted nondirected graph G=(V,E) portrayed as an adjacency list, a special arc is defined as an arc (u,v) where both u and v has the same distance from source vertex s. i ...
2 votes
1 answer
1k views

How to determine the time and memory complexity for solving a sliding-tile puzzle?

I have seen many posts which were related to algorithms for solving an N⨯N puzzle, but I could not figure out the time complexity or memory complexity in these algorithms, especially when we want to ...
1 vote
1 answer
148 views

Correctness of bft resulting in shortest path

I found the following proof concerning the correctness of a breadth-first traversal resulting in shortest path: source: https://people.eecs.berkeley.edu/~daw/teaching/cs170-s03/Notes/lecture6.pdf The ...
1 vote
0 answers
87 views

Proof for Queue in BFS consists of vertices of distance k and k+1

For any vertex v reachable from s, BFS computes a shortest path from s to v (no path from s to v has fewer edges). In order to prove the above proposition, The author of the book has stated that we ...
2 votes
1 answer
283 views

The distinct-vertex $\alpha$-edge variant of the all-pairs shortest paths problem

The following problem is a variant of the all pairs shortest path problem: Given a weighted, directed graph $G=(V,E), |V| = n,|E| = m,$ and an integer $\alpha\ge 1$, how can I find an efficient ...
0 votes
3 answers
2k views

Is DFS better than BFS for space complexity when finding path from root to a node in a tree?

For simplicity, and I think without loss of generality, we can consider a binary tree. Suppose that we want to find the path between the root node and some node in the tree (we don't know where it is ...
-1 votes
1 answer
623 views

How to find time complexity of Breadth First Search for this tree?

This is what I got from another forum, but honestly doesn't make much sense to me. Time complexity for a single tree doesn't make a lot of sense, since the function in the big O notation might be ...
1 vote
0 answers
218 views

Visiting vertices on a graph using DFS and BFS

I have this graph that I created and am wondering how DFS and BFS would work on something like this. I made this graph undirected and am going off the premise that if possible, a vertex should be ...
1 vote
1 answer
395 views

Why can't we use BFS with modifications to find shortest paths in weighted graphs

I came across this post about how we can get to all shortest paths from source (u) to destination (v) . If the algorithm is working in O(E + V), why can't we use it (after slight modifications) for ...
0 votes
0 answers
679 views

Number of shortest paths between two nodes in undirected unweighted graph

I'm trying to devise a $O(|V| + |E|)$ algorithm to calculate number of shortest paths between $s$ and $f$ on a undirected, unweighted graph. Can someone please check my pseudo-code? Also, isn't $O(|V| ...
1 vote
1 answer
134 views

Is the first distance that gets assigned to a node in BFS always the shortest distance?

Consider the following bfs pseudo code that calculates distances of all nodes from $s$ in graph $G=(V,E)$. I know that if $G$ was undirected and unweighted, then the above bfs would calculate correct ...
-2 votes
1 answer
8k views

Print all nodes which are the endpoint of the diameter of a tree

Given a tree with n nodes, Print all nodes which are the endpoint of the diameter. 1<= n <=100000. E.g. For Above tree answer would be A,B,F,G I tried the O(n2) approach (Running Dfs from each ...
1 vote
1 answer
55 views

Meaning of source here

In graph theory, a source of a directed graph $D = (V(D), E(D))$ is a vertex of it whose in-degree is zero. The book CLRS makes these statements: Given a graph $G = (V, E)$ and a distinguished source ...
0 votes
1 answer
535 views

Connectivity in Directed Graph

Connectivity in undirected graph can be easily identified using Disjoint Union Set (Union Find). Is there any way to check connectivity in a directed graph efficiently other than doing Depth First ...
4 votes
2 answers
642 views

Why do basic graph algorithms (BFS, DFS, Prim, Kruskal) have a similar structure?

This is my first post on CS Stack Exchange. For some time, I have been studying basic graph algorithms, mainly BFS, DFS, minimum spanning trees and their basic algorithms (Kruskal and Prim). One thing ...
3 votes
2 answers
47 views

There exists some number $x$ so in any run of BFS from vertex $w$, so the distance from $u$ to $v$ in BFS tree is always $x$

Studying for my finals and stuck on the following question: Prove or disprove: Given an undirected and connected graph $G=(V,E)$ and three different vertices $u,v,w\in V$ then there exists some ...
-1 votes
1 answer
202 views

Why Breadth First Search is used for shortest path

We can read on the internet: BFS finds the shortest path to the destination. But how ? Check this example: for this example we can get 40 10 20 30 60 50 70 What is ...
0 votes
0 answers
19 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
1 answer
170 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 ...
1 vote
0 answers
29 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
2 answers
174 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
1 answer
136 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
1 answer
203 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
1 answer
136 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
1 answer
59 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
2 answers
186 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
0 answers
37 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
0 answers
269 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
1 answer
531 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
1 answer
148 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
1 answer
124 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
0 answers
74 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
0 answers
164 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
1 answer
175 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
0 answers
65 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
1 answer
99 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 ...