当前位置：首页 > news >正文

c++_csp-j算法 (1)

news 来源：原创 2025/8/7 10:42:22

DFS搜索(深度优先搜索)

讲解

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

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

1. 基本思想

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

2. 递归实现

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

DFS(node):访问节点node将节点node标记为已访问for 每个邻居节点neighbor of node:if neighbor未被访问过:DFS(neighbor)

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

3. 栈实现

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

DFS(node):初始化一个栈s将起始节点node入栈将节点node标记为已访问while 栈s非空:弹出栈顶节点top访问节点topfor 每个邻居节点neighbor of top:if neighbor未被访问过:将neighbor入栈将neighbor标记为已访问

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

4. 应用领域

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

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

第二部分:图的表示

在计算机科学中，图是一种非常重要的数据结构，用于表示对象之间的关系。图由节点（顶点）和边组成，节点之间的边表示节点之间的关系。在图论中，图可以分为有向图和无向图，有向图中的边是有方向的，无向图中的边是没有方向的。

图的表示有多种方式，常见的包括邻接矩阵和邻接表。在邻接矩阵中，图的节点和边可以用二维矩阵表示，矩阵的行和列分别表示图中的节点，矩阵中的值表示节点之间的边。邻接矩阵适用于稠密图，但对于稀疏图来说可能会占用较多的内存空间。而邻接表是一种更为灵活的表示方式，适用于稀疏图。在邻接表中，每个节点对应一个链表，链表中存储了与该节点相邻的节点，通过链表的方式表示节点之间的关系。

邻接表的实现

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

#include <iostream>
#include <vector>using namespace std;// 图的节点结构体
struct Node {int val;Node* next;Node(int v) : val(v), next(nullptr) {}
};// 邻接表表示图的数据结构
class Graph {
private:int V; // 图中节点的个数vector<Node*> adjList; // 邻接表public:Graph(int v) : V(v) {adjList.resize(V, nullptr);}// 添加边void addEdge(int src, int dest) {Node* newNode = new Node(dest);newNode->next = adjList[src];adjList[src] = newNode;// 无向图的话，需要添加反向边newNode = new Node(src);newNode->next = adjList[dest];adjList[dest] = newNode;}// 打印邻接表void printGraph() {for (int i = 0; i < V; i++) {Node* temp = adjList[i];cout << "顶点 " << i << " 的邻接表：";while (temp) {cout << " -> " << temp->val;temp = temp->next;}cout << endl;}}
};int main() {Graph graph(5);graph.addEdge(0, 1);graph.addEdge(0, 4);graph.addEdge(1, 2);graph.addEdge(1, 3);graph.addEdge(1, 4);graph.addEdge(2, 3);graph.addEdge(3, 4);graph.printGraph();return 0;
}

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

深度优先搜索（DFS）算法

深度优先搜索（DFS）是一种用于图和树的遍历算法，通过尽可能深的搜索图的分支，直到无法继续为止，然后回溯到上一个节点，继续搜索下一个分支。DFS算法可以用递归或栈来实现。

在DFS算法中，我们需要一个辅助数组来标记节点是否被访问过，避免重复访问。下面是一个简单的示例代码，展示了如何用递归实现DFS算法：

#include <iostream>
#include <vector>using namespace std;class Graph {
private:int V;vector<Node*> adjList;public:Graph(int v) : V(v) {adjList.resize(V, nullptr);}void addEdge(int src, int dest) {Node* newNode = new Node(dest);newNode->next = adjList[src];adjList[src] = newNode;newNode = new Node(src);newNode->next = adjList[dest];adjList[dest] = newNode;}void printGraph() {for (int i = 0; i < V; i++) {Node* temp = adjList[i];cout << "顶点 " << i << " 的邻接表：";while (temp) {cout << " -> " << temp->val;temp = temp->next;}cout << endl;}}void DFSUtil(int v, vector<bool>& visited) {visited[v] = true;cout << v << " ";Node* temp = adjList[v];while (temp) {int adjNode = temp->val;if (!visited[adjNode]) {DFSUtil(adjNode, visited);}temp = temp->next;}}void DFS(int v) {vector<bool> visited(V, false);DFSUtil(v, visited);}
};int main() {Graph graph(5);graph.addEdge(0, 1);graph.addEdge(0, 4);graph.addEdge(1, 2);graph.addEdge(1, 3);graph.addEdge(1, 4);graph.addEdge(2, 3);graph.addEdge(3, 4);graph.printGraph();cout << "DFS遍历结果：";graph.DFS(0);return 0;
}

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

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

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

