深度优先搜索(Depth-First Search,DFS)是一种用于遍历或搜索树或图的算法。

简介: 深度优先搜索(Depth-First Search,DFS)是一种用于遍历或搜索树或图的算法。

在深度优先搜索中,我们从起始顶点开始沿着一条路径尽可能深地搜索,直到到达最深的顶点,然后再倒退回来继续搜索其他路径。DFS 通常使用栈来实现,它遵循以下步骤:

 

1. 选择一个起始顶点作为当前顶点,并将其标记为已访问。

2. 将当前顶点入栈。

3. 在栈不为空的情况下,重复以下步骤:

  - 弹出栈顶元素作为当前顶点。

  - 对于当前顶点的每个未访问的邻居顶点,将其标记为已访问并入栈。

4. 当无法继续深入时(即当前顶点没有未访问的邻居顶点),回溯到上一个顶点继续搜索。

 

DFS 的特点包括:

 

- 深度优先:尽可能深地搜索每条路径,直到无法继续深入为止。

- 非最优解:DFS 不保证找到最优解,因为它可能会陷入局部最优解而无法跳出。

- 递归性质:DFS 可以使用递归或栈来实现,递归实现更简洁直观,但在处理大规模图时可能会导致栈溢出。

 

DFS 在许多领域都有广泛的应用,包括图论、人工智能、编译器等。在图论中,DFS 可以用于查找连通分量、拓扑排序、寻找路径等问题。在人工智能中,DFS 可以用于搜索状态空间、解决迷宫问题等。在编译器中,DFS 可以用于控制流图的遍历和分析等。

 

总的来说,深度优先搜索(Depth-First Search,DFS)是一种用于遍历或搜索树或图的算法。它从起始顶点开始,沿着路径直到到达最深的顶点,然后再倒退回来继续搜索其他路径。

 

### C 语言

 

```c
#include <stdio.h>
#include <stdlib.h>
 
#define MAX_VERTICES 100
 
typedef struct {
    int data[MAX_VERTICES];
    int top;
} Stack;
 
void init(Stack *s) {
    s->top = -1;
}
 
void push(Stack *s, int value) {
    s->data[++(s->top)] = value;
}
 
int pop(Stack *s) {
    return s->data[(s->top)--];
}
 
int isEmpty(Stack *s) {
    return s->top == -1;
}
 
typedef struct {
    int vertices[MAX_VERTICES];
    int front, rear;
} Queue;
 
void init(Queue *q) {
    q->front = 0;
    q->rear = -1;
}
 
void enqueue(Queue *q, int value) {
    q->vertices[++(q->rear)] = value;
}
 
int dequeue(Queue *q) {
    return q->vertices[(q->front)++];
}
 
int isEmpty(Queue *q) {
    return q->front > q->rear;
}
 
typedef struct {
    int vertices[MAX_VERTICES][MAX_VERTICES];
    int visited[MAX_VERTICES];
    int num_vertices;
} Graph;
 
void initGraph(Graph *g, int num_vertices) {
    g->num_vertices = num_vertices;
    for (int i = 0; i < num_vertices; i++) {
        g->visited[i] = 0;
        for (int j = 0; j < num_vertices; j++) {
            g->vertices[i][j] = 0;
        }
    }
}
 
void addEdge(Graph *g, int v1, int v2) {
    g->vertices[v1][v2] = 1;
    g->vertices[v2][v1] = 1;
}
 
void dfs(Graph *g, int start) {
    Stack s;
    init(&s);
    push(&s, start);
    g->visited[start] = 1;
 
    while (!isEmpty(&s)) {
        int current = pop(&s);
        printf("%d ", current);
 
        for (int i = 0; i < g->num_vertices; i++) {
            if (g->vertices[current][i] == 1 && g->visited[i] == 0) {
                push(&s, i);
                g->visited[i] = 1;
            }
        }
    }
}
 
int main() {
    Graph g;
    initGraph(&g, 6);
    addEdge(&g, 0, 1);
    addEdge(&g, 0, 2);
    addEdge(&g, 1, 3);
    addEdge(&g, 1, 4);
    addEdge(&g, 2, 5);
 
    printf("DFS traversal starting from vertex 0: ");
    dfs(&g, 0);
 
    return 0;
}
```


### C++ 语言

```cpp
#include <iostream>
#include <vector>
#include <stack>
 
using namespace std;
 
void dfs(vector<vector<int>>& graph, vector<bool>& visited, int start) {
    stack<int> s;
    s.push(start);
    visited[start] = true;
 
    while (!s.empty()) {
        int current = s.top();
        s.pop();
        cout << current << " ";
 
        for (int i = 0; i < graph[current].size(); i++) {
            int neighbor = graph[current][i];
            if (!visited[neighbor]) {
                s.push(neighbor);
                visited[neighbor] = true;
            }
        }
    }
}
 
int main() {
    vector<vector<int>> graph = {{1, 2}, {0, 3, 4}, {0, 5}, {1}, {1}, {2}};
    vector<bool> visited(graph.size(), false);
 
    cout << "DFS traversal starting from vertex 0: ";
    dfs(graph, visited, 0);
 
    return 0;
}
```

 

### Java 语言

 

