4 ms·
1) 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 travers
by inetknght 6y ago
1) 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.