BFS & DFS

Posted on | In , |
  • Running time complexity: O(V + E)
  • Memory complexity is not good as we have to sort lots of references. That is why DFS is usually preferred.
  • But it constructs a shortest path: Dijkstra algorithm does a BFS if all the edge weights are equal to one.
  • We have an empty queue at the beginning and we keep checking whether we have visited the given node or not. Keep iterating until queue is not empty. Applications
  • In artificial intelligence / machine learning it can prove to be very important, robot can discover the surrounding more easily with BFS than DFS.
  • It is also important in maximum flow, Edmonds-Karp algorithm uses BFS for finding augmenting paths.
  • Serialization / deserialization of a tree like structure, when order does matter, it allows the tree to be reconstructed in an efficient manner.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Node(object):

    def __init__(self, name):
        self.name = name
        self.adjacencyList = []
        self.visited = False
        self.prodecessor = None


class BreadthFirstSearch(object):

    def bfs(self, startNode):

        queue = []
        queue.append(startNode)
        startNode.visited = True

        # BFS --> queue
        # DFS --> stack BUT usually implement it with recursion
        while queue:

            actualNode = queue.pop(0)
            print(actualNode.name)

            for n in actualNode.adjacencyList:
                if not n.visited:
                    n.visited = True
                    queue.append(n)


node1 = Node('A')
node2 = Node('B')
node3 = Node('C')
node4 = Node('D')
node5 = Node('E')

node1.adjacencyList.append(node2)
node1.adjacencyList.append(node3)
node1.adjacencyList.append(node4)
node1.adjacencyList.append(node5)

bfs = BreadthFirstSearch()
bfs.bfs(node1)
  • Depth-first search is a widely used graph traversal algorithm besides breadth-first search.
  • It explores as far as possible along each branch before backtracking.
  • Time complexity: O(V + E)
  • Memory complexity: slightly better than BFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Node(object):

    def __init__(self, name):
        self.name = name
        self.adjacencyList = []
        self.visited = False
        self.predecessor = None


# DFS --> stack(os level) goes as deep as possible
# BFS --> queue, layer by layer
class DepthFirstSearch(object):

    def dfs(self, node):

        node.visited = True
        print(node.name)

        for n in node.adjacencyList:
            if not n.visited:
                self.dfs(n)


node1 = Node('A')
node2 = Node('B')
node3 = Node('C')
node4 = Node('D')
node5 = Node('E')

node1.adjacencyList.append(node2)
node1.adjacencyList.append(node3)
node1.adjacencyList.append(node4)
node1.adjacencyList.append(node5)

dfs = DepthFirstSearch()
dfs.dfs(node1)

GeeksforGeeks

Breadth First Search or BFS for a Graph
Depth First Search or DFS for a Graph
BFS vs DFS for Binary Tree
Algorithm Questions

0%