CODEWITHSUNDEEP
algorithmgraphdepth-first-search
ekeith
ekeith

Reputation: 644

Performing Depth-First Traversal on a vertex with no edges connected

I'm trying to translate an Adjacency matrix to a directed graph and perform a DFS on the graph. adjacency matrix

Here is the graph I came up with. enter image description here

The traversal starts from vertex A and E is not connected by any other vertex, I don't understand what is going to happen to E , in the sense that how does DFS help traverse it?

Upvotes: 0

Views: 1764

Answers (2)

user2357112
user2357112

Reputation: 280281

A depth-first search starting (only) from A will simply not find E.

If an algorithm based on depth-first search needs to traverse every node of a graph that might not be strongly connected, it usually launches depth-first searches from every node of the graph in sequence, with all such depth-first searches sharing a single frontier set so nodes aren't re-explored.

Upvotes: 3

templatetypedef
templatetypedef

Reputation: 372714

DFS just won't traverse the node E if you start at A. DFS has the nice property that if you run a DFS starting at some node v, it will visit every node reachable from v and none of the other nodes in the graph, so it can actually be used to determine what's reachable from a starting node.

Depending on what you're trying to do, this may or may not be a bad thing. If your goal was to find all the nodes in the graph, you'll need to change strategies.

Upvotes: 3

Related Questions