c++_csp-j算法 (1)

DFS搜索(深度优先搜索)

讲解

第一部分：DFS搜索算法简介

深度优先搜索（Depth-First Search，DFS）是一种常用的图搜索算法，用于遍历或搜索图或树的所有节点。DFS算法的焦点思想是尽可能深地搜索图的分支，直到无法再深入为止，然后回溯到上一级节点，继续搜索其他分支。DFS算法是一种递归的搜索算法，也可以用栈来实现。在现实应用中，DFS算法常用于办理图的遍历、连通性、路径搜索等标题。
1. 基本思想

DFS算法的基本思想是从图中的某一节点出发，沿着一条路径一直走到底，直到无法继续为止，然后回溯到上一个节点，继续搜索其他路径，直到所有路径都被搜索完毕。在搜索的过程中，需要标记已经访问过的节点，避免重复访问，以防止陷入无限循环。
2. 递归实现

DFS算法的递归实现是一种直观且简朴的方式。递归地访问节点的邻居节点，直到所有节点都被访问过为止。递归实现DFS的伪代码如下：

1. DFS(node):
2.     访问节点node
3.     将节点node标记为已访问
4.     for 每个邻居节点neighbor of node:
5.         if neighbor未被访问过:
6.             DFS(neighbor)

复制代码

在递归实现中，需要一个标记数组来记录节点的访问状态，防止重复访问。递归实现的优点是简朴直观，易于理解，但在处理大规模图或树时可能会出现栈溢出的标题。
3. 栈实现

为了避免递归实现中可能出现的栈溢出标题，可以使用栈来实现DFS算法。栈实现的DFS算法是一种非递归的方式，通过维护一个栈来模拟递归的过程。栈实现DFS的伪代码如下：

1. DFS(node):
2.     初始化一个栈s
3.     将起始节点node入栈
4.     将节点node标记为已访问
5.     while 栈s非空:
6.         弹出栈顶节点top
7.         访问节点top
8.         for 每个邻居节点neighbor of top:
9.             if neighbor未被访问过:
10.                 将neighbor入栈
11.                 将neighbor标记为已访问

复制代码

栈实现DFS算法的优点是可以避免递归调用的深度限制，适用于处理大规模图或树。栈实现的DFS算法通常使用一个栈来生存待访问的节点，一个标记数组来记录节点的访问状态。
4. 应用领域

DFS算法在许多领域都有偏重要的应用，包罗但不限于：

• 图的遍历：DFS算法可以用来遍历图中的所有节点，查找连通分量等。
  
• 路径搜索：DFS算法可以用来搜索图中的路径，如寻找从起始节点到目标节点的路径。
  
• 拓扑排序：DFS算法可以用来实现拓扑排序，找出有向无环图的拓扑顺序。
  
• 基因组序列分析：DFS算法可以用来在基因组序列中搜索特定的序列模式。
  

第二部分:图的表示

在盘算机科学中，图是一种非常重要的数据结构，用于表示对象之间的关系。图由节点（顶点）和边构成，节点之间的边表示节点之间的关系。在图论中，图可以分为有向图和无向图，有向图中的边是有方向的，无向图中的边是没有方向的。
图的表示有多种方式，常见的包罗邻接矩阵和邻接表。在邻接矩阵中，图的节点和边可以用二维矩阵表示，矩阵的行和列分别表示图中的节点，矩阵中的值表示节点之间的边。邻接矩阵适用于稠密图，但对于希罕图来说可能会占用较多的内存空间。而邻接表是一种更为机动的表示方式，适用于希罕图。在邻接表中，每个节点对应一个链表，链表中存储了与该节点相邻的节点，通过链表的方式表示节点之间的关系。
邻接表的实现

在C++中，可以通过结构体和链表来实现邻接表表示图的数据结构。下面是一个简朴的示例代码，展示了如何用邻接表表示图：

