Skip to main content
Code Review

Return to Answer

added 109 characters in body
Source Link
Chaos
Chaos
  • 201
  • 1
  • 4

I've assumed here the OP is performing DFS on undirected graphs - if not only my second point is valid.

There are several other answers here suggesting better coding practices and more efficient implementations, but they're missing the biggest problem with you code: it doesn't perform depth first search!

To demonstrate this run it with the graph created by:

Graph g;
g.addEdge(0, 1);
g.addEdge(1, 3);
g.addEdge(1, 2);
g.addEdge(4, 3);
g.addEdge(3, 5);

This outputs 0 1 3 5 2 4. This is wrong. 4 is part of the 3 branch so should be explored before the program backtracks and explores 2. The bug here is in the addEdge() function which makes w reachable from v but does not make v reachable from w. You need to add adj[w].push_back(v);.

The other issue with your code is that it will explore nodes which aren't attached to the rest of the graph (try adding g.addEdge(20, 21);. DFS shouldn't be able to get to these nodes but can anyway). The root problem here is your DFS() function, which starts a new depth first search every time it finds an unvisited i. This loop should not exist. Instead your program should have a parameter for where the depth first search should start, eg: 0, and go straight to the functionality in DFSUtil().

There are several other answers here suggesting better coding practices and more efficient implementations, but they're missing the biggest problem with you code: it doesn't perform depth first search!

To demonstrate this run it with the graph created by:

Graph g;
g.addEdge(0, 1);
g.addEdge(1, 3);
g.addEdge(1, 2);
g.addEdge(4, 3);
g.addEdge(3, 5);

This outputs 0 1 3 5 2 4. This is wrong. 4 is part of the 3 branch so should be explored before the program backtracks and explores 2. The bug here is in the addEdge() function which makes w reachable from v but does not make v reachable from w. You need to add adj[w].push_back(v);.

The other issue with your code is that it will explore nodes which aren't attached to the rest of the graph (try adding g.addEdge(20, 21);. DFS shouldn't be able to get to these nodes but can anyway). The root problem here is your DFS() function, which starts a new depth first search every time it finds an unvisited i. This loop should not exist. Instead your program should have a parameter for where the depth first search should start, eg: 0, and go straight to the functionality in DFSUtil().

I've assumed here the OP is performing DFS on undirected graphs - if not only my second point is valid.

There are several other answers here suggesting better coding practices and more efficient implementations, but they're missing the biggest problem with you code: it doesn't perform depth first search!

To demonstrate this run it with the graph created by:

Graph g;
g.addEdge(0, 1);
g.addEdge(1, 3);
g.addEdge(1, 2);
g.addEdge(4, 3);
g.addEdge(3, 5);

This outputs 0 1 3 5 2 4. This is wrong. 4 is part of the 3 branch so should be explored before the program backtracks and explores 2. The bug here is in the addEdge() function which makes w reachable from v but does not make v reachable from w. You need to add adj[w].push_back(v);.

The other issue with your code is that it will explore nodes which aren't attached to the rest of the graph (try adding g.addEdge(20, 21);. DFS shouldn't be able to get to these nodes but can anyway). The root problem here is your DFS() function, which starts a new depth first search every time it finds an unvisited i. This loop should not exist. Instead your program should have a parameter for where the depth first search should start, eg: 0, and go straight to the functionality in DFSUtil().

Source Link
Chaos
Chaos
  • 201
  • 1
  • 4

There are several other answers here suggesting better coding practices and more efficient implementations, but they're missing the biggest problem with you code: it doesn't perform depth first search!

To demonstrate this run it with the graph created by:

Graph g;
g.addEdge(0, 1);
g.addEdge(1, 3);
g.addEdge(1, 2);
g.addEdge(4, 3);
g.addEdge(3, 5);

This outputs 0 1 3 5 2 4. This is wrong. 4 is part of the 3 branch so should be explored before the program backtracks and explores 2. The bug here is in the addEdge() function which makes w reachable from v but does not make v reachable from w. You need to add adj[w].push_back(v);.

The other issue with your code is that it will explore nodes which aren't attached to the rest of the graph (try adding g.addEdge(20, 21);. DFS shouldn't be able to get to these nodes but can anyway). The root problem here is your DFS() function, which starts a new depth first search every time it finds an unvisited i. This loop should not exist. Instead your program should have a parameter for where the depth first search should start, eg: 0, and go straight to the functionality in DFSUtil().