LeetCode---搜索算法

2023-10-31

LeetCode---搜索算法

搜索算法
- 图
LeetCode

搜索算法

图

图Graph的概念

图是一种由节点和边构成的数据结构，实际上树也是一种特殊的图。图可以用来表示现实世界中的很多事物：道路交通系统、航班线路、互联网连接等等。

顶点Vertex (节点Nond)：是图的基本组成部分，顶点具有名称标识key，也可以携带数据项payload。
边Edge（弧Arc）：作为两个顶点之间关系的表示，边连接两个顶点；边可以是无向或有向的，相应的图称为“无向图”和“有向图”。
权重Weight：为了表达从一个顶点到另一个顶点的代价，可以给边赋权；例如公交网中的两个站点之间的“距离”、“通行时间”和“票价”都可以作为权重。

在这里插入图片描述
路径Path：图中的路径，是由边依次连接起来的顶点序列；无权路径的长度为边的数量；带权路径的长度为所有边权重的和；如下图的一条路径(V3,V4,V0,V1)，其边为{(V3,V4,7),(V4,V0,1),(V0,V1,5)}。

圈Cycle：圈是首尾顶点相同的路径，如下图中(V5,V2,V3,V5V)是一个圈。如果有向图中不存在任何圈，则称为“有向无圈图”(directed acylic graph：DAG)。
在这里插入图片描述

图的抽象数据类型

在这里插入图片描述

邻接矩阵

优点：简单。
缺点：空间复杂度太高。
在这里插入图片描述

邻接列表

在这里插入图片描述

class Node(object):
    def __init__(self, key):
        self.key = key
        self.connected_to = {}

    # 添加一个边
    def add_nbr(self, nbr, weight=0):
        self.connected_to[nbr] = weight

    # 获取当前节点所有连接
    def get_connections(self):
        return self.connected_to.keys()

    # 获取当前节点的key
    def get_key(self):
        return self.key

    # 获取指定边的权重
    def get_weight(self, nbr):
        return self.connected_to[nbr]

    # 打印当前节点连接的所有节点信息
    def __str__(self):
        return str(self.key) + ' connected to: ' + str([x.key for x in self.connected_to])


class Graph(object):
    def __init__(self):
        self.nodes = {}
        self.node_num = 0

    # 添加节点
    def add_node(self, key):
        self.node_num += 1
        new_node = Node(key)
        self.nodes[key] = new_node
        return new_node

    # 通过key获取节点
    def get_node(self, key):
        return self.nodes.get(key)

    # 添加一条边
    def add_edge(self, from_node, to_node, weight=0):
        if from_node not in self.nodes:
            self.add_node(from_node)
        if to_node not in self.nodes:
            self.add_node(to_node)
        self.nodes[from_node].add_nbr(self.nodes[to_node], weight)

    # 获取图中所有节点
    def get_nodes(self):
        return self.nodes.keys()

    def __iter__(self):
        return iter(self.nodes.values())

    # in操作符
    def __contains__(self, key):
        return key in self.nodes

图的搜索算法

广度优先BFS

给定图G，已经开始搜索的起始顶点S。BFS搜索所有从S可到达其他顶点的边，并且在到达更远的距离k+1的顶点之前，BFS会找到全部距离为k的顶点。

# 标准的广度优先的基本流程
def bfs():
	定义队列;
	
    定义备忘录，用于记录已经访问的位置；
    
    判断边界条件，是否能直接返回结果的;

    将起始位置加入到队列中，同时更新备忘录;

    while 队列不为空:
        获取当前队列中的元素个数。
        for (元素个数):
            取出一个位置节点。
            判断是否到达终点位置。
            获取它对应的下一个所有的节点。
            for （每个节点）
	            条件判断，过滤掉不符合条件的位置。
	            新位置重新加入队列。

深度优先DFS

深度优先于广度优先算法流程基本一致，只是将队列改为了栈存储检查的节点。

# 标准的广度优先的基本流程
def bfs():
	定义栈;
	
    定义备忘录，用于记录已经访问的位置；
    
    判断边界条件，是否能直接返回结果的;

    将起始位置加入到栈中，同时更新备忘录;

    while 栈不为空:
        获取当前栈中的元素个数。
        for (元素个数):
            取出一个位置节点。
            判断是否到达终点位置。
            获取它对应的下一个所有的节点。
            for （每个节点）
	            条件判断，过滤掉不符合条件的位置。
	            新位置重新加入栈。

LeetCode---搜索算法