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.
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.
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).
Not using data structures that enable concurrency prevents performance improvements since modern hardware is, in general, more parallel than vertical.