I was wondering how to go about solving a problem with disconnected graphs and depth-first search. Here is an example of a disconnected graph.
How would I go through it in DFS?
My current reasoning is by going down the left most subtree, as you would with a BST, so assuming that the node 5 is the start, the path would be: [5, 1, 4, 13, 2, 6, 17, 9, 11, 12, 10, 18].
On
DFS can be used to solve the connectivity problem. You continue to run it on different components until the entire graph is "discovered". Under any case, it does not take longer than $V+E$.
if none of the edges are connected, then you will simply run DFS on every vertice until you discover your graph is disconnected.
On
Normally, running DFS (by taking the left-most node first) would stop after visiting node 6. The visiting order that you describe
[5, 1, 4, 13, 2, 6, 17, 9, 11, 12, 10, 18]
would happen if the two trees where connected through a root. Imagine a new node (let's call it 3) which is the parent of 5 and 17. Now re-run DFS. You would get
[3, 5, 1, 4, 13, 2, 6, 17, 9, 11, 12, 10, 18]
If you use DFS for traversal reasons, say because you want to make some transformation to each node of the graph, since node 3 is a superficial one that you added, you have to handle that node exceptionally. However, usually, nodes of a graph are given as a list or as integers (which are the indexes in $v_i$). Then you can visit (and apply any transformations on) all nodes just by traversing that list or by using the integers successively to refer to all of your nodes.
If you use DFS for path-finding reasons, then it makes no sense to try to connect the two components. The results will be wrong.
This link should answer your question. In fact, DFS is often used to determine whether or not a graph is disconnected or not - if we run DFS and do not reach all of the nodes in the graph, the graph must be disconnected. Hope that helps!