Skip to main content
8 votes
Accepted

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

The complexity of the BFS and DFS algorithms depend heavily on the graph being analyzed, and the search strategy being used. If we have a method to consistently get "closer" to a solution, ...
Exalted Toast's user avatar
6 votes
Accepted

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

Maybe not exactly what you are looking for, but there is a really cool and natural way to represent BFS with an adjacency matrix. Consider a graph $G = (V, E)$ and its adjacency matrix representation $...
codeing_monkey's user avatar
5 votes

Can Edge Belong to a cycle if it is part of multiple BFS products

As Yuval pointed out, there is some ambiguity of the original exercise as the enqueueing order of the neighbors of a node is not stipulated by the definition of a breadth-first-search (BFS). ...
John L.'s user avatar
  • 39.1k
4 votes

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

In non-weighted graphs it is not possible that in the following graph the shortest path from A to C goes via B. ...
trincot's user avatar
  • 140
4 votes
Accepted

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

As you have noticed, the requirement of vertices in a path being distinct introduces significant difficulty and obstacle against an efficient algorithm. That requirement has far-reaching impact both ...
John L.'s user avatar
  • 39.1k
3 votes
Accepted

An efficient way to find a pair of unrelated edges

This 2015 paper by Williams et al. considers induced subgraphs and shows how to find $C_4$ and co-$C_4$ in a graph $G$ time $O(\min\{n^\omega, m^{\frac{4\omega-1}{2\omega+1}}\})$, where $n$, $m$ are ...
Steven's user avatar
  • 29.5k
3 votes
Accepted

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$

The statement is false. Take a look at the following graph: In one BFS run, you will get the following tree: That has a distance of $1$ between $u$ and $v$, while in a different run, you could get ...
nir shahar's user avatar
  • 11.6k
3 votes
Accepted

Meaning of source here

In that context source is just a way to give a specific name to the vertex $s$. It makes sense to use that word since it is the vertex from which all shortest-paths computed using BFS emanate.
Steven's user avatar
  • 29.5k
3 votes
Accepted

Can Edge Belong to a cycle if it is part of multiple BFS products

Let's show first that such an edge might belong to a cycle, by considering the case of a square $ab,bc,cd,da$. We will show that $ab$ could belong to BFS trees starting at arbitrary vertices. This is ...
Yuval Filmus's user avatar
2 votes
Accepted

Number of sentences and sentential forms generated by a grammar

If the context-free grammar is unambiguous, you can count the number of sentences it generates in a linear scan with a carefully chosen order. I'll assume we have removed all useless symbols and ...
D.W.'s user avatar
  • 162k
2 votes
Accepted

Algorithm for finding strongest connection for a user on social network

Your algorithm doesn't work. BFS doesn't explore all paths. One of the paths you haven't explored might have much higher strength than all the ones you have explored. There exists a counterexample ...
D.W.'s user avatar
  • 162k
2 votes
Accepted

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

When we want to design an algorithm, we mainly consider how our data is organized. When we model a problem with graph for example, the things we could do are restricted to this specified model. For ...
Omid Yaghoubi's user avatar
2 votes
Accepted

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

I think this is best handled by contacting the lecturer, but here are four reasons. A Kain0_0 remarks, your solution is recursive, while his isn't. Didactic considerations behind this might be: ...
reinierpost's user avatar
  • 5,738
2 votes
Accepted

Connectivity in Directed Graph

The problem that you stated is known as the Graph Reachability Query problem. You may want to check this paper: An Efficient Algorithm for Answering Graph Reachability Queries, and the references ...
Inuyasha Yagami's user avatar
2 votes

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

It's true, time complexity for a single tree doesn't make sense. Aysmptotic notations are used to get bounds of how the algorithm scales in terms of its input size. The usual time complexity for BFS ...
Rinkesh P's user avatar
  • 1,024
2 votes

Special arcs - graph traversal

Run BFS from source vertex $s$ to find length of shortest path from $s$ to all other vertices in $O(V+E)$. After than, traverse all edges $(u,v)$, let $d[u]$ be shortest distance of vertex $u$ from $s$...
ErroR's user avatar
  • 1,942
2 votes
Accepted

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

One-line takeaway: a tree has either one center or two adjacent centers, which are shared by all diameters. The clue to solve the problem faster is sort of hidden in the symmetric tree given in the ...
John L.'s user avatar
  • 39.1k
2 votes

Find best path in an alternating graph

Here's a hint: explicitly create the "mirror graph", and then you redirect all the edges so that the destination is in the other graph. Also, add the edges $vv'$ (and vice versa) where $v'$ ...
Pål GD's user avatar
  • 16.7k
1 vote
Accepted

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

Answer to question 1: I am not sure how the version of BFS with iterators would work. But it's also not clear why you would want to do that -- if you are after $O(V)$ space, the original algorithm ...
Tomek Czajka's user avatar
1 vote
Accepted

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

Let $r$ be an arbitrary root. Denote by $d(v)$ the distance from $r$ to $v$. As you might know, every edge goes either between vertices of the same layer, ie, vertices of same $d(v)$, or between ...
Pål GD's user avatar
  • 16.7k
1 vote
Accepted

Correctness of bft resulting in shortest path

The contradiction is that we're assuming the first time we've seen $w$ is through the node we're expanding, $v$. However, if there were a shorter path, then the second-to-last node in that path must ...
BlueRaja - Danny Pflughoeft's user avatar
1 vote
Accepted

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

Yes. You can imagine that instead of pop one node at a time, you can pop all nodes. Then enqueue all unvisited nodes that connected from one of the popped nodes. This imagination does not change the ...
John L.'s user avatar
  • 39.1k
1 vote

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

One way to see the similarities between BFS and DFS is to consider them as the same algorithm (or perhaps some sort of "meta algorithm"), but using a different underlying data-structure: BFS ...
Discrete lizard's user avatar
  • 8,303
1 vote

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

To keep it short and simple, the answer is yes. BFS, in addition to the set of visited nodes, makes use of queue for unprocessed ...
Aarush Aggarwal's user avatar
1 vote

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

In the case of the binary tree, and assuming your binary tree is balanced, yes, I think you will be using more space at any given time in general with BFS. DFS would be allocating and releasing memory ...
Carlos R.F.'s user avatar
1 vote

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

I think it is possible by rescaling the in-order index to what it would be in a complete and full (perfect) tree, i.e. $perfect\_index = index*\frac{ceil_2(size + 1)}{size}$ where $ceil_2(arg)$ ...
Adriaan Jacobs's user avatar
1 vote

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

To the extent of my knowledge, applying BFS on a graph (directed or undirected), starting from the "source" node and visiting only nodes that we can reach using the BFS (that is, we don't ...
nir shahar's user avatar
  • 11.6k
1 vote

How does BFS guarantee the minimum path for this problem?

BFS (or Breadth-First Search) from its name implies that it will search for the destination along the breadth. That means it looks at all the current possible routes ie nodes connected to the current ...
Abhishek Rathore's user avatar
1 vote

Shortest Path with a twist

First, your algorithm is not |V|+|E| because each node can be visited more than once. This is because at each stage of your BFS, there is not greedy to always visit the optimal next node. If you are ...
timg's user avatar
  • 234
1 vote

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

First of all your question is quite confusing: There is at least one edge $w \in V$ Is it an edge or a vertex? Maybe it would be easier for you to look at some edge $(u,v) \in E$ and think about the ...
Jan Chomiak's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible