2020-2021:teams:namespace:kongyou:深度优先搜索
差别
这里会显示出您选择的修订版和当前版本之间的差别。
|
2020-2021:teams:namespace:kongyou:深度优先搜索 [2020/05/16 11:23] kongyou 创建 |
2020-2021:teams:namespace:kongyou:深度优先搜索 [2020/05/16 11:29] (当前版本) kongyou |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ====深度优先搜索(DFS)==== | + | =========深度优先搜索(DFS)========= |
| 过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次. | 过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次. | ||
| 行 24: | 行 24: | ||
| + | 递归实现 | ||
| + | <code c++> | ||
| + | void dfs(int v)//以v开始做深度优先搜索 | ||
| + | { | ||
| + | list<int>::iterator it; | ||
| + | visited[v] = true; | ||
| + | cout << v << " "; | ||
| + | for (it = graph[v].begin(); it != graph[v].end(); it++) | ||
| + | if (!visited[*it]) | ||
| + | dfs(*it); | ||
| + | } | ||
| + | </code> | ||
| + | |||
| + | 非递归实现（栈） | ||
| + | <code c++> | ||
| + | void dfs(int v)//以v开始做深度优先搜索 | ||
| + | { | ||
| + | list<int>::iterator it; | ||
| + | visited[v] = true; | ||
| + | cout << v << " "; | ||
| + | stack<int>mystack; | ||
| + | mystack.push(v); | ||
| + | while (!mystack.empty()) | ||
| + | { | ||
| + | v = mystack.top(); | ||
| + | mystack.pop(); | ||
| + | if (!visited[v]) | ||
| + | { | ||
| + | cout << v << " "; | ||
| + | visited[v] = true; | ||
| + | } | ||
| + | |||
| + | for (it = graph[v].begin(); it != graph[v].end(); it++) | ||
| + | { | ||
| + | if (!visited[*it]) | ||
| + | { | ||
| + | mystack.push(*it); | ||
| + | |||
| + | } | ||
| + | } | ||
| + | } | ||
| + | cout << endl; | ||
| + | } | ||
| + | </code> | ||
2020-2021/teams/namespace/kongyou/深度优先搜索.1589599422.txt.gz · 最后更改: 2020/05/16 11:23 由 kongyou
