“DFS Python” Ответ

DFS Python

# Python program to print DFS traversal for complete graph
from collections import defaultdict
  
# This class represents a directed graph using adjacency
# list representation
class Graph:
  
    # Constructor
    def __init__(self):
  
        # default dictionary to store graph
        self.graph = defaultdict(list)
  
    # function to add an edge to graph
    def addEdge(self,u,v):
        self.graph[u].append(v)
  
    # A function used by DFS
    def DFSUtil(self, v, visited):
  
        # Mark the current node as visited and print it
        visited[v]= True
        print v,
  
        # Recur for all the vertices adjacent to
        # this vertex
        for i in self.graph[v]:
            if visited[i] == False:
                self.DFSUtil(i, visited)
  
  
    # The function to do DFS traversal. It uses
    # recursive DFSUtil()
    def DFS(self):
        V = len(self.graph)  #total vertices
  
        # Mark all the vertices as not visited
        visited =[False]*(V)
  
        # Call the recursive helper function to print
        # DFS traversal starting from all vertices one
        # by one
        for i in range(V):
            if visited[i] == False:
                self.DFSUtil(i, visited)
  
  
# Driver code
# Create a graph given in the above diagram
g = Graph()
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)
  
print "Following is Depth First Traversal"
g.DFS()
  
# This code is contributed by Neelam Yadav
Testy Tarsier

DFS -алгоритм Python

# 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'))
Bacem OBEY

Ответы похожие на “DFS Python”

Вопросы похожие на “DFS Python”

Больше похожих ответов на “DFS Python” по Python

Смотреть популярные ответы по языку

Смотреть другие языки программирования