Depth First Search (DFS)

Time Complexity: O(V+E) where V is number of vertices in the graph and E is number of edges in the graph.

DFS "is an algorithm for traversing or searching tree data structure. One starts at the root and explores as far as possible along each branch before backtracking.

DFS Traversal of a Graph vs Tree

In the graph, there might be cycles and disconnectivity. Unlike the graph, the tree does not contain a cycle and are always connected. So DFS of a tree is relatively easier. We can simply begin from a node, then traverse its adjacent (or children) without caring about cycles. And if we begin from a single node (root), and traverse this way, it is guaranteed that we traverse the whole tree as there is no dis-connectivity,

DFS Traversal Types

Pre-order [Root, Left, Right]
In-order [Left, Root, Right]
Post-order [Left, Right, Root]

Pre-order

The result for this algorithm will be 1--2--3--4--5--6--7.

Print the value of the node.
Go to the left child and print it. This is if, and only if, it has a left child.
Go to the right child and print it. This is if, and only if, it has a right child.

def pre_order(self):
    print(self.value)

    if self.left_child:
        self.left_child.pre_order()

    if self.right_child:
        self.right_child.pre_order()

In-order

The result of the in-order algorithm for this tree example is 3--2--4--1--6--5--7.

The left first, the middle second, and the right last.

def in_order(self):
    if self.left_child:
        self.left_child.in_order()

    print(self.value)

    if self.right_child:
        self.right_child.in_order()

Go to the left child and print it. This is if, and only if, it has a left child.
Print the node's value
Go to the right child and print it. This is if, and only if, it has a right child.

Post-order

The result of the post order algorithm for this tree example is 3--4--2--6--7--5--1.

The left first, the right second, and the middle last.

def post_order(self):
    if self.left_child:
        self.left_child.post_order()

    if self.right_child:
        self.right_child.post_order()

    print(self.value)

Go to the left child and print it. This is if, and only if, it has a left child.
Go to the right child and print it. This is if, and only if, it has a right child.
Print the node's value

Algorithm for DFS in a graph

DFS(to visit a vertex v)

Mark v as visited
Recursively visit all unmarked vertices w adjacent to v

Non-Recursive

public void dfs(Graph G, int v) {
    Stack<Integer> stack = new Stack<Integer>();
    stack.push(v);
    while(!stack.isEmpty()) {
        v = stack.pop();
        marked[v] = true;
        for (int w : G.adj(v)) {
            if (!marked[w])
                stack.push(w);
        }
    }
}

Properties

DFS marks all vertices connected to s in time proportional to the sum of their degrees.
After DFS, we can find vertices connected to s in constant time and can find a path to s (if one exists) in time proportional to its length.

Union-Find vs DFS

The union-find algorithm is best suited for situations where the equivalence relationship is changing, i.e., there are "Union" operations which need to be performed on your set of partitions. Given a fixed undirected graph, you don't have the equivalence relationships changing at all - the edges are all fixed. OTOH, if you have a graph with new edges being added, DFS won't cut it. While DFS is asymptotically faster than union-find, in practice, the likely deciding factor would be the actual problem that you are trying to solve.

Static graph - DFS

Dynamic graph - Union-find