DFS

Dfs

# Depth First Search: DFS Algorithm

# 1) Pick any node. 
# 2) If it is unvisited, mark it as visited and recur on all its 
#    adjacent (neighbours) nodes. 
# 3) Repeat until all the nodes are visited

graph= {
    'A' : ['B','C'],
    'B' : ['D', 'E'],
    'C' : ['F'],
    'D' : [],
    'E' : ['F'],
    'F' : []
    }
visited = set() # Set to keep track of visited nodes of graph.

def dfs(visited, graph, node):  #function for dfs 
    if node not in visited:
        ''' 
        We start with A
        Then B
        Then D
        Then E
        Then F
        Then C
        A -> B -> D -> E -> F -> C
        '''
        print(node)
        # added to visited to avoid visit the node twice 
        visited.add(node)
        for neighbour in graph[node]:
            ''' 
            * Neighbour of A : B and C but first visit B
            * Then neighbour of B : D and E but first visit D 
            * Then neighbour of D : doesn't have neighbour then backtrack to the neighbour
                of the previous node (B) which is E
            * Then neighbour of E : F
            * Then neighbour of F : doesn't have neighbour then backtrack to the neighbour 
                of the previous node E but doesn't have other neighbour except F which is visited
                So backtracking again to B and B also doesn't have nodes not visited 
                So backtracking again to A: C not visited YAY!
            '''
            dfs(visited, graph, neighbour)
    
print(dfs(visited, graph, 'A'))

DFS explained

 def depth_first_search(graph):
    visited, stack = set(), [root]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(graph[vertex] - visited)
    return visited

Source: brilliant.org

DFS explained

Initialize an empty stack for storage of nodes, S.
For each vertex u, define u.visited to be false.
Push the root (first node to be visited) onto S.
While S is not empty:
    Pop the first element in S, u.
    If u.visited = false, then:
        U.visited = true
        for each unvisited neighbor w of u:
            Push w into S.
End process when all nodes have been visited.

Source: brilliant.org

DFS

print("found ans")

-3

Source: purdue.brightspace.com

Similar codes

0 vote215 views1 answer
Record audio with processing python
Python
0 vote206 views1 answer
Can you use the astro a50 with a phone
Python
5 votes206 views2 answers
Combining list of list to single list python
Python
0 vote211 views1 answer
Access CSV Files in Google Colab
Python
0 vote217 views1 answer
Python parse /etc/resolv.conf
Python
0 vote165 views1 answer
Error: getaddrinfo ENOTFOUND www.python.org www.python.org:443 Downloading Python failed. Error: { Error: getaddrinfo ENOTFOUND www.python.org www.python.org:443
Python
18 votes222 views5 answers
Discord.py get user input
Python
0 vote224 views1 answer
Convert string input into a nested tuple in python
Python
1 vote211 views2 answers
Delete the content from the entry form in tkinter python
Python
0 vote192 views1 answer
Tags['tag'].value_counts()
Python