深度优先搜索 (DFS) 算法

更新于 2025/10/16 16:21:06

深度优先搜索 (DFS) 算法

深度优先搜索 (DFS) 算法是一种递归算法，用于搜索图或树数据结构的所有顶点。该算法以深度方向遍历图，并使用堆栈记住在任何迭代中出现死角时获取下一个顶点以开始搜索。

如上例所示，DFS 算法首先从 S 遍历到 A、D、G、E、B，然后到 F，最后到 C。它采用以下规则。

规则 1 −访问相邻的未访问顶点。将其标记为已访问。显示它。将其压入堆栈。
规则 2 − 如果未找到相邻顶点，则从堆栈中弹出一个顶点。（它将弹出堆栈中所有没有相邻顶点的顶点。）
规则 3 − 重复规则 1 和规则 2，直到堆栈为空。

步骤	遍历	描述
1		初始化堆栈。
2		将 S 标记为已访问并将其放入堆栈。探索 S 中任何未访问的相邻节点。我们有三个节点，可以从中选取任意一个。在本例中，我们将按字母顺序选取节点。
3		将 A 标记为已访问，并将其放入堆栈。探索 A 节点的任何未访问相邻节点。S 和 D 都与 A 相邻，但我们只关注未访问的节点。
4		访问 D 并将其标记为已访问，然后放入堆栈。这里，我们有 B 和 C 节点，它们与 D 相邻，并且都未访问过。不过，我们还是要按字母顺序选择。
5		我们选择B，将其标记为已访问并放入堆栈。此处B没有任何未访问的相邻节点。因此，我们从堆栈中弹出 B。
6		我们检查堆栈顶部是否返回到上一个节点，并检查它是否有任何未访问的节点。这里，我们发现 D 位于栈顶。
7		现在唯一来自 D 的未访问相邻节点是 C。因此，我们访问 C，将其标记为已访问，然后将其放入栈中。

由于 C 没有任何未访问的相邻节点，因此我们不断弹出堆栈，直到找到一个具有未访问相邻节点的节点。在这种情况下，没有元素，我们会不断弹出，直到堆栈为空。

示例

以下是深度优先搜索 (DFS) 算法在各种编程语言中的实现 −

C C++ Java Python

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 5
struct Vertex {
   char label;
   bool visited;
};
//堆栈变量
int stack[MAX];
int top = -1;
//图变量
//顶点数组
struct Vertex* lstVertices[MAX];
//邻接矩阵
int adjMatrix[MAX][MAX];
//顶点数量
int vertexCount = 0;
//堆栈函数
void push(int item) { 
   stack[++top] = item; 
} 
int pop() { 
   return stack[top--]; 
} 
int peek() {
   return stack[top];
}
bool isStackEmpty() {
   return top == -1;
}
//图函数

//将顶点添加到顶点列表
void addVertex(char label) {
    struct Vertex* vertex = (struct Vertex*) malloc(sizeof(struct Vertex));
    vertex->label = label;
    vertex->visited = false;
    lstVertices[vertexCount++] = vertex;
}
//将边添加到边数组
void addEdge(int start,int end) {
    adjMatrix[start][end] = 1;
    adjMatrix[end][start] = 1;
}
//显示顶点
void displayVertex(int vertexIndex) {
    printf("%c ",lstVertices[vertexIndex]->label);
}
//获取相邻的未访问顶点
int getAdjUnvisitedVertex(int vertexIndex) {
   int i;
   for(i = 0; i < vertexCount; i++) {
      if(adjMatrix[vertexIndex][i] == 1 && lstVertices[i]->visited == false) {
         return i;
      }
   }
   return -1;
}
void depthFirstSearch() {
    int i;
    //将第一个节点标记为已访问
    lstVertices[0]->visited = true;
    //显示顶点
    displayVertex(0);
    //将顶点索引压入堆栈
    push(0);
   while(!isStackEmpty()) {
      //获取栈顶顶点的未访问顶点
      int unvisitedVertex = getAdjUnvisitedVertex(peek());
      //未找到相邻顶点
      if(unvisitedVertex == -1) {
         pop();
      } else {
         lstVertices[unvisitedVertex]->visited = true;
         displayVertex(unvisitedVertex);
         push(unvisitedVertex);
      }
   }
   //堆栈为空，搜索完成，重置访问标志    
   for(i = 0;i < vertexCount;i++) {
      lstVertices[i]->visited = false;
   }        
}
int main() {
   int i, j;

   for(i = 0; i < MAX; i++) {   // 设置邻接
      for(j = 0; j < MAX; j++) // 矩阵为 0
         adjMatrix[i][j] = 0;
   }
   addVertex('S');   // 0
   addVertex('A');   // 1
   addVertex('B');   // 2
   addVertex('C');   // 3
   addVertex('D');   // 4
   addEdge(0, 1);    // S - A
   addEdge(0, 2);    // S - B
   addEdge(0, 3);    // S - C
   addEdge(1, 4);    // A - D
   addEdge(2, 4);    // B - D
   addEdge(3, 4);    // C - D
   printf("Depth First Search: ");
   depthFirstSearch(); 
   return 0;   
}

