Questions tagged [breadth-first-search]
The breadth-first-search tag has no summary.
49 questions
1
vote
1
answer
175
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 ...
- 131
3
votes
1
answer
167
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 ...
- 374
2
votes
1
answer
160
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 ...
- 21
4
votes
2
answers
1k
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. ...
- 43
2
votes
1
answer
262
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 ...
- 123
1
vote
1
answer
70
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 ...
- 367
2
votes
1
answer
290
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 ...
- 142
1
vote
0
answers
332
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) ...
- 11
0
votes
0
answers
280
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
1
answer
739
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 ...
- 111
0
votes
0
answers
59
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
68
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 ...
- 11
3
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
207
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 ...
- 59
1
vote
0
answers
129
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 ...
- 11