I‘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

I‘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).