输出

Depth First Search: S A D B C

//深度优先遍历的 C++ 代码
#include <iostream>
#include <array>
#include <vector>
constexpr int MAX = 5;
struct Vertex {
   char label;
   bool visited;
};
//堆栈变量
std::array<int, MAX> stack;
int top = -1;
//图变量
//顶点数组
std::array<Vertex*, MAX> lstVertices;
//邻接矩阵
std::array<std::array<int, MAX>, MAX> adjMatrix;
//顶点数量
int vertexCount = 0;
//堆栈函数
void push(int item) {
   stack[++top] = item;
}
int pop() {
   return stack[top--];
}
int peek() {
   return stack[top];
}
bool isStackEmpty() {
   return top == -1;
}
//图形函数
//将顶点添加到顶点列表
void addVertex(char label) {
   Vertex* vertex = new Vertex;
   vertex->label = label;
   vertex->visited = false;
   lstVertices[vertexCount++] = vertex;
}

//将边添加到边数组
void addEdge(int start, int end) {
    adjMatrix[start][end] = 1;
    adjMatrix[end][start] = 1;
}

//显示顶点
void displayVertex(int vertexIndex) {
    std::cout << lstVertices[vertexIndex]->label << " ";
}
//获取相邻的未访问顶点
int getAdjUnvisitedVertex(int vertexIndex) {
   for (int i = 0; i < vertexCount; i++) {
      if (adjMatrix[vertexIndex][i] == 1 && !lstVertices[i]->visited) {
         return i;
      }
   }
   return -1;
}
//标记第一个节点为已访问
void depthFirstSearch() {
   lstVertices[0]->visited = true;
   //显示顶点
   displayVertex(0);
   //将顶点索引压入堆栈
   push(0);
   while (!isStackEmpty()) {
       //获取栈顶顶点的未访问顶点
      int unvisitedVertex = getAdjUnvisitedVertex(peek());
      //未找到相邻顶点
      if (unvisitedVertex == -1) {
         pop();
      } else {
         lstVertices[unvisitedVertex]->visited = true;
         displayVertex(unvisitedVertex);
         push(unvisitedVertex);
      }
   }
   //堆栈为空，搜索完成，重置访问标志
   for (int i = 0; i < vertexCount; i++) {
      lstVertices[i]->visited = false;
   }
}
int main() {
   for (int i = 0; i < MAX; i++) {   //设置邻接
      for (int j = 0; j < MAX; j++) {    // 矩阵为 0
         adjMatrix[i][j] = 0;
      }
   }
   addVertex('S');
   addVertex('A');
   addVertex('B');
   addVertex('C');
   addVertex('D');
   addEdge(0, 1);
   addEdge(0, 2);
   addEdge(0, 3);
   addEdge(1, 4);
   addEdge(2, 4);
   addEdge(3, 4);
   std::cout << "Depth First Search: ";
   depthFirstSearch();
   return 0;
}

输出

Depth First Search: S A D B C

