首页 > 其他分享 >第十一章 图论 Part1

第十一章 图论 Part1

时间:2024-09-04 13:37:02浏览次数:11  
标签:图论 graph self dfs Part1 第十一章 path 节点 append

任务

797. 所有可能的路径

给你一个有 n 个节点的 有向无环图(DAG),请你找出所有从节点 0 到节点 n-1 的路径并输出(不要求按特定顺序)

graph[i] 是一个从节点 i 可以访问的所有节点的列表(即从节点 i 到节点 graph[i][j]存在一条有向边)。

思路

题目所给的图的表示是邻接表,题意就是找到从i到n的所有路径,这里使用dfs。参考之前的回溯章节,区别是当时的各种情况的出发根节点可以认为是虚拟节点,在循环和递归中处理各种情况,而现在的出发节点是实际的图的点,需要提前加入到path中来保证正确。

class Solution:
    def __init__(self):
        self.result = []
        self.path = []

    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        self.path.append(0)
        self.dfs(graph,0,len(graph)-1)
        return self.result

    def dfs(self,graph,x,n): # 从x出发到n
        if x == n:
            self.result.append(self.path[:])
            return

        for i in graph[x]:
            self.path.append(i)
            self.dfs(graph,i,n)
            self.path.pop()

下面给出输入为 邻接矩阵的算法

class Solution:
    def __init__(self):
        self.result = []
        self.path = []

    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        self.path.append(0)
        self.dfs(graph,0,len(graph)-1)
        return self.result

    def dfs(self,graph,x,n): # 从x出发到n
        if x == n:
            self.result.append(self.path[:])
            return

        for i in graph[x][i]:
            if graph[x][i] == 1:
              self.path.append(i)
              self.dfs(graph,i,n)
              self.path.pop()

深度有限搜索(dfs)和广度优先搜索(bfs) 简析

可以认为树中的 先中后序遍历为dfs的特例,层序遍历为bfs的特例。

dfs适合的问题:

  1. 路径查找:在一些问题中,我们需要找到从起点到终点的一条路径(或所有路径)。DFS 很适合这种问题,因为它可以递归地探索每一条可能的路径,直到找到目标为止。
  2. 连通性问题:DFS 可以用于判断图是否连通,即图中是否存在一条从一个节点到另一个节点的路径。
  3. 拓扑排序:在处理有向无环图(DAG)时,DFS 可以用于生成拓扑排序
  4. 回溯算法:之前的回溯算法章节的问题都可以认为是dfs解决的问题

bfs适合的问题

  1. 最短路径问题:BFS 是在无权图中寻找两点之间最短路径的最优算法。因为 BFS 按层次遍历,所以首次到达目标节点时,一定是通过最短路径到达的。
  2. 层次遍历:BFS 按层次逐层遍历图或树结构,非常适合需要按照距离或层次关系处理的场景。
  3. 最小生成树(MST):在一些图算法中,BFS 可以用来生成最小生成树(虽然更常用的是 Prim 或 Kruskal 算法)。

bfs的参考代码

from collections import deque

# 表示四个方向
dir = [(0, 1), (1, 0), (-1, 0), (0, -1)]

def bfs(grid, visited, x, y):
    # 定义队列
    que = deque()
    # 起始节点加入队列
    que.append((x, y))
    # 只要加入队列,立刻标记为访问过的节点
    visited[x][y] = True

    while que:
        # 从队列取元素
        curx, cury = que.popleft() # 当前节点坐标

        # 开始向当前节点的四个方向左右上下去遍历
        for i in range(4):
            nextx = curx + dir[i][0]
            nexty = cury + dir[i][1]  # 获取周边四个方向的坐标

            # 坐标越界了,直接跳过
            if nextx < 0 or nextx >= len(grid) or nexty < 0 or nexty >= len(grid[0]):
                continue

            # 如果节点没被访问过
            if not visited[nextx][nexty]:
                # 队列添加该节点为下一轮要遍历的节点
                que.append((nextx, nexty))
                # 只要加入队列立刻标记,避免重复访问
                visited[nextx][nexty] = True

