【深度优先搜索】和【广度优先搜索】的区别介绍

这篇具有很好参考价值的文章主要介绍了【深度优先搜索】和【广度优先搜索】的区别介绍。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一. 前言

深度优先搜索(Depth-First Search,DFS)和广度优先搜索(Breadth-First Search,BFS)是两种常见的图搜索算法。它们的主要区别在于搜索的方式和顺序不同。

二. 区别

1. DFS的搜索方式是:

从某个节点出发,沿着一条路径直到底部,然后返回到前一个节点,继续搜索下一条路径,直到搜索完整张图。DFS使用栈或者递归来实现搜索过程。

具体步骤如下:

  • 访问起始结点;
  • 递归地访问第一个未被访问的相邻结点,如果没有未被访问的相邻结点,则回溯到上一个结点继续递归;
  • 依次访问和递归每个未被访问的相邻结点,直到找到目标结点或到达叶子结点为止。

2. BFS的搜索方式是:

从某个节点出发,将其所有邻接节点加入到队列中,然后依次访问队列中的节点,将其邻接节点加入到队列中,以此类推,直到搜索完整张图。BFS使用队列来实现搜索过程。

具体步骤如下:

  • 将起始结点放入队列中;

  • 访问队列头部结点,将其未访问过的相邻结点加入队列尾部;

  • 将队列头部结点出队列;

  • 重复步骤 2 和 3,直到队列为空或找到目标结点。

三. 代码示例

1. 深度优先搜索代码示例:

示例一

def dfs(graph, start, target, path=[]):
    # 记录路径
    path = path + [start]
    # 到达目标结点,返回路径
    if start == target:
        return path
    # 遍历相邻结点
    for node in graph[start]:
        if node not in path:
            newpath = dfs(graph, node, target, path)
            if newpath:
                return newpath
    return None

示例二

class Graph:
    def __init__(self, graph_dict=None):
        if graph_dict is None:
            graph_dict = {}
        self.__graph_dict = graph_dict
 
    def add_vertex(self, vertex):
        if vertex not in self.__graph_dict:
            self.__graph_dict[vertex] = []
 
    def add_edge(self, edge):
        edge = set(edge)
        (vertex1, vertex2) = tuple(edge)
        if vertex1 in self.__graph_dict:
            self.__graph_dict[vertex1].append(vertex2)
        else:
            self.__graph_dict[vertex1] = [vertex2]
 
    def dfs(self, start, visited=None):
        if visited is None:
            visited = set()
        visited.add(start)
        print(start)
        for next in self.__graph_dict[start] - visited:
            self.dfs(next, visited)
        return visited
 
 
graph = {"A": {"B", "C"},
         "B": {"A", "D", "E"},
         "C": {"A", "F"},
         "D": {"B"},
         "E": {"B", "F"},
         "F": {"C", "E"}}
 
g = Graph(graph)
print("Depth First Search:")
g.dfs("A")

运行结果
【深度优先搜索】和【广度优先搜索】的区别介绍,python,数据结构-算法,深度优先,宽度优先,算法

2. 广度优先搜索代码示例:

示例一

from collections import deque

# 使用队列实现 BFS
def bfs(graph, start, target):
    # 使用 deque 实现双端队列
    queue = deque()
    queue.append(start)
    visited = set()
    visited.add(start)
    while queue:
        # 出队列
        node = queue.popleft()
        # 到达目标结点,返回
        if node == target:
            return True
        # 遍历相邻结点
        for neighbor in graph[node]:
            # 未访问过的结点入队列
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    # 没有找到目标结点
    return False

示例二

from collections import deque
 
 
class Graph:
    def __init__(self, graph_dict=None):
        if graph_dict is None:
            graph_dict = {}
        self.__graph_dict = graph_dict
 
    def add_vertex(self, vertex):
        if vertex not in self.__graph_dict:
            self.__graph_dict[vertex] = []
 
    def add_edge(self, edge):
        edge = set(edge)
        (vertex1, vertex2) = tuple(edge)
        if vertex1 in self.__graph_dict:
            self.__graph_dict[vertex1].append(vertex2)
        else:
            self.__graph_dict[vertex1] = [vertex2]
 
    def bfs(self, start):
        visited, queue = set(), deque([start])
        visited.add(start)
        while queue:
            vertex = queue.popleft()
            print(vertex)
            for neighbour in self.__graph_dict[vertex]:
                if neighbour not in visited:
                    visited.add(neighbour)
                    queue.append(neighbour)
 
 
graph = {"A": {"B", "C"},
         "B": {"A", "D", "E"},
         "C": {"A", "F"},
         "D": {"B"},
         "E": {"B", "F"},
         "F": {"C", "E"}}
 
g = Graph(graph)
print("Breadth First Search:")
g.bfs("A")

