Graph DFS

题目描述

解题方法

use stack

Solution

visited = {}

def dfs(nodes):
    stack = []
    stack.append(rootNode)
    visited[rootNode] = True
    # print rootNode
    while stack:
        cur = stack[-1] # not pop!
        child = getUnivisitedChildNode(cur)
        if child:
            visited[child] = True
            print child
            stack.append(child)
        else: # all neighbors are visited
            stack.pop()

def getUnivisitedChildNode(node):
    for nb in node.neighbors:
        if nb not in visited:
            return nb

recursive

def dfs(v):
    visited = {}
    dfs_helper(v, visited)

def dfs_helper(v, visited):
    visited[v] = True
    while v.hasNext():
        n = i.next()
        if n not in visited: # 要没有visit过的
            dfs_helpert(n, visited)

Reference