图的dfs框架

[zyune]

// 记录被遍历过的节点
boolean[] visited;
// 记录从起点到当前节点的路径
boolean[] onPath;

/* 图遍历框架 */
void traverse(Graph graph, int s) {
    if (visited[s]) return;
    // 经过节点 s，标记为已遍历
    visited[s] = true;
    // 做选择：标记节点 s 在路径上
    onPath[s] = true;
    for (int neighbor : graph.neighbors(s)) {
        traverse(graph, neighbor);
    }
    // 撤销选择：节点 s 离开路径
    onPath[s] = false;
}

[zyune]

visited = [False for node in graph]
onPath = [False for node in graph]

def traverse(graph, s):  # graph 题目输入的test case的图，s是当前的节点
    if visited[s]:
        return
    # 经过节点 s，标记为已遍历
    visited[s] = True
    # 做选择：标记节点 s 在路径上
    onPath[s] = True
    for node in graph[s]:  # 递归遍历s node所有的neighbour node
        traverse(graph, s)
    # 撤销选择：节点 s 离开路径
    onPath[s] = false