```java
import java.util.Stack;
 
class Graph {
    private int numVertices;
    private int[][] vertices;
    private boolean[] visited;
 
    public Graph(int numVertices) {
        this.numVertices = numVertices;
        vertices = new int[numVertices][numVertices];
        visited = new boolean[numVertices];
    }
 
    public void addEdge(int v1, int v2) {
        vertices[v1][v2] = 1;
        vertices[v2][v1] = 1;
    }
 
    public void dfs(int start) {
        Stack<Integer> stack = new Stack<>();
        stack.push(start);
        visited[start] = true;
 
        while (!stack.isEmpty()) {
            int current = stack.pop();
            System.out.print(current + " ");
 
            for (int i = 0; i < numVertices; i++) {
                if (vertices[current][i] == 1 && !visited[i]) {
                    stack.push(i);
                    visited[i] = true;
                }
            }
        }
    }
 
    public static void main(String[] args) {
        Graph graph = new Graph(6);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 5);
 
        System.out.print("DFS traversal starting from vertex 0: ");
        graph.dfs(0);
    }
}
```
相关文章
|
15天前
|
机器学习/深度学习 算法 安全
【无人机三维路径规划】基于非支配排序的鲸鱼优化算法NSWOA与多目标螳螂搜索算法MOMSA求解无人机三维路径规划研究(Matlab代码实现)
【无人机三维路径规划】基于非支配排序的鲸鱼优化算法NSWOA与多目标螳螂搜索算法MOMSA求解无人机三维路径规划研究(Matlab代码实现)
|
17天前
|
机器学习/深度学习 算法 安全
【无人机三维路径规划】多目标螳螂搜索算法MOMSA与非支配排序的鲸鱼优化算法NSWOA求解无人机三维路径规划研究(Matlab代码实现)
【无人机三维路径规划】多目标螳螂搜索算法MOMSA与非支配排序的鲸鱼优化算法NSWOA求解无人机三维路径规划研究(Matlab代码实现)
|
2月前
|
机器学习/深度学习 算法 文件存储
神经架构搜索NAS详解:三种核心算法原理与Python实战代码
神经架构搜索(NAS)正被广泛应用于大模型及语言/视觉模型设计,如LangVision-LoRA-NAS、Jet-Nemotron等。本文回顾NAS核心技术,解析其自动化设计原理,探讨强化学习、进化算法与梯度方法的应用与差异,揭示NAS在大模型时代的潜力与挑战。
300 6
神经架构搜索NAS详解:三种核心算法原理与Python实战代码
|
18天前
|
机器学习/深度学习 算法 机器人
【机器人路径规划】基于深度优先搜索(Depth-First-Search,DFS)算法的机器人路径规划(Python代码实现)
【机器人路径规划】基于深度优先搜索(Depth-First-Search,DFS)算法的机器人路径规划(Python代码实现)
|
18天前
|
存储 算法 数据可视化
基于禁忌搜索算法的TSP问题最优路径搜索matlab仿真
本程序基于禁忌搜索算法解决旅行商问题(TSP),旨在寻找访问多个城市的最短路径。使用 MATLAB 2022A 编写,包含城市坐标生成、路径优化及结果可视化功能。通过禁忌列表、禁忌长度与藐视准则等机制,提升搜索效率与解的质量,适用于物流配送、路径规划等场景。
|
6月前
|
人工智能 自然语言处理 算法
阿里云 AI 搜索开放平台:从算法到业务——AI 搜索驱动企业智能化升级
本文介绍了阿里云 AI 搜索开放平台的技术的特点及其在各行业的应用。
645 3
|
2月前
|
机器学习/深度学习 并行计算 算法
MATLAB实现利用禁忌搜索算法解决基站选址问题
MATLAB实现利用禁忌搜索算法解决基站选址问题
67 0
|
3月前
|
存储 搜索推荐 算法
加密算法、排序算法、字符串处理及搜索算法详解
本文涵盖四大类核心技术知识。加密算法部分介绍了对称加密(如 AES)、非对称加密(如 RSA)、哈希摘要(如 SHA-2)、签名算法的特点及密码存储方案(加盐、BCrypt 等)。 排序算法部分分类讲解了比较排序(冒泡、选择、插入、归并、快排、堆排序)和非比较排序(计数、桶、基数排序)的时间复杂度、适用场景及实现思路,强调混合排序的工业应用。 字符串处理部分包括字符串反转的双指针法,及项目中用正则进行表单校验、网页爬取、日志处理的实例。 搜索算法部分详解了二分查找的实现(双指针与中间索引计算)和回溯算法的概念(递归 + 剪枝),以 N 皇后问题为例说明回溯应用。内容全面覆盖算法原理与实践
132 0
|
4月前
|
机器学习/深度学习 算法 数据可视化
基于Qlearning强化学习的机器人迷宫路线搜索算法matlab仿真
本内容展示了基于Q-learning算法的机器人迷宫路径搜索仿真及其实现过程。通过Matlab2022a进行仿真,结果以图形形式呈现,无水印(附图1-4)。算法理论部分介绍了Q-learning的核心概念,包括智能体、环境、状态、动作和奖励,以及Q表的构建与更新方法。具体实现中,将迷宫抽象为二维网格世界,定义起点和终点,利用Q-learning训练机器人找到最优路径。核心程序代码实现了多轮训练、累计奖励值与Q值的可视化,并展示了机器人从起点到终点的路径规划过程。
129 0
|
10天前
|
存储 编解码 算法
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)

热门文章

最新文章