标签:图论,graph,self,dfs,Part1,第十一章,path,节点,append
From: https://www.cnblogs.com/haohaoscnblogs/p/18396266

相关文章

  • PART1-Oracle关系数据结构-分区、视图以及其他的对象
    4.分区、视图与其他对象4.1.分区概述分区允许您将非常大的表和索引分解成更小、更易于管理的部分,称为分区。每个分区是一个独立的对象,有自己的名称,并且可以选择拥有自己的存储特性。为了说明分区的概念,假设一个人力资源经理有一个大盒子,里面装着员工文件夹。每个文件夹都列出......
  • 代码随想录day50 || 图论基础
    图论基础定义图的构造方式1,邻接矩阵矩阵位置array[i][j]=k,i表示节点i,j表示节点j,[i][j]表示i-->j存在一条边,k表示的是边的权重邻接矩阵的优点:表达方式简单,易于理解检查任意两个顶点间是否存在边的操作非常快适合稠密图,在边数接近顶点数平方的图中,邻接矩阵是一种空......
  • 代码随想录 刷题记录-26 图论 (3)最小生成树
    一、prim算法精讲53.寻宝解题思路最小生成树是所有节点的最小连通子图,即:以最小的成本(边的权值)将图中所有节点链接到一起。图中有n个节点,那么一定可以用n-1条边将所有节点连接到一起。那么如何选择这n-1条边就是最小生成树算法的任务所在。例如本题示例中的无......
  • 代码随想录day16--图论
    题目描述:给定一个由1(陆地)和0(水)组成的矩阵,你需要计算岛屿的数量。岛屿由水平方向或垂直方向上相邻的陆地连接而成,并且四周都是水域。你可以假设矩阵外均被水包围。输入描述:第一行包含两个整数N,M,表示矩阵的行数和列数。后续N行,每行包含M个数字,数字为1或者0。输出描......
  • 《NET CLR via C#》---第十一章(事件)
    事件成员的类型提供了以下功能:方法能等级它对事件的关注方法能注销它对事件的关注事件发生时,登记的方法将收到通知CLR事件模型以委托为基础。委托是调用回调方法的一种类型安全的方式。对象凭借回调方法接受它们订阅的通知。设计要公开事件的类型在某些情况下,当某个事件......
  • 「代码随想录算法训练营」第五十二天 | 图论 part10
    目录Floyd算法题目:97.小明逛公园A*算法题目:126.骑士的攻击最短路算法总结Floyd算法Floyd算法用于求解多源最短路问题(求多个起点到多个终点的多条最短路径)。在前面学习的dijkstra算法、Bellman算法都是求解单源最短路的问题(即只能有一个起点)。注意:Floyd算法对边的权值正负没......
  • 第十章 单调栈 Part1
    目录任务739.每日温度思路496.下一个更大元素I思路503.下一个更大元素II思路任务739.每日温度给定一个整数数组temperatures,表示每天的温度,返回一个数组answer,其中answer[i]是指对于第i天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,请在该位置用0......
  • Study Plan For Algorithms - Part18
    1.搜索插入位置题目链接:https://leetcode.cn/problems/search-insert-position/给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。classSolution:defsearchInsert(self,nums:List[int],target:......
  • 第九章 动态规划Part13
    目录任务647.回文子串思路516.最长回文子序列思路任务647.回文子串给你一个字符串s,请你统计并返回这个字符串中回文子串的数目。回文字符串是正着读和倒过来读一样的字符串。子字符串是字符串中的由连续字符组成的一个序列。思路这道题的DP思路不是很直观,dp表示的......
  • 「代码随想录算法训练营」第五十一天 | 图论 part9
    目录Bellman_ford算法模拟过程题目:94.城市间货物运输IBellman_ford队列优化算法(又名SPFA)模拟过程题目:94.城市间货物运输IBellman_ford算法之判断负权回路题目:95.城市间货物运输IIBellman_ford算法之单源有限最短路题目:96.城市间货物运输IIIBellman_ford算法Bellman_ford算法......