Depth First Search algorithm.

Depth First Search use case.


A graph is a data structure that includes a set of vertices and edges. Graph traversing means a visit to each vertex of the graph, going to all the vertices of the graph without going into a loop. Depth First Search (DFS) is one of the ways to traverse the graph visiting all the vertices and edges.

Depth First Search algorithm.



In depth-first search the LIFO (Last In First Out) principle stack data structure is used. The algorithm starts at the root node (some arbitrary node), then keeps on exploring or visiting vertices till we reach a dead-end. Visited nodes are marked, then traversing all the adjacent and unmarked nodes and calling the recursive function with the index of the adjacent node. Depth-first search is considered as a non-optimal solution. Originally a depth-first search was used as a strategy for solving mazes.


Depth First Search Python code:




graph1 = {'0': set(['1', '2']),
         '1': set(['0', '3', '4']),
         '2': set(['0']),
         '3': set(['1']),
         '4': set(['2', '3'])}

def dfs(graph, node, visited):
    if node not in visited:
        visited.append(node)
        for n in graph[node]:
            dfs(graph,n, visited)
    return visited

visited = dfs(graph1,'0', [])
print(visited)

OUT: ['0', '2', '1', '3', '4']





See also related topics: