3 ms·
1) If it‘s a tree, it ain‘t got no loops 2) The stack isn‘t to deal with loops, the „visited“ flag at each edge is there for that. The stack (for DFS, BFS would
by red0point 6y ago
1) If it‘s a tree, it ain‘t got no loops
2) The stack isn‘t to deal with loops, the „visited“ flag at each edge is there for that. The stack (for DFS, BFS would be a queue) is there to keep track of which nodes have been visited such that you can construct a path from the starting node to the one you‘re looking for.
Obviously there are variants to this, depending on what you‘re actually trying to achieve with it. My point is that a stack would be a very inefficient way to deal with loops.
- inetknght 6y ago1) you're right, I edited my message to reflect that I meant a graph traversal algorithm. 2) a visited flag on an edge? That won't support simultaneous traversals. Keeping a stack is a lot more efficient than permitting only one traversal at a time.
- red0point 6y agoI‘m not sure why you‘re bringing concurrency to the table. My point still is that looking something up in a stack (did I visit this node?) costs O(n) time, so the BFS will degrade from O(m+n) to O(m*n+n). To come back to the concurrency, if you can index your edges in some way, you can also store the visited flag in a separate datastracture to support concurrent access (one „flag store“ for each access).
- inetknght 6y ago> I‘m not sure why you‘re bringing concurrency to the table. Not using data structures that enable concurrency prevents performance improvements since modern hardware is, in general, more parallel than vertical.
- hinkley 6y agoModifying the graph turns it into shared (mutable) state. Your code is still re-entrant, but it's no longer concurrent.