10 examples of 'iterative dfs' in Python

26
def dfs(self, root, ls, res):
27
    if not root.left and not root.right:
28
        res.append(ls + str(root.val))
29
    if root.left:
30
        self.dfs(root.left, ls + str(root.val) + "->", res)
31
    if root.right:
32
        self.dfs(root.right, ls + str(root.val) + "->", res)

14
def DFS(path, visited, res):
15
    if len(path) == N:
16
        res += [cal_V(path)]
17
        return
18
    for i in xrange(N):
19
        if not visited[i]:
20
            if i>0 and not visited[i-1] and Y[i] == Y[i-1]:
21
                continue
22
            visited[i] = True
23
            DFS(path + [Y[i]], visited, res)
24
            visited[i] = False

26
def dfs(self, node, level, res):
27
    if node:
28
        if level > len(res): res.insert(0,[])
29
        res[-level].append(node.val)
30
        self.dfs(node.left, level+1, res)
31
        self.dfs(node.right,level+1, res)
32
        return res

11
def DFSrecur(self,s,visited):
12
	visited[s] = True
13
	print(s , end=" ")
14
	for i in self.graph[s]:
15
		if visited[i] == False:
16
			self.DFSrecur(i,visited)

77
def dfs(x):
78
    if x.is_leaf:
79
        yield x
80
    else:
81
        for x in order.val:
82
            if x == 'l':
83
                yield from dfs(x.lson)
84
            elif x == 'n':
85
                yield x
86
            elif x == 'r':
87
                yield from dfs(x.rson)

1
def dfs(self):
2
    """
3
    Computes the initial source vertices for each connected component
4
    and the parents for each vertex as determined through depth-first-search
5
    :return: initial source vertices for each connected component, parents for each vertex
6
    :rtype: set, dict
7
    """
8
    parents = {}
9
    components = set()
10
    to_visit = []
11
12
    for vertex in self.get_vertex():
13
        if vertex not in parents:
14
            components.add(vertex)
15
        else:
16
            continue
17
18
        to_visit.append(vertex)
19
20
        while to_visit:
21
            v = to_visit.pop()
22
23
            for neighbor in self.get_neighbor(v):
24
                if neighbor not in parents:
25
                    parents[neighbor] = v
26
                    to_visit.append(neighbor)
27
28
    return components, parents

71
def dfs(node, k):
72
    if node in visited or not node or k < 0: return
73
    if k == 0:
74
        ans.append(node.val)
75
        return
76
    dfs(node.left, k-1)
77
    dfs(node.right, k-1)

15
def __dfs(self, candidates, size, start, path, residue, res):
16
    """
17
    :param candidates: 无重复元素的数组
18
    :param size: 数组的长度，避免一直使用 len(candidates)
19
    :param start: 从 candidates 索引的第几位开始考虑
20
    :param path: 深度优先搜索沿途经过的路径
21
    :param residue: 剩余值
22
    :param res: 存放结果集的列表
23
    :return:
24
    """
25
    if residue == 0:
26
        res.append(path[:])
27
        return
28
29
    for index in range(start, size):
30
        # 因为我们已经将数组预处理成升序数组，一旦发现当前遍历的数比剩余值还大，循环就可以停止了
31
        if residue - candidates[index] < 0:
32
            break
33
        path.append(candidates[index])
34
        # 注意：因为数字可以无限制重复被选取，因此起始位置还是自己
35
        self.__dfs(candidates, size, index, path, residue - candidates[index], res)
36
        path.pop()

33
def DFS(self, v):
34
35
    # Mark all the vertices as not visited
36
    visited = [False] * (len(self.graph))
37
38
    # Call the recursive helper function to print
39
    # DFS traversal
40
    self.DFSUtil(v, visited)

10
def DFSUtil(self,v,visited):
11
    visited[v]=True
12
    print v,
13
14
    for i in self.graph[v]:
15
        if visited[i] == False:
16
            self.DFSUtil(i, visited)