1. #include <iostream>
2. #include <vector>
4. using namespace std;
6. // 图的节点结构体
7. struct Node {
8.     int val;
9.     Node* next;
10.     Node(int v) : val(v), next(nullptr) {}
11. };
13. // 邻接表表示图的数据结构
14. class Graph {
15. private:
16.     int V; // 图中节点的个数
17.     vector<Node*> adjList; // 邻接表
19. public:
20.     Graph(int v) : V(v) {
21.         adjList.resize(V, nullptr);
22.     }
24.     // 添加边
25.     void addEdge(int src, int dest) {
26.         Node* newNode = new Node(dest);
27.         newNode->next = adjList[src];
28.         adjList[src] = newNode;
30.         // 无向图的话，需要添加反向边
31.         newNode = new Node(src);
32.         newNode->next = adjList[dest];
33.         adjList[dest] = newNode;
34.     }
36.     // 打印邻接表
37.     void printGraph() {
38.         for (int i = 0; i < V; i++) {
39.             Node* temp = adjList[i];
40.             cout << "顶点 " << i << " 的邻接表：";
41.             while (temp) {
42.                 cout << " -> " << temp->val;
43.                 temp = temp->next;
44.             }
45.             cout << endl;
46.         }
47.     }
48. };
50. int main() {
51.     Graph graph(5);
52.     graph.addEdge(0, 1);
53.     graph.addEdge(0, 4);
54.     graph.addEdge(1, 2);
55.     graph.addEdge(1, 3);
56.     graph.addEdge(1, 4);
57.     graph.addEdge(2, 3);
58.     graph.addEdge(3, 4);
60.     graph.printGraph();
62.     return 0;
63. }

复制代码

在上面的代码中，我们定义了一个Graph类来实现邻接表表示图的数据结构。通过addEdge函数可以添加边，通过printGraph函数可以打印邻接表。在main函数中，我们创建了一个包含5个节点的图，并添加了一些边，最后打印了邻接表。
深度优先搜索（DFS）算法

深度优先搜索（DFS）是一种用于图和树的遍历算法，通过尽可能深的搜索图的分支，直到无法继续为止，然后回溯到上一个节点，继续搜索下一个分支。DFS算法可以用递归或栈来实现。
在DFS算法中，我们需要一个辅助数组来标记节点是否被访问过，避免重复访问。下面是一个简朴的示例代码，展示了如何用递归实现DFS算法：

1. #include <iostream>
2. #include <vector>
4. using namespace std;
6. class Graph {
7. private:
8.     int V;
9.     vector<Node*> adjList;
11. public:
12.     Graph(int v) : V(v) {
13.         adjList.resize(V, nullptr);
14.     }
16.     void addEdge(int src, int dest) {
17.         Node* newNode = new Node(dest);
18.         newNode->next = adjList[src];
19.         adjList[src] = newNode;
21.         newNode = new Node(src);
22.         newNode->next = adjList[dest];
23.         adjList[dest] = newNode;
24.     }
26.     void printGraph() {
27.         for (int i = 0; i < V; i++) {
28.             Node* temp = adjList[i];
29.             cout << "顶点 " << i << " 的邻接表：";
30.             while (temp) {
31.                 cout << " -> " << temp->val;
32.                 temp = temp->next;
33.             }
34.             cout << endl;
35.         }
36.     }
38.     void DFSUtil(int v, vector<bool>& visited) {
39.         visited[v] = true;
40.         cout << v << " ";
42.         Node* temp = adjList[v];
43.         while (temp) {
44.             int adjNode = temp->val;
45.             if (!visited[adjNode]) {
46.                 DFSUtil(adjNode, visited);
47.             }
48.             temp = temp->next;
49.         }
50.     }
52.     void DFS(int v) {
53.         vector<bool> visited(V, false);
54.         DFSUtil(v, visited);
55.     }
56. };
58. int main() {
59.     Graph graph(5);
60.     graph.addEdge(0, 1);
61.     graph.addEdge(0, 4);
62.     graph.addEdge(1, 2);
63.     graph.addEdge(1, 3);
64.     graph.addEdge(1, 4);
65.     graph.addEdge(2, 3);
66.     graph.addEdge(3, 4);
68.     graph.printGraph();
70.     cout << "DFS遍历结果：";
71.     graph.DFS(0);
73.     return 0;
74. }

复制代码

在上面的代码中，我们在Graph类中添加了DFS算法的实现。DFSUtil函数是DFS算法的递归辅助函数，用于现实的深度优先搜索过程。DFS函数是DFS算法的入口函数，用于启动DFS搜索。在main函数中，我们创建了一个包含5个节点的图，并添加了一些边，然后打印了邻接表，并通过DFS函数进行深度优先搜索。


第三部分：DFS搜索函数实现

在这一部分，我们将深入探讨深度优先搜索（DFS）算法的实现细节，包罗如何在图的表示中实现DFS搜索函数，以及如何在现实应用中应用DFS算法办理标题。我们将讨论DFS搜索函数的实现，深入探讨递归和非递归两种实现方式，以及如何在DFS搜索中应用回溯和标记访问的技巧。让我们开始吧！
递归实现DFS搜索函数

