跳到主要内容

深度优先搜索（DFS）

提示
  1. 基本概念：深度优先搜索（DFS）是一种在图形或树结构中遍历或搜索所有顶点的递归算法，按照深度优先的顺序进行。
  2. 算法过程：DFS开始于任一顶点，并将顶点标记为已访问，然后递归访问其所有未访问的邻接顶点，直到所有顶点都被访问。该过程使用堆栈来存储待访问顶点，并在顶点没有未访问邻接点时回溯。
  3. 应用场景：DFS用于路径查找、检查图的二分性、找出图的强连通分量、检测循环等场合，其时间复杂度为O(V + E)，空间复杂度为O(V)，其中V和E分别是图的顶点数和边数。

深度优先搜索或深度优先遍历是一种用于搜索图形或树数据结构的所有顶点的递归算法。遍历意味着访问图形的所有节点。

深度优先搜索算法​

标准的DFS实现将图的每个顶点放入以下两个类别之一：

  1. 已访问
  2. 未访问

该算法的目的是标记每个顶点为已访问，同时避免循环。

DFS算法工作原理如下：

  1. 从将图的任何一个顶点放在堆栈的顶部开始。
  2. 取堆栈的顶部项目并将其添加到已访问列表中。
  3. 创建该顶点的相邻节点列表。将未在已访问列表中的节点添加到堆栈的顶部。
  4. 重复执行步骤2和3，直到堆栈为空。

深度优先搜索示例​

让我们通过一个示例看看深度优先搜索算法是如何工作的。我们使用一个具有5个顶点的无向图。

我们从顶点0开始，深度优先搜索算法首先将其放入已访问列表中，并将其所有相邻顶点放入堆栈中。

我们从顶点0开始，深度优先搜索算法首先将其放入已访问列表中，并将其所有相邻顶点放入堆栈中。

从将其放入已访问列表并将其所有相邻顶点放入堆栈开始。

接下来，我们访问堆栈顶部的元素，即1，并转到其相邻节点。由于0已经访问过，我们转而访问2。

接下来，我们访问堆栈顶部的元素，即1，并转到其相邻节点。由于0已经访问过，我们转而访问2。

顶点2有一个未访问的相邻顶点4，因此我们将其添加到堆栈的顶部并访问它。

顶点2有一个未访问的相邻顶点4，因此我们将其添加到堆栈的顶部并访问它。

顶点2有一个未访问的相邻顶点4，因此我们将其添加到堆栈的顶部并访问它。

当我们访问最后一个元素3时，它没有未访问的相邻节点，因此我们已完成了图的深度优先遍历。

当我们访问最后一个元素3时，它没有未访问的相邻节点，因此我们已完成了图的深度优先遍历。

DFS伪代码（递归实现）​

下面是DFS的伪代码。在init()函数中，注意我们对每个节点运行DFS函数。这是因为图可能具有两个不同的不连通部分，为了确保覆盖每个顶点，我们还可以在每个节点上运行DFS算法。

DFS(G, u)
    u.visited = true
    for each v ∈ G.Adj[u]
        if v.visited == false
            DFS(G,v)

init() {
    For each u ∈ G
        u.visited = false
     For each u ∈ G
       DFS(G, u)
}

Python、Java和C/C++中的DFS实现​

以下是深度优先搜索算法的示例代码，带有示例。代码已经简化，以便我们可以专注于算法而不是其他细节。

Python Java C C++

# Python中的DFS算法


# DFS算法
def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)

    print(start)

    for next in graph[start] - visited:
        dfs(graph, next, visited)
    return visited


graph = {'0': set(['1', '2']),
         '1': set(['0', '3', '4']),
         '2': set(['0']),
         '3': set(['1']),
         '4': set(['2', '3'])}

dfs(graph, '0')
// Java中的DFS算法

import java.util.*;

class Graph {
  private LinkedList<Integer> adjLists[];
  private boolean visited[];

  // 创建图
  Graph(int vertices) {
    adjLists = new LinkedList[vertices];
    visited = new boolean[vertices];

    for (int i = 0; i < vertices; i++)
      adjLists[i] = new LinkedList<Integer>();
  }

  // 添加边
  void addEdge(int src, int dest) {
    adjLists[src].add(dest);
  }

