Click here to Skip to main content
15,946,683 members
Please Sign up or sign in to vote.
1.00/5 (2 votes)
C#
graph = {'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])}

def dfs(graph, start):
        visited, stack = set(), [start]
        while stack:
            vertex = stack.pop(-1)
            if vertex not in visited:
                visited.add(vertex)
                print visited
                stack.extend(graph[vertex] - visited)
    return visited

dfs(graph,'A')
set(['A'])
set(['A', 'B'])
set(['A', 'B', 'D'])
set(['A', 'B', 'E', 'D'])
set(['A', 'B', 'E', 'D', 'F'])
set(['A', 'C', 'B', 'E', 'D', 'F'])
set(['A', 'C', 'B', 'E', 'D', 'F'])



I am trying to do Depth first search and I have printed the visited every time to see what is happening in the visited node. In beginning visited node seems to give correct output but after few iteration visited.add() adds the element in the middle of the set. I am not understanding why this is happening.
Posted
Updated 1-Feb-16 11:33am
v2

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900