递归实现DFS搜索函数

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

void DFSUtil(int v, vector<bool>& visited) {visited[v] = true;cout << v << " ";Node* temp = adjList[v];while (temp) {int adjNode = temp->val;if (!visited[adjNode]) {DFSUtil(adjNode, visited);}temp = temp->next;}
}void DFS(int v) {vector<bool> visited(V, false);DFSUtil(v, visited);
}

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

非递归实现DFS搜索函数

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

void DFS(int v) {vector<bool> visited(V, false);stack<int> stack;stack.push(v);while (!stack.empty()) {v = stack.top();stack.pop();if (!visited[v]) {visited[v] = true;cout << v << " ";Node* temp = adjList[v];while (temp) {int adjNode = temp->val;if (!visited[adjNode]) {stack.push(adjNode);}temp = temp->next;}}}
}

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

DFS搜索函数的应用

DFS搜索函数在实际应用中有很多用途，包括解决图的遍历问题、寻找图中的路径、判断图的连通性、拓扑排序等。DFS算法还可以应用于解决迷宫问题、括号匹配问题、数独等各种算法问题。

一个常见的应用是判断图中是否存在路径，我们可以用DFS搜索函数来实现。下面是一个简单的示例代码，展示了如何用DFS搜索函数判断图中是否存在从节点v到节点w的路径：

bool hasPath(int v, int w) {vector<bool> visited(V, false);return hasPathUtil(v, w, visited);
}bool hasPathUtil(int v, int w, vector<bool>& visited) {if (v == w) {return true;}visited[v] = true;Node* temp = adjList[v];while (temp) {int adjNode = temp->val;if (!visited[adjNode] && hasPathUtil(adjNode, w, visited)) {return true;}temp = temp->next;}return false;
}

在上面的代码中，我们实现了一个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$。

代码

#include<bits/stdc++.h>
using namespace std;
int m,n,f[1005][1005],s,b[1005][1005],pd,lll;
int xx,dd,xb,db;
char a[1005][1005];
int bx[4]={0,0,-1,1};
int by[4]={-1,1,0,0};
void dfs(int x,int y){if(x<1||x>n||y<1||y>m||f[x][y]==1||a[x][y]!='#')return ;else{a[x][y]='@';f[x][y]=1;if(x>xx)xx=x;if(y>dd)dd=y;if(x<xb)xb=x;if(y<db)db=y;for(int i=0; i<4; i++)dfs(x+bx[i],y+by[i]);}return ;
}
int main(){
cin>>n>>m;
for(int i=1; i<=n; i++)for(int j=1; j<=m; j++)cin>>a[i][j];
for(int i=1; i<=n; i++){for(int j=1; j<=m; j++){if(a[i][j]=='#'){xx=-1,dd=-1,xb=2100000,db=2100000;dfs(i,j);for(int k=xb; k<=xx; k++){for(int l=db; l<=dd; l++){if(a[k][l]=='.')pd=1,s=-1;a[k][l]='.';}}if(pd==0)s++;}}
}
if(s!=-1)cout<<"There are "<<s<<" ships.";
else cout<<"Bad placement.";
return 0;
}

例题(2)

P1219 [USACO1.5] 八皇后 Checker Challenge

P1219 [USACO1.5] 八皇后 Checker Challenge - 洛谷

# P1219 [USACO1.5] 八皇后 Checker Challenge

## 题目描述

一个如下的 $6 \times 6$ 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。

![](https://cdn.luogu.com.cn/upload/image_hosting/3h71x0yf.png)

上面的布局可以用序列 $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