Implement Depth-First Search (DFS) Graph Algorithm in Python using Loop

Author: Al-mamun Sarkar Date: 2020-03-29 20:09:09

Implement the Depth-First Search (DFS) Graph Algorithm in Python using Loop. The following code shows how to implement the Depth-First Search (DFS) Algorithm in the Python programming language.

Code:

class Graph:
    def __init__(self, graph):
        self.graph = graph
        self.visited_node = []
        self.stact = []

    def dfs(self, node):
        self.stact.append(node)
        while self.stact:
            vertex = self.stact.pop()
            if vertex not in self.visited_node:
                self.visited_node.append(vertex)
                self.stact.extend([item for item in graph[vertex]])
        return self.visited_node


graph = {
    'A': {'B', 'C'},
    'B': {'A', 'D', 'E'},
    'C': {'A', 'F'},
    'D': {'B'},
    'E': {'B', 'F'},
    'F': {'C', 'E'}
}

g = Graph(graph)
print(g.dfs('A'))

 

Output:

['A', 'B', 'E', 'F', 'C', 'D']