运行结果
【深度优先搜索】和【广度优先搜索】的区别介绍,python,数据结构-算法,深度优先,宽度优先,算法文章来源地址https://www.toymoban.com/news/detail-741543.html

四. 总结:

  • 深度优先搜索:倾向于深度遍历图中的分支,直到遇到叶子节点或目标节点;
  • 广度优先搜索:倾向于先遍历离起始节点较近的节点,然后逐步向下遍历。

到了这里,关于【深度优先搜索】和【广度优先搜索】的区别介绍的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构与算法基础-学习-24-图的遍历之DFS(深度优先搜索)和BFS(广度优先搜索)

    目录 一、遍历定义 二、遍历实质 三、DFS 四、BFS 五、宏定义 六、自定义类型 七、函数实现 1、DFS(邻接矩阵实现) 2、DFS(邻接表实现) 3、BFS(邻接矩阵实现) 4、BFS(邻接表实现) 5、打印邻接矩阵遍历顺序  6、打印邻接表遍历顺序 八、遍历算法效率分析 1、DFS 2、BFS 九

    2024年02月03日
    浏览(72)
  • 数据结构上机实验——图的实现(以无向邻接表为例)、图的深度优先搜索(DFS)、图的广度优先搜索(BFS)

      图采用邻接表存储结构,编程实现图的深度优先搜索和广度优先搜索算法。              2.1创建图 2.1.1定义图的顶点、边及类定义   我们定义一个 邻接表类(ALGraph) 。这里实现一些基础的数据结构。要注意结构体的嵌套。    Edge: 用于表示图中的边

    2024年02月04日
    浏览(52)
  • Python 算法基础篇:深度优先搜索( DFS )和广度优先搜索( BFS )

    深度优先搜索( DFS )和广度优先搜索( BFS )是两种常用的图遍历算法,用于在图中搜索目标节点或遍历图的所有节点。本篇博客将介绍 DFS 和 BFS 算法的基本概念,并通过实例代码演示它们的应用。 😃😄 ❤️ ❤️ ❤️ 深度优先搜索( DFS )是一种用于遍历或搜索图或树

    2024年02月07日
    浏览(65)
  • Python 图算法,图最短路径,图广度优先搜索,图深度优先搜索,图排序

    一、图数据库相关算法 图数据库是一种专门用来存储和处理图数据的数据库系统。它使用图结构来表示数据之间的关联关系,以及节点和边之间的属性信息。以下是一些常用的图数据库算法: 1. 最短路径算法:最短路径算法用于计算图中两个节点之间的最短路径,例如Dijk

    2024年02月15日
    浏览(34)
  • 图的遍历之 深度优先搜索和广度优先搜索

    深度优先搜索的图文介绍 1. 深度优先搜索介绍 图的深度优先搜索(Depth First Search),和树的先序遍历比较类似。 它的思想:假设初始状态是图中所有顶点均未被访问,则从某个顶点v出发,首先访问该顶点,然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图,直至

    2024年02月13日
    浏览(52)
  • 深度优先搜索(DFS)和广度优先搜索(BFS)

    深度优先搜索(DFS)和广度优先搜索(BFS)是图论中两个非常重要的算法,主要用于拓扑排序,寻路(走迷宫)和搜索引擎等。在我们写算法时经常会遇到需要使用DFS和BFS的题目,例如leetcode中的岛屿相关的问题以及有关树的题目大多都会使用DFS或者BFS。 深度优先搜索 深度优

    2024年02月10日
    浏览(45)
  • 深度优先搜索(DFS)和广度优先搜索(BFS)

    代码随想录 深度优先搜索和广度优先搜索,都是图形搜索算法,它两相似,又却不同,在应用上也被用到不同的地方。这里拿一起讨论,方便比较。 先给大家说一下两者大概的区别: 如果搜索是以接近起始状态的程序依次扩展状态的,叫广度优先搜索。 如果扩展是首先扩展

    2024年02月02日
    浏览(51)
  • 深度优先搜索(DFS、深搜)和广度优先搜索(BFS、广搜)

    目录 深度优先搜索(DFS、深搜)和广度优先搜索(BFS、广搜) 深度优先搜索(简称“深搜”或DFS) 广度优先搜索 总结 深度优先生成树和广度优先生成树 非连通图的生成森林 深度优先生成森林 广度优先生成森林 图 1 无向图 深度优先搜索的过程类似于树 的先序遍历 ,首先

    2024年01月20日
    浏览(48)
  • LeetCode-200. 岛屿数量【深度优先搜索 广度优先搜索 并查集 数组 矩阵】

    给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。 岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 此外,你可以假设该网格的四条边均被水包围。 示例 1: 输入:grid = [ [“1”,“1”,“1”,“

    2024年04月14日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包