CODEWITHSUNDEEP
depth-first-searchundirected-graph
User
User

Reputation: 1726

Proper traversal of undirected graph using depth first search?

I've got an undirected graph that I need to traverse using depth first search.

The excel chart below shows each node has been marked after traversal in the marked column, and the edgeTo column shows which node brought us to that node. For example, we got to node 1 from node 5, we got to node 2 from node 7, etc.

My question is for node 6 and 8, since they are separated from the main graph, how do I properly traverse it? My guess is that I start at 6 and go to 8, but since 6 will already have been visited at that point, I do not go back to 6 from 8. Hence row 6 is left blank in the edgeTo column.

Am I correct? Is my chart correct?

Upvotes: 0

Views: 242

Answers (1)

FrankS101
FrankS101

Reputation: 2135

Depth first search is basically used to find a path between two nodes in a graph. The graph of your example is disconnected, i.e. there exist two nodes in your graph such that no path in your graph has those nodes as endpoints.

6 and 8 are obviously nodes that belong to a different subgraph and therefore you can't find a path between 0 and 8 and the DFS will return IMPOSSIBLE or No path found. Apart from that your chart is correct.

Upvotes: 1

Related Questions