# 深度优先搜索(DFS)小结

[TOC]

```public class GraphNode{
int val;
List<GraphNode> neighbors;
}
```

`HasheSet<GraphNode> visited = new HasheSet<GraphNode>();`

## Recursive DFS

```public void DFS(GraphNode nd){
System.out.println(nd.val);
for(GraphNode next: nd.neighbors){
if( !visited.contains(next) )
DFS(next);
}
}
```

## Non-recursive DFS

```public void DFS(GraphNode start){
Stack<GraphNode> s = new Stack<GraphNode>();
q.push(start);
while(!s.empty()){
GraphNode cur = s.pop();
System.out.println(cur.val);
for(GraphNode next: cur.children){
if(!visited.contains(next)){
s.push(next);
}
}
}//while
}
```

## DFS for binary tree: Preorder traversal

dfs另一个有用的性质是: 对于二叉树而言, dfs得到的节点顺序正是其前序遍历(preorder traversal)的顺序.

`[preorder(node)] = node.val + [preorder(node.left)] + [preorder(node.right)]`

## Cycle Detection

`HasheMap<GraphNode, Boolean> visited = new HasheMap<GraphNode, Boolean>();`

```public void DFS(GraphNode nd){
visited.put(nd, false); // mark as status-1
for(GraphNode next: nd.neighbors){
if( !visited.contains(next) )
DFS(next);
else if(visited.get(next)==false) // found cycle
System.out.println("Cycle detected!!!");
}// now all touchable nodes from nd are visited
visited.put(nd, true); // mark as status-2
}
```

## Topology Sort

propositions:

• 拓扑排序的结果不唯一.
• 有回路的图不存在拓扑顺序.
• 如果一个节点没有出边, 那么它可以放在拓扑排序的最后面(没有节点以来它).
• 如果一个节点没有入边, 那么它可以放在拓扑排序的最后面.

`HasheMap<GraphNode, Integer> order = new HasheMap<GraphNode, Integer>();`

```public void DFS(GraphNode nd){
for(GraphNode next: nd.neighbors){
if( !visited.contains(next) )
DFS(next);
}// all touchable nodes from nd are visited
order.put(nd, K--);
}
```