CVBB ACM Team

--- 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>