  // DFS算法
  void DFS(int vertex) {
    visited[vertex] = true;
    System.out.print(vertex + " ");

    Iterator<Integer> ite = adjLists[vertex].listIterator();
    while (ite.hasNext()) {
      int adj = ite.next();
      if (!visited[adj])
        DFS(adj);
    }
  }

  public static void main(String args[]) {
    Graph g = new Graph(4);

    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 3);

    System.out.println("以下是深度优先遍历");

    g.DFS(2);
  }
}
// C语言中的深度优先搜索算法

#include <stdio.h>
#include <stdlib.h>

struct node {
  int vertex;
  struct node* next;
};

struct node* createNode(int v);

struct Graph {
  int numVertices;
  int* visited;

  // 我们需要int**来存储二维数组。
  // 同样，我们需要struct node**来存储链表数组
  struct node** adjLists;
};

// 深度优先搜索算法
void DFS(struct Graph* graph, int vertex) {
  struct node* adjList = graph->adjLists[vertex];
  struct node* temp = adjList;

  graph->visited[vertex] = 1;
  printf("访问 %d \n", vertex);

  while (temp != NULL) {
    int connectedVertex = temp->vertex;

    if (graph->visited[connectedVertex] == 0) {
      DFS(graph, connectedVertex);
    }
    temp = temp->next;
  }
}

// 创建一个节点
struct node* createNode(int v) {
  struct node* newNode = malloc(sizeof(struct node));
  newNode->vertex = v;
  newNode->next = NULL;
  return newNode;
}

// 创建图
struct Graph* createGraph(int vertices) {
  struct Graph* graph = malloc(sizeof(struct Graph));
  graph->numVertices = vertices;

  graph->adjLists = malloc(vertices * sizeof(struct node*));

  graph->visited = malloc(vertices * sizeof(int));

  int i;
  for (i = 0; i < vertices; i++) {
    graph->adjLists[i] = NULL;
    graph->visited[i] = 0;
  }
  return graph;
}

// 添加边
void addEdge(struct Graph* graph, int src, int dest) {
  // 从src到dest添加边
  struct node* newNode = createNode(dest);
  newNode->next = graph->adjLists[src];
  graph->adjLists[src] = newNode;

  // 从dest到src添加边
  newNode = createNode(src);
  newNode->next = graph->adjLists[dest];
  graph->adjLists[dest] = newNode;
}

// 打印图
void printGraph(struct Graph* graph) {
  int v;
  for (v = 0; v < graph->numVertices; v++) {
    struct node* temp = graph->adjLists[v];
    printf("\n 顶点 %d 的邻接列表\n ", v);
    while (temp) {
      printf("%d -> ", temp->vertex);
      temp = temp->next;
    }
    printf("\n");
  }
}

int main() {
  struct Graph* graph = createGraph(4);
  addEdge(graph, 0, 1);
  addEdge(graph, 0, 2);
  addEdge(graph, 1, 2);
  addEdge(graph, 2, 3);

  printGraph(graph);

  DFS(graph, 2);

  return 0;
}
// C++中的深度优先搜索算法

#include <iostream>
#include <list>
using namespace std;

class Graph {
  int numVertices;
  list<int> *adjLists;
  bool *visited;

   public:
  Graph(int V);
  void addEdge(int src, int dest);
  void DFS(int vertex);
};

// 初始化图
Graph::Graph(int vertices) {
  numVertices = vertices;
  adjLists = new list<int>[vertices];
  visited = new bool[vertices];
}

// 添加边
void Graph::addEdge(int src, int dest) {
  adjLists[src].push_front(dest);
}

// 深度优先搜索算法
void Graph::DFS(int vertex) {
  visited[vertex] = true;
  list<int> adjList = adjLists[vertex];

  cout << vertex << " ";

  list<int>::iterator i;
  for (i = adjList.begin(); i != adjList.end(); ++i)
    if (!visited[*i])
      DFS(*i);
}

int main() {
  Graph g(4);
  g.addEdge(0, 1);
  g.addEdge(0, 2);
  g.addEdge(1, 2);
  g.addEdge(2, 3);

  g.DFS(2);

  return 0;
}

深度优先搜索的复杂性​

深度优先搜索（DFS）算法的时间复杂度表示为 O(V + E)，其中 V 是节点数，E 是边数。

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

DFS 算法的应用​

  1. 寻找路径
  2. 检查图是否是二分图
  3. 寻找图的强连通分量
  4. 检测图中的循环
最后于 更新