递归是实现DFS搜索函数的一种常见方式，它轻便而直观。在递归实现DFS搜索函数时，我们需要一个辅助函数来递归地访问图中的节点，并标记已访问的节点，以避免重复访问。下面是一个简朴的示例代码，展示了如何递归实现DFS搜索函数：

1. void DFSUtil(int v, vector<bool>& visited) {
2.     visited[v] = true;
3.     cout << v << " ";
5.     Node* temp = adjList[v];
6.     while (temp) {
7.         int adjNode = temp->val;
8.         if (!visited[adjNode]) {
9.             DFSUtil(adjNode, visited);
10.         }
11.         temp = temp->next;
12.     }
13. }
15. void DFS(int v) {
16.     vector<bool> visited(V, false);
17.     DFSUtil(v, visited);
18. }

复制代码

在上面的代码中，DFSUtil函数是DFS搜索的递归辅助函数，用于现实的深度优先搜索过程。在DFS函数中，我们首先创建一个巨细为图中节点个数的visited数组，用于标记节点是否被访问过。然后调用DFSUtil函数开始深度优先搜索，从节点v开始遍历图。在DFSUtil函数中，我们首先标记节点v为已访问，并输出节点v的值。然后遍历节点v的邻接节点，假如邻接节点未被访问过，则递归调用DFSUtil函数继续深度优先搜索。
非递归实现DFS搜索函数

除了递归实现外，我们还可以用非递归的方式实现DFS搜索函数，通常使用栈来辅助实现。非递归实现DFS搜索函数可以避免递归调用的开销，适用于深度优先搜索较深的图。下面是一个简朴的示例代码，展示了如何非递归实现DFS搜索函数：

1. void DFS(int v) {
2.     vector<bool> visited(V, false);
3.     stack<int> stack;
4.     stack.push(v);
6.     while (!stack.empty()) {
7.         v = stack.top();
8.         stack.pop();
10.         if (!visited[v]) {
11.             visited[v] = true;
12.             cout << v << " ";
14.             Node* temp = adjList[v];
15.             while (temp) {
16.                 int adjNode = temp->val;
17.                 if (!visited[adjNode]) {
18.                     stack.push(adjNode);
19.                 }
20.                 temp = temp->next;
21.             }
22.         }
23.     }
24. }

复制代码

在上面的代码中，我们使用了一个栈来辅助实现非递归的DFS搜索函数。首先创建一个visited数组和一个栈stack，将起始节点v入栈。然后在while循环中，从栈中弹出一个节点v，假如节点v未被访问过，则标记节点v为已访问，并输出节点v的值。然后遍历节点v的邻接节点，将未被访问过的邻接节点入栈，继续深度优先搜索。
DFS搜索函数的应用

DFS搜索函数在现实应用中有许多用途，包罗办理图的遍历标题、寻找图中的路径、判定图的连通性、拓扑排序等。DFS算法还可以应用于办理迷宫标题、括号匹配标题、数独等各种算法标题。
一个常见的应用是判定图中是否存在路径，我们可以用DFS搜索函数来实现。下面是一个简朴的示例代码，展示了如何用DFS搜索函数判定图中是否存在从节点v到节点w的路径：

1. bool hasPath(int v, int w) {
2.     vector<bool> visited(V, false);
3.     return hasPathUtil(v, w, visited);
4. }
6. bool hasPathUtil(int v, int w, vector<bool>& visited) {
7.     if (v == w) {
8.         return true;
9.     }
11.     visited[v] = true;
12.     Node* temp = adjList[v];
13.     while (temp) {
14.         int adjNode = temp->val;
15.         if (!visited[adjNode] && hasPathUtil(adjNode, w, visited)) {
16.             return true;
17.         }
18.         temp = temp->next;
19.     }
21.     return false;
22. }

复制代码

在上面的代码中，我们实现了一个hasPath函数来判定图中是否存在从节点v到节点w的路径。在hasPathUtil函数中，我们首先判定节点v和节点w是否相称，假如相称则表示存在路径，直接返回true。然后标记节点v为已访问，并遍历节点v的邻接节点，递归地判定邻接节点是否存在路径到节点w。假如找到路径则返回true，否则返回false。




例题(1)

P1331 海战

