Note: In binary trees, DFS traversals can be further categorised as Preorder, Postorder, and Inorder.
Note that the implementation of DFS does require adjustments depending on whether the graph is
directed or undirected.
In a directed graph, edges are unidirectional, so an edge from A to B doesn't imply an edge from B to A.
Thus, the adjacency list or matrix reflects only the defined direction.
In an undirected graph, every edge is bidirectional. When you add an edge between two nodes, both nodes
link to each other. For instance, if there's an edge between A and B, both A → B and B → A are
implicitly available.
Detecting cycles in directed graphs requires additional handling, such as tracking nodes in the current
recursion stack (or marking nodes as "in progress") since back edges can indicate a cycle.
In an undirected graph, cycles can be detected by checking for nodes already visited, with one added step
to ensure we aren't mistaking the parent node (the node that directed us here) as part of a cycle.
DFS on a weighted graph operates the same as it would in an unweighted graph in terms of basic
traversal, simply checking reachability from one node to another. The weights on edges don't influence the
traversal order, as DFS doesn't consider edge costs; it explores along any available path.
For tasks that require evaluating edge weights, like finding the shortest path or constructing a Minimum
Spanning Tree, specialized algorithms such as Dijkstra,
Bellman-Ford, Prim, and
Kruskal are more appropriate.