【学习笔记】[ZJOI2022] 深搜

**深度优先搜索（DFS）学习笔记**

**前言**

深度优先搜索（DFS）是计算机科学中一个非常重要的算法。它是一种用于遍历图或树结构的方法，能够有效地解决许多问题，如寻找路径、检测环路等。在本文中，我们将详细介绍DFS的基本概念、实现原理和应用场景。

**什么是深度优先搜索（DFS）**

深度优先搜索是一种用于遍历图或树结构的算法。它从一个起始点出发，沿着边或弧向下探索，直到达到叶子结点或遇到障碍为止。在回溯过程中，DFS会尝试访问尚未访问过的结点，以尽可能深入地探索图结构。

**DFS的实现原理**

DFS的实现原理可以分为以下几个步骤：

1. **选择起始点**:选择一个起始点作为 DFS 的入口。
2. **沿边或弧向下探索**:从起始点出发，沿着边或弧向下探索，直到达到叶子结点或遇到障碍为止。
3. **回溯**:在回溯过程中，DFS会尝试访问尚未访问过的结点，以尽可能深入地探索图结构。

**DFS的应用场景**

DFS有许多应用场景，如：

* **寻找路径**:DFS可以用于寻找从起始点到目标点的最短路径。
* **检测环路**:DFS可以用于检测是否存在环路。
* **求解问题**:DFS可以用于解决许多问题，如旅行商问题、骑士问题等。

**代码示例**

以下是使用C++语言实现DFS的示例代码：

cpp#include <iostream>
using namespace std;

// 定义图结构struct Graph {
 int V; // 图中的顶点数 int **adj; // 邻接矩阵};

// 初始化图结构Graph* createGraph(int vertices) {
 Graph* graph = new Graph;
 graph->V = vertices;
 graph->adj = new int*[vertices];
 for (int i =0; i < vertices; i++) {
 graph->adj[i] = new int[vertices];
 // 初始化邻接矩阵 for (int j =0; j < vertices; j++)
 graph->adj[i][j] =0;
 }
 return graph;
}

// DFS函数void DFS(Graph* graph, int v, bool visited[]) {
 // 标记当前顶点为已访问 visited[v] = true;
 // 输出当前顶点 cout << v << " ";
 // 遍历邻接矩阵，找到未访问的顶点 for (int i =0; i < graph->V; i++) {
 if (!visited[i] && graph->adj[v][i] ==1)
 DFS(graph, i, visited);
 }
}

// 主函数int main() {
 int vertices =5;
 // 创建图结构 Graph* graph = createGraph(vertices);
 // 初始化邻接矩阵 graph->adj[0][1] = graph->adj[1][0] =1;
 graph->adj[0][2] = graph->adj[2][0] =1;
 graph->adj[1][3] = graph->adj[3][1] =1;
 graph->adj[2][4] = graph->adj[4][2] =1;
 // DFS函数 bool visited[vertices];
 for (int i =0; i < vertices; i++)
 visited[i] = false;
 cout << "DFS Traversal: ";
 DFS(graph,0, visited);
 return0;
}