Redpill me on connected components

Is that how you check a path between two nodes exists?

Attached: Untitled.png (651x669, 105K)

>CLRS

what

DFS/BFS

Do I call it from every single node or what, isn't that like O(2^n)

>Is that how you check a path between two nodes exists?
Use a pathfinding algorithm. That's what they're for.

>Do I call it from every single node or what
No, just run it from the place you want to start.

What's a good pathfinding algorithm? BFS?

>What's a good pathfinding algorithm? BFS?
BFS is fine ( O(n) ). What you really ought to do is think carefully about the properties of the data you're going to be looking for paths in.

OP pic related is basically it, I have strings that represent zones and keys required to go through some zones.
Given a starting zone, I have to output all zones I don't have a path to.
I started dijkstra and bellman ford but it's just not working out. I\ll try BFS, thanks for the tip.

>I started dijkstra and bellman ford but it's just not working out.
Those are intended for weighted graphs.

Well aren't my weights the keys (no weight if unlocked)
So generally, is forming a set of connected components the goal?

You could always assume the weight as 1.
Terrible approach. If you have no key there shouldn't be an edge between the nodes. Only then will it work.

>there shouldn't be an edge between the nodes
That is so fucking niggerlicious. So I should just induce my graph as I gradually find keys? Won't that be pretty slow?

>Well aren't my weights the keys (no weight if unlocked)
I guess you could do it that way. It would be kind of clunky though, and it would require your keys to be strictly ordered, which is a restriction you probably don't want.

>You could always assume the weight as 1.
That's BFS.

>If you have no key there shouldn't be an edge between the nodes. Only then will it work.
Putting keys on edges is completely reasonable. With a modification of Dijkstra you could even determine all minimal sets of keys needed to travel between any pair of points.

>determine all minimal sets of keys needed to travel between any pair of points.
The point of this exercise is to find all keys, unlock all doors, and mark everything unreachable with red.

>>determine all minimal sets of keys needed to travel between any pair of points.
Yes? Keys can probably (not necessarily, but it's fairly mild restriction) be arranged into a poset, and modifying Dijkstra to operate on partially-ordered weights is totally feasible.

Well OP didn't clarify you had to find the keys, only to check the reachability. Then I'd try pre-processing the graph first by replacing paths to doors by the shortest path from the door to the key, then run any pathfinding algorithm.

this is alien to me, we've only studied BFS and DFS
ill think about this, tahnk you very much

Actually scrap that, sometimes it would be better to collect multiple keys in advance. Then BFS is the way to go.

>this is alien to me, we've only studied BFS and DFS
Partially ordered sets are really fucking neat. I'd strongly recommend reading about them.

So while there are locked, go to each unexplored zone and get each key, then unlock every locked zone?

One area could have keys to the next and to the consequent area, it would be pretty dumb to backtrack. BFS will check all those variants and everything in between. Just abort routes that reach doors without having a key to that door.

Right so first pass, no unlocks. Second pass, unlocks.
BFS works best on an adjacency list, right?

Nah, just one pass is necessary with proper checks done during the traversal.
>BFS works best on an adjacency list, right?
Doesn't matter. In your case I'd rather build a proper graph structure where you can differentiate between different kinds of nodes. Also storing the current set of keys for each path would be necessary.

Right thanks for the help a lot, i'll think about it