Introduction Link to heading

DFS and BFS are probably the first topics to cover when doing anything related to graphs. I started with things like Dijkstra and Prim, which could be extensions of DFS and BFS.

DFS and BFS can be used for several applications like finding the shortest path, detecting cycles, and identifying connected components.

Breadth-First Search Link to heading

Wiki says that BFS visits the nodes of a graph by visiting the neighbor nodes first, then moving to the next level of neighbors.

For implementation, a queue can be used to push the nodes being visited. As long as the queue is not empty, the traversal will keep going until there are no more nodes to enqueue or dequeue.

    def BFS(self, start):
        # Initialize queue and visited
        q = []
        visited = [False] * self.V
        # Add start node to queue and mark it visited
        q.append(start)
        visited[start] = True

        while len(q) != 0:
            current = q.pop(0)
            print(f"BFS Node {current}")
            for (n, w) in self.graph[current]:
                if visited[n] == False and (not n in q):  # The second condition
                    visited[n] = True
                    q.append(n)

Depth-First Search Link to heading

Wiki says that DFS visits nodes by going down in the graph until there are no reachable adjacent nodes. Then it backtracks to the parent node and starts iterating adjacent nodes from there.

A stack is used to store nodes in the path from the root to the current node. Again, visiting means printing the correct node at the correct time.

    def DFS(self, start):
        # Initialize stack and visited
        s = []
        visited = [False] * self.V
        s.append(start)

        while len(s) != 0:
            v = s.pop()
            if visited[v] == False:
                visited[v] = True
                print(f"DFS Node = {v}")
                for (n2, w) in self.graph[v]:
                    s.append(n2)

Putting It All Together Link to heading

class Graph:
    def BFS(self, start):
        q = []
        visited = [False] * self.V
        q.append(start)

        while len(q) != 0:
            current = q.pop(0)
            visited[current] = True
            print(f"{current}")
            for (n, w) in self.graph[current]:
                if visited[n] == False and (not n in q):
                    q.append(n)

    def getVertex(self, n, s, visited):
        for (n2, w) in self.graph[n]:
            if visited[n2] == False:
                return n2
        return None

    def DFS(self, start):
        s = []
        visited = [False] * self.V
        s.append(start)
        visited[start] = True
        print(f"DFS Node = {start}")

        while len(s) != 0:
            adjVertex = self.getVertex(s[-1], s, visited)
            print(adjVertex)
            if adjVertex is None:
                s.pop()
            else:
                visited[adjVertex] = True
                print(f"DFS Node = {adjVertex}")
                s.append(adjVertex)

class UndirectedGraph(Graph):
    def __init__(self, V):
        self.V = V
        self.graph = [[] for i in range(V)]

    def connect(self, n1, n2, w):
        self.graph[n1].append((n2, w))
        self.graph[n2].append((n1, w))

class DirectedGraph(Graph):
    def __init__(self, V):
        self.V = V
        self.graph = [[] for i in range(V)]

    def connect(self, n1, n2, w):
        self.graph[n1].append((n2, w))

def main():
    g = DirectedGraph(4)
    g.connect(1, 2, 0)
    g.connect(0, 2, 0)
    g.connect(0, 1, 0)
    g.connect(2, 0, 0)
    g.connect(2, 3, 0)
    g.connect(3, 3, 0)
    print('>>>>>>>>> BFS')
    g.BFS(2)
    print('>>>>>>>>> DFS')
    g.DFS(2)

    print('===================')
    g1 = UndirectedGraph(6)
    g1.connect(0, 1, 0)
    g1.connect(0, 2, 0)
    g1.connect(1, 4, 0)
    g1.connect(1, 3, 0)
    g1.connect(2, 4, 0)
    g1.connect(3, 4, 0)
    g1.connect(3, 5, 0)
    g1.connect(4, 5, 0)
    print('BFS')
    g1.BFS(0)
    print('DFS')
    g1.DFS(0)

if __name__ == "__main__":
    main()