P1331 海战 - 洛谷
# P1331 海战
## 标题配景
在峰会期间，武装部队得处于高度警备。警察将监视每一条大街，军队将保卫修建物，领空将充满了 F-2003 飞机。
别的，巡洋船只和舰队将被派去保护海岸线。不幸的是，由于种种原因，国防海军部仅有很少的几位军官能指挥大型海战。因此，他们造就了一些新海军指挥官。军官们选择了“海战”游戏来资助他们学习。
## 标题描述
在一个方形的盘上，放置了固定数量和形状的船只，每只船却不能遇到其它的船。在本题中，我们认为船是方形的，所有的船只都是由图形构成的方形。
求出该棋盘上放置的船只的总数。
## 输入格式
第一行为两个整数 $R$ 和 $C$，用空格隔开，分别表示游戏棋盘的行数和列数。
接下来 $R$ 行，每行 $C$ 个字符，为 `#` 或 `.`。`#` 表示船只的一部分，`.` 表示水。
## 输特别式
一行一个字符串，假如船的位置放得正确（即棋盘上只存在相互之间不能打仗的方形，假如两个 `#` 号上下相邻或左右相邻却分属两艘差别的船只，则称这两艘船相互打仗了）。就输出 `There are S ships.`，$S$ 表示船只的数量。否则输出 `Bad placement.`。
## 输入输出样例 #1
### 输入 #1
```
6 8
.....#.#
##.....#
##.....#
.......#
#......#
#..#...#
```
### 输出 #1
```
There are 5 ships.
```
## 分析/提示
对于 $100\%$ 的数据，$1 \le R,C \le 1000$。
代码

1. #include<bits/stdc++.h>
2. using namespace std;
3. int m,n,f[1005][1005],s,b[1005][1005],pd,lll;
4. int xx,dd,xb,db;
5. char a[1005][1005];
6. int bx[4]={0,0,-1,1};
7. int by[4]={-1,1,0,0};
8. void dfs(int x,int y){
9.     if(x<1||x>n||y<1||y>m||f[x][y]==1||a[x][y]!='#')return ;
10.     else{
11.     a[x][y]='@';
12.     f[x][y]=1;
13.     if(x>xx)xx=x;
14.     if(y>dd)dd=y;
15.     if(x<xb)xb=x;
16.     if(y<db)db=y;
17.    
18.     for(int i=0; i<4; i++)
19.         dfs(x+bx[i],y+by[i]);
20.     }
21.     return ;
22. }
23. int main(){
24. cin>>n>>m;
25. for(int i=1; i<=n; i++)
26.     for(int j=1; j<=m; j++)
27.         cin>>a[i][j];
28. for(int i=1; i<=n; i++){
29.     for(int j=1; j<=m; j++){
30.         if(a[i][j]=='#'){
31.             xx=-1,dd=-1,xb=2100000,db=2100000;
32.             dfs(i,j);
33.             for(int k=xb; k<=xx; k++){
34.                 for(int l=db; l<=dd; l++){
35.                     if(a[k][l]=='.')pd=1,s=-1;
36.                     a[k][l]='.';
37.                 }
38.             }
39.             if(pd==0)s++;
40.         }
41.     }
42. }
43. if(s!=-1)cout<<"There are "<<s<<" ships.";
44. else cout<<"Bad placement.";
45. return 0;
46. }

复制代码

例题(2)

P1219 [USACO1.5] 八皇后 Checker Challenge
P1219 [USACO1.5] 八皇后 Checker Challenge - 洛谷
# P1219 [USACO1.5] 八皇后 Checker Challenge
## 标题描述
一个如下的 $6 \times 6$ 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包罗两条主对角线的所有平行线）上至多有一个棋子。
上面的结构可以用序列 $2\ 4\ 6\ 1\ 3\ 5$ 来描述，第 $i$ 个数字表示在第 $i$ 行的相应位置有一个棋子，如下：
行号 $1\ 2\ 3\ 4\ 5\ 6$
列号 $2\ 4\ 6\ 1\ 3\ 5$
这只是棋子放置的一个解。请编一个步伐找出所有棋子放置的解。  
并把它们以上面的序列方法输出，解按字典顺序排列。  
请输出前 $3$ 个解。最后一行是解的总个数。
## 输入格式
一行一个正整数 $n$，表示棋盘是 $n \times n$ 巨细的。
## 输特别式
前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。
## 输入输出样例 #1
### 输入 #1
```
6
```
### 输出 #1
```
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4
```
## 分析/提示
【数据范围】  
对于 $100\%$ 的数据，$6 \le n \le 13$。
标题翻译来自NOCOW。
USACO Training Section 1.5

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。