• 首页 首页 icon
  • 工具库 工具库 icon
    • IP查询 IP查询 icon
  • 内容库 内容库 icon
    • 快讯库 快讯库 icon
    • 精品库 精品库 icon
    • 问答库 问答库 icon
  • 更多 更多 icon
    • 服务条款 服务条款 icon

经典算法:深度优先搜索算法(DFS)

武飞扬头像
正经程序员
帮助44

前言

深度优先搜索算法(DFS)是一种用于遍历或搜索树或图的算法。这个算法会尽可能深的搜索树的分支。当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问为止。

深度优先搜索是图论中的经典算法,利用深度优先搜索算法可以产生目标图的拓扑排序表,利用拓扑排序表可以方便的解决很多相关的图论问题,如无权最长路径问题等。

image.png

在树中的深度优先搜索

树是一个无向图,其中任意两个顶点都通过一条路径连接。换句话说,任何无环连通图都是一棵树。对于一棵树,我们有以下遍历方法:

  • Preorder:在其子节点之前访问每个节点。
  • Postorder:在其子节点之后访问每个节点。
  • 中序(仅适用于二叉树):访问左子树、节点、右子树。

在图中的深度优先搜索

深度优先搜索 (DFS)是一种遍历与树的前序遍历密切相关的图的方法。以下是前序遍历的递归实现:

procedure preorder(treeNode v)
{
    visit(v);
    for each child u of v
        preorder(u);
}

要将其转换为图遍历算法,请将“child”替换为“neighbor”。但是为了防止无限循环,请跟踪已经发现的顶点而不是重新访问它们。

procedure dfs(vertex v)
{
    visit(v);
    for each neighbor u of v
        if u is undiscovered
            call dfs(u);
}

DFS递归实现

Java示例

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
 
// 存储图边的类
class Edge
{
    int source, dest;
 
    public Edge(int source, int dest)
    {
        this.source = source;
        this.dest = dest;
    }
}
 
// 表示图形对象的类
class Graph
{
    // 表示邻接列表的列表
    List<List<Integer>> adjList = null;
 
    Graph(List<Edge> edges, int n)
    {
        adjList = new ArrayList<>();
        for (int i = 0; i < n; i  ) {
            adjList.add(new ArrayList<>());
        }
 
        // 向无向图添加边
        for (Edge edge: edges)
        {
            int src = edge.source;
            int dest = edge.dest;
 
            adjList.get(src).add(dest);
            adjList.get(dest).add(src);
        }
    }
}
 
class Main
{
    // 对图上的图进行DFS遍历的函数
    public static void DFS(Graph graph, int v, boolean[] discovered)
    {
        // 将当前节点标记为已发现
        discovered[v] = true;
 
        // 打印当前节点
        System.out.print(v   " ");
 
        // 每条边 (v, u) 
        for (int u: graph.adjList.get(v))
        {
            // 如果 `u` 还没有被发现
            if (!discovered[u]) {
                DFS(graph, u, discovered);
            }
        }
    }
 
    public static void main(String[] args)
    {
        // 根据上图的图边列表
        List<Edge> edges = Arrays.asList(
                // 节点 0 未连接
                new Edge(1, 2), new Edge(1, 7), new Edge(1, 8), new Edge(2, 3),
                new Edge(2, 6), new Edge(3, 4), new Edge(3, 5), new Edge(8, 9),
                new Edge(8, 12), new Edge(9, 10), new Edge(9, 11)
            );
 
        // 图中的节点总数(标记为 0 到 12)
        int n = 13;
 
        // 从给定的边构建图
        Graph graph = new Graph(edges, n);
 
        // 跟踪是否发现顶点
        boolean[] discovered = new boolean[n];
 
        // 从所有未发现的节点执行 DFS 遍历到
        // 覆盖图的所有连通分量
        for (int i = 0; i < n; i  )
        {
            if (!discovered[i]) {
                DFS(graph, i, discovered);
            }
        }
    }
}

输出:0 1 2 3 4 5 6 7 8 9 10 11 12