//深度优先遍历的Java程序
public class DepthFirstSearch {
    private static final int MAX = 5;
    private static class Vertex {
        char label;
        boolean visited;
    }
    private static int[] stack = new int[MAX];
    private static int top = -1;
    private static Vertex[] lstVertices = new Vertex[MAX];
    private static int[][] adjMatrix = new int[MAX][MAX];
    private static int vertexCount = 0;
    private static void push(int item) {
        stack[++top] = item;
    }
    private static int pop() {
        return stack[top--];
    }
    private static int peek() {
        return stack[top];
    }
    private static boolean isStackEmpty() {
        return top == -1;
    }
    private static void addVertex(char label) {
        Vertex vertex = new Vertex();
        vertex.label = label;
        vertex.visited = false;
        lstVertices[vertexCount++] = vertex;
    }
    private static void addEdge(int start, int end) {
        adjMatrix[start][end] = 1;
        adjMatrix[end][start] = 1;
    }
    private static void displayVertex(int vertexIndex) {
        System.out.print(lstVertices[vertexIndex].label + " ");
    }
    private static int getAdjUnvisitedVertex(int vertexIndex) {
        for (int i = 0; i < vertexCount; i++) {
            if (adjMatrix[vertexIndex][i] == 1 && !lstVertices[i].visited) {
                return i;
            }
        }
        return -1;
    }
    private static void depthFirstSearch() {
        lstVertices[0].visited = true;
        displayVertex(0);
        push(0);
        while (!isStackEmpty()) {
            int unvisitedVertex = getAdjUnvisitedVertex(peek());

            if (unvisitedVertex == -1) {
                pop();
            } else {
                lstVertices[unvisitedVertex].visited = true;
                displayVertex(unvisitedVertex);
                push(unvisitedVertex);
            }
        }
        for (int i = 0; i < vertexCount; i++) {
            lstVertices[i].visited = false;
        }
    }
    public static void main(String[] args) {
        for (int i = 0; i < MAX; i++) {
            for (int j = 0; j < MAX; j++) {
                adjMatrix[i][j] = 0;
            }
        }
        addVertex('S');   // 0
        addVertex('A');   // 1
        addVertex('B');   // 2
        addVertex('C');   // 3
        addVertex('D');   // 4
        addEdge(0, 1);    // S - A
        addEdge(0, 2);    // S - B
        addEdge(0, 3);    // S - C
        addEdge(1, 4);    // A - D
        addEdge(2, 4);    // B - D
        addEdge(3, 4);    // C - D
        System.out.print("Depth First Search: ");
        depthFirstSearch();
    }
}

输出

Depth First Search: S A D B C

#深度优先遍历的Python程序
MAX = 5
class Vertex:
    def __init__(self, label):
        self.label = label
        self.visited = False
#堆栈变量
stack = []
top = -1
#图变量
#顶点数组
lstVertices = [None] * MAX
#邻接矩阵
adjMatrix = [[0] * MAX for _ in range(MAX)]
#顶点数量
vertexCount = 0
#堆栈函数
def push(item):
    global top
    top += 1
    stack.append(item)
def pop():
    global top
    item = stack[top]
    del stack[top]
    top -= 1
    return item
def peek():
    return stack[top]
def isStackEmpty():
    return top == -1
#图函数
#将顶点添加到顶点列表
def addVertex(label):
    global vertexCount
    vertex = Vertex(label)
    lstVertices[vertexCount] = vertex
    vertexCount += 1
#将边添加到边数组
def addEdge(start, end):
    adjMatrix[start][end] = 1
    adjMatrix[end][start] = 1
#显示顶点
def displayVertex(vertexIndex):
    print(lstVertices[vertexIndex].label, end=' ')
def getAdjUnvisitedVertex(vertexIndex):
    for i in range(vertexCount):
        if adjMatrix[vertexIndex][i] == 1 and not lstVertices[i].visited:
            return i
    return -1
def depthFirstSearch():
    lstVertices[0].visited = True
    displayVertex(0)
    push(0)
    while not isStackEmpty():
        unvisitedVertex = getAdjUnvisitedVertex(peek())
        if unvisitedVertex == -1:
            pop()
        else:
            lstVertices[unvisitedVertex].visited = True
            displayVertex(unvisitedVertex)
            push(unvisitedVertex)
    for i in range(vertexCount):
        lstVertices[i].visited = False
for i in range(MAX):
    for j in range(MAX):
        adjMatrix[i][j] = 0
addVertex('S')   # 0
addVertex('A')   # 1
addVertex('B')   # 2
addVertex('C')   # 3
addVertex('D')   # 4
addEdge(0, 1)    # S - A
addEdge(0, 2)    # S - B
addEdge(0, 3)    # S - C
addEdge(1, 4)    # A - D
addEdge(2, 4)    # B - D
addEdge(3, 4)    # C - D
print("Depth First Search:", end=' ')
depthFirstSearch()

输出

Depth First Search: S A D B C

点击查看深度优先搜索 (BFS) 算法的 C 实现

DFS 算法的复杂度

时间复杂度

DFS 算法的时间复杂度表示为 O(V + E)，其中 V 是节点数，E 是边数。

空间复杂度

DFS 算法的空间复杂度为 O(V)。

数据结构和算法

数据结构

链接列表

堆栈 &队列

搜索算法

排序算法

图形数据结构

树数据结构

递归

分而治之

贪婪算法

动态规划

近似算法

随机算法

DSA 有用资源

深度优先搜索 (DFS) 算法

深度优先搜索 (DFS) 算法

示例

输出

输出

输出

输出

DFS 算法的复杂度

时间复杂度

空间复杂度

颜色选择器

读后有收获微信请站长喝咖啡

错误报告

您的建议:

感谢您的帮助！