OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more

# Tag Info

## Hot answers tagged depth-first-search

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

• 101
Accepted

### pictorial representation of pre and post ordering for edge types

"I am assuming that $u$ is the node/vertex we see first and then we see $v$ later." That is a wrong assumption, which makes that summarizing table unintelligible. The right assumption ...
• 39k
Accepted

### Is the chalk really needed in the "chalk and string labyrinth" analogy for depth-first search?

First of all keep in mind that this is just an analogy meant to convey the intuition behind the DFS algorithm on graphs. Now graphs can be directed, which would correspond to having a labyrinth with ...
• 29.5k

• 277k
1 vote
Accepted

### DFS produces the correct Topologically ordered sequence

Before I get to the proof, let me just clarify that the algorithm using DFS would be to process edges in decreasing order of finishing times while running DFS on the input graph. Now to prove that the ...
• 285
1 vote
Accepted

### find the strong component containing the vertex v

Since you are not trying to write an optimal algorithm, like this one or that one, I suggest you do not try to optimize space usage too much, especially if the optimization only diminish the ...
• 15.7k
1 vote

### Alternatives for finding sources in a DAG

Use a priority queue to keep a list of all vertices with prioritization on in-degrees. Pop off one vertex $v$ with in-degree zero, decrement the in-degree-count of the out-neighborhood of $v$. Repeat ...
• 16.4k

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