# Tag Info

Accepted

### What don't I understand in topological sort using DFS?

Main misunderstanding is when nodes are added to the answer - you add them when you leave them, right before/at backtracking So you check A, check C, find that C is terminal - so you add C at the end ...
• 225

### Genetic algorithms applied to topological orderings of a DAG

There is no one correct answer. You may have to try different possibilities and see how well they work. One candidate mutation operation is the following: pick a random pair of adjacent nodes (i.e., ...
• 161k

• 15.8k
1 vote

### Why compute finish time in topological sort

I guess the algorithm you presented is from CLRS. You are right that the finishing time is not necessary for the algorithm to work. Once the vertex is completely explored (all its neighbors are ...
• 2,780
1 vote
Accepted

### Topological sort and finding longest path in DAG to solve a stacking boxes variation (no rotation)

The topological order is not guaranteed to be a solution. Indeed the topological order clearly has length $n$ while there are instances in which it is not possible to stack all boxes. As an example ...
• 29.5k
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

### Valid orderings for topological sort

A source is a vertex with in-degree zero. An order of the vertices is a topological order if deleting the vertices in that order deletes only sources. Hence, you can verify that an order is ...
• 16.7k
1 vote

### Valid orderings for topological sort

You can answer your own question by checking whether, for each edge $(u,v)$ of the graph, $u$ appears before $v$ in each of the three candidate topological orders that you listed.
• 29.5k
1 vote

### Ordering of operations in a DAG of git commits

Assuming I understand the semantics: You cannot concurrently Create the same bug report twice, so that's not a problem Title could be a Last-Writer-Wins (LWW) register. If two users perform SetTitle ...
• 11

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