DFS without skipping visited nodes python

Question

I am writing following code to realize dfs without skipping visited nodes. With the following example graph, using a as root. the first branch could be a-b-c-d. then traverse another branch of b, b-d. then traverse another branch of a, a-d, then a-e. The shape of this tree should be To end the loop, I will use depth. e.g. if depth equals to 3, then a tree branch has at most 3 nodes. There is an example graph:

G = {'a': set(['d','b','e']),
     'b': set(['a', 'c', 'd']),
     'c': set(['b','d']),
     'd': set(['a','b','c']),
     'e': set(['a'])}

with depth equals 3, a as the start, my expected result is a b c d d d c e.
I have tried for a while but no luck. Here is my current code:

def depth_first_search(graph, start,maxdepth):
    depth={start:0}
    visited, stack = set(), [start]
    while stack:
        vertex = stack.pop()
        print(vertex)
        if depth[vertex]==maxdepth:
           break
        # if vertex not in visited:
        #     visited.add(vertex)
        #    for neighbor in set(graph[vertex]-visited):
        for neighbor in graph[vertex]:
                # if neighbor in depth:
                #      continue
                stack.extend(neighbor)
                depth[neighbor]=depth[vertex]+1
    return depth

user_11393144 · Answer

Since nobody till now answer my question. I would like to post mine that I figure out recently. different thoughts are welcomed.

def buildtree_draft(G,k):
    remove=[]
    if len(G) <= 2:
        return
    else:
        for node in list(G.nodes()):
            remove.append(node)
            for node1 in list(G.neighbors(node)):
                set1=set([node,node1])
                li.append(set1)
                for item in li:
                    if item not in result:
                        result.append(item)
                for node2 in list(G.neighbors(node1)):
                    if node2==node:
                        continue
                    else:
                        set2=set([node,node1,node2])
                        li.append(set2)
                        for item in li:
                            if item not in result:
                                result.append(item)
            G.remove_nodes_from(remove)

DFS without skipping visited nodes python

1 Answers