The tag has no usage guidance.

13 questions
Filter by
Sorted by
Tagged with
73 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 ...
23 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 ...
53 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 ...
32 views

### more than one min cut in a net flow

I know the answer to the question, but I still can't understand. I have the max flow and I need to determine whether there is more than one min-cut. I know that I need to run BFS from s in the ...
63 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 ...
24 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$ ...
100 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 ...
38 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....
23 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. ...
39 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 ...
57 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 ...