Skip to main content
We’ve updated our Terms of Service. A new AI Addendum clarifies how Stack Overflow utilizes AI interactions.
Computer Science

Questions tagged [breadth-first-search]

The tag has no summary.

Filter by
Sorted by
Tagged with
1 vote
1 answer
177 views

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
167 views

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
160 views

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 ...
4 votes
2 answers
1k views

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
262 views

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
70 views

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 ...
2 votes
1 answer
290 views

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
333 views

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
283 views

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
752 views

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
59 views

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

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 ...
3 votes
1 answer
1k views

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

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
129 views

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 ...

15 30 50 per page
1
2 3 4

AltStyle によって変換されたページ (->オリジナル) /