复杂性分析:

  • 时间复杂度:  O(V E),其中 V 是顶点数,E 是图中的边数。
  • 空间复杂度:  O(V),因为需要一个额外访问的大小为 V 的数组。

O(E)可能在O(1)和O(V^2)之间变化,具体取决于图形的密集程度。

DFS迭代实现

DFS 的非递归实现类似于BFS 的非递归实现,但在两个方面有所不同:

  • 它使用堆栈而不是队列。
  • DFS 应该只在弹出顶点之后标记发现,而不是在推送它之前。
  • 它使用反向迭代器而不是迭代器来产生与递归 DFS 相同的结果。

Java示例

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
 
class Edge
{
    int source, dest;
 
    public Edge(int source, int dest)
    {
        this.source = source;
        this.dest = dest;
    }
}
 
class Graph
{
    // 表示邻接列表的列表
    List<List<Integer>> adjList = null;
 
    Graph(List<Edge> edges, int n)
    {
        adjList = new ArrayList<>();
        for (int i = 0; i < n; i  ) {
            adjList.add(new ArrayList<>());
        }
 
        // 向无向图添加边
        for (Edge edge: edges)
        {
            int src = edge.source;
            int dest = edge.dest;
 
            adjList.get(src).add(dest);
            adjList.get(dest).add(src);
        }
    }
}
 
class Main
{
    // 从顶点`v`开始,在图上执行迭代DFS
    public static void iterativeDFS(Graph graph, int v, boolean[] discovered)
    {
        // 创建一个用于迭代 DFS 的堆栈
        Stack<Integer> stack = new Stack<>();
 
        // 将源节点推入堆栈
        stack.push(v);
 
        // 循环直到堆栈为空
        while (!stack.empty())
        {
            // 从堆栈中弹出一个顶点
            v = stack.pop();
 
            // 如果顶点已经被发现,忽略
            if (discovered[v]) {
                continue;
            }
 
            // 如果弹出的顶点 `v` 还没有被发现,我们将到达这里;
            // 打印 `v` 并将其未发现的相邻节点处理到堆栈中
            discovered[v] = true;
            System.out.print(v   " ");
 
            // 为每条边 (v, u)
            List<Integer> adjList = graph.adjList.get(v);
            for (int i = adjList.size() - 1; i >= 0; i--)
            {
                int u = adjList.get(i);
                if (!discovered[u]) {
                    stack.push(u);
                }
            }
        }
    }
 
    public static void main(String[] args)
    {
        List<Edge> edges = Arrays.asList(
                // 请注意,节点 0 未连接
                new Edge(1, 2), new Edge(1, 7), new Edge(1, 8), new Edge(2, 3),
                new Edge(2, 6), new Edge(3, 4), new Edge(3, 5), new Edge(8, 9),
                new Edge(8, 12), new Edge(9, 10), new Edge(9, 11)
                // (6, 9) 引入循环
        );
 
        // 图中的节点总数(标记为 0 到 12)
        int n = 13;
 
        // 从给定的边构建图
        Graph graph = new Graph(edges, n);
 
        // 跟踪是否发现顶点
        boolean[] discovered = new boolean[n];
 
        // 从所有未发现的节点进行迭代 DFS 遍历到
        // 覆盖图的所有连通分量
        for (int i = 0; i < n; i  )
        {
            if (!discovered[i]) {
                iterativeDFS(graph, i, discovered);
            }
        }
    }
}

输出:0 1 2 3 4 5 6 7 8 9 10 11 12

DFS 的应用

  • 在图中查找连通分量。
  • DAG(有向无环图)中的拓扑排序。
  • 查找 2/3(边或顶点)连接的组件。
  • 寻找图的桥梁。
  • 寻找强连通分量。
  • 仅用一种解决方案解决难题,例如迷宫。
  • 在图形中寻找双连通性等等……

这篇好文章是转载于:学新通技术网

  • 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
  • 本站站名: 学新通技术网
  • 本文地址: /boutique/detail/tanfbebg
系列文章
更多 icon
同类精品
更多 icon
继续加载