在深度优先搜索中，我们从起始顶点开始沿着一条路径尽可能深地搜索，直到到达最深的顶点，然后再倒退回来继续搜索其他路径。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); } } ```
