图论DFS得到从开始到结束节点的路径

图论是数学的一个分支，研究的是图的性质和图之间的关系。DFS（深度优先搜索）是图论中一种常用的搜索算法，用于遍历或搜索图的所有节点。

DFS从图的某个节点开始，沿着一条路径尽可能深地访问图的节点，直到到达不能继续前进的节点。然后回溯到前一个节点，继续探索其他路径，直到遍历完所有节点或找到目标节点。

DFS得到从开始节点到结束节点的路径的步骤如下：

从开始节点开始，将其标记为已访问。
检查当前节点是否为结束节点，如果是，则路径找到，结束搜索。
如果当前节点不是结束节点，遍历当前节点的邻居节点。
对于每个未访问的邻居节点，递归地应用DFS算法，将邻居节点作为新的当前节点。
如果所有邻居节点都已访问过或没有邻居节点，回溯到上一个节点，继续遍历其他路径。
重复步骤3-5，直到找到结束节点或遍历完所有节点。

DFS在图论中有广泛的应用，例如寻找图中的连通分量、判断图是否为二分图、拓扑排序等。在实际应用中，DFS也可以用于解决迷宫问题、路径规划、社交网络分析等。

腾讯云提供了多个与图论相关的产品和服务，例如腾讯云图数据库 Neptune，它是一种高性能、高可靠的图数据库，适用于存储和查询大规模图数据。您可以通过以下链接了解更多关于腾讯云图数据库 Neptune 的信息： https://cloud.tencent.com/product/neptune

请注意，以上答案仅供参考，具体的产品选择和推荐应根据实际需求和情况进行评估。

两点间最短路径生成树

graph、minimum-spanning-tree、spanning-tree

我有加权无向图。我需要找到尽可能小的代价的生成树，这样A点和B点之间的距离就会尽可能低。例如，我有一个图：。最小最小生成树看起来像。但这会使A和B之间的距离= 3。现在我要做的是：在图中查找AB之间的距离，使用BFS。使用DFS从步骤1找到AB之间的所有路径。从步骤2的每条路径生成生成树。比较它们，得到最小的。一切正常，直到我得到A距离= 12的图。第二步，然后花太多的时间。有什么更快的方法吗？谢谢。

浏览 0提问于2018-10-10得票数 1

4回答

如何找到所有最短的路径

algorithm、graph-theory、breadth-first-search、shortest-path

我有一个图，我想找到两个节点之间的所有最短路径。我通过BFS找到了两个节点之间的最短路径。然而，它只是给了我一条最短的路径，如果有超过一条。我怎样才能让他们都使用BFS呢？我用著名的BFS伪码实现了我的代码。此外，我有一个邻接列表向量，它保存所有节点的邻接顶点。

浏览 5提问于2013-11-28得票数 10

回答已采纳

2回答

通过无向边缘加权树查找最长路径

graph-theory、graph-traversal

我在寻找一种算法，通过边缘加权树找到最长的路径。这个图是无圈的和连通的，但是没有有向，只有稀疏连接的，没有定义的起点，可以有很多叶节点。最长的路径只能穿过一条边缘并通过一个顶点一次。一种简化的表示法，如本例所示，其中边权值与长度成正比。会有B-C-D-G-H-I。我看过标准的图遍历算法，例如BFS、DFS、MST等，但似乎都不适合我的问题。在我去实现一个蛮力算法之前，我想我会在这里检查任何建议的解决方案。

浏览 3提问于2022-10-21得票数 0

2回答

深度优先图算法的时间复杂度

algorithm、time-complexity、depth-first-search

我开始学习时间复杂度，我在示例中查找了一些简单排序的时间复杂度。我想知道如何使用|V|=n和|E|=m在图中计算深度优先搜索的平均时间复杂度，设开始节点为'u‘，结束节点为'v’。

浏览 0提问于2012-04-12得票数 23

回答已采纳

1回答

从MySQL数据库通过PHP计算两个“位置”之间的最短路径

php、mysql

我正在尝试找出获取/显示多个位置之间最短距离的最佳方法。为了更好地解释这一点，请将其视为一张地图，并使用以下内容。每个位置的所有距离和路径都已经放入MySQL数据库中。地点(Letter ->可到达的地点。和[]中的距离/时间) A -> B [5] A -> C [4] B -> Z [1] C -> Z [50] 所以A可以去B，只需要5分钟。而从A到C需要4分钟。现在我想弄清楚的是，假设有人说他们当前在位置A，想要到达Z。我如何让系统通过数据库来确定A -> B -> Z与A -> C -> Z相比是最短路径。我最初想在每个系统

浏览 0提问于2010-07-12得票数 1

回答已采纳

4回答

为什么有向无圈图中的最长路径需要拓扑排序？

graph、topological-sort、longest-path

问题:给定一个加权有向无圈图(DAG)和其中的一个源顶点，求出从s到给定图中所有其他顶点的最长距离。请找到参考图：为什么我们需要拓扑排序？我们不能简单地从源顶点使用修改后的BFS吗？为什么我们这么关心线性排序。如果这是重复，那么请将我转到相关的答案。谢谢

浏览 3提问于2014-12-23得票数 12

回答已采纳

2回答

查找所有BFS/DFS遍历

graph、traversal、graph-traversal

给定一个无向循环图，我希望通过广度优先搜索或深度优先搜索找到所有可能的遍历。给出了一个邻接表形式的图： A-BC B-A C-ADE D-C E-C 因此，从根A开始的所有BFS路径将是： {ABCDE,ABCED,ACBDE,ACBED} 对于DFS： {ABCDE,ABCED,ACDEB,ACEDB} 我如何以有意义的方式在算法上生成这些遍历？我想可以生成所有字母的排列并检查它们的有效性，但对我来说这似乎是最后的选择。任何帮助都将不胜感激。

浏览 3提问于2012-10-29得票数 4

回答已采纳

6回答

如何在O(n+m)中找到有向图的母点？

algorithm、graph-theory

有向图G= (V，E)中的母点是一个顶点v，使得从v到G的一条有向路可以到达所有其它顶点。给出了一个O(n+m)算法来检验图G是否包含母点。 (c)来自Skiena手册仅找到O(n(n+m))方式

浏览 0提问于2010-11-30得票数 7

2回答

星中的回溯

algorithm、search、a-star

蓝墙绿色高亮显示单元格=开放列表红色高亮显示单元格=封闭列表你好，有人能告诉我如何在星型搜索算法中实现回溯吗？我根据wiki实现了星型搜索，但它没有回溯，我的意思是回溯，如图中所示，开放列表(绿色单元格)包含2,0和3,3，0时，当前节点将“跳转”到3,3，因为成本现在超过3,3，并继续从那里搜索，如何才能使其从2,0 ->2，1->2，2.一路回到3,3然后从那里开始搜索？

浏览 5提问于2015-02-04得票数 3

回答已采纳

1回答

BFS和DFS在图上产生相同树的所有情况是什么？

graph、depth-first-search、breadth-first-search

我想知道在什么情况下，BFS和DFS从根植于任何节点的图生成相同的树。我知道其中一个例子是，图已经是一棵树了。这是唯一的案子吗？这取决于您选择节点的邻居的方式吗？挑选邻居的顺序会使它变得相同的方式有哪些呢？

浏览 2提问于2019-09-23得票数 0

1回答

理解图中进行遍历时的排序

data-structures

我试着理解深度第一和宽度第一的遍历在一个图形的上下文中。我所见过的大多数视觉示例都使用树来说明两者之间的区别。树中节点的排序比在图中的排序要直观得多(至少对我来说是这样)，从根节点从左到右从上到下排列节点是非常有意义的。在处理图时，我没有看到这样的自然排序。我看到了一个用不同节点标记为A但F的例子，其中作者解释了遍历，节点假定它们的标签的词法顺序。这似乎意味着节点所表示的值的类型必须具有内在的可比性。是这种情况吗？如有任何澄清，将不胜感激！

浏览 3提问于2015-03-23得票数 0

回答已采纳

2回答

C#算法搜索两个顶点之间的所有路径

c#、algorithm、graph、nodes、depth-first-search

最近给出了在C#中实现具有权值的有向图的任务。我是3/4的方式，但我必须使用测试数据，并返回答案的基础上的数据。我有图工作，我可以增加两个节点之间的成本，以及返回所有路径之间的两个节点使用深度优先搜索。令我困惑的是，其中一个问题是:找到从节点"C“到"C”的路由数目，费用小于30。给出的样本答案是 CDC, CBEC, CEBCDC, CDEBC, CEBCEBC, CEBCEBCEBC **7 in total** These are the input graph details "A to B: 5", "B to C: 4&

浏览 1提问于2015-04-10得票数 4

回答已采纳

2回答

二进制搜索和深度优先搜索有什么区别？

depth-first-search

执行二进制搜索通常会导致内存泄漏问题，尽管它比线性搜索更快。这两种搜索方法，深度优先搜索和二进制搜索，更适合搜索随机数。

浏览 0提问于2013-03-26得票数 1

1回答

使用BFS在图中找到最短的路径

c++、graph

我有由二维表表示的矩形图(我不能改变表示图形的形式)： bool graph[n][m]; //where n and m are dimensions of rectangle 一般情况是这样的：我的问题是：，在我的例子中，表示图的顶点之间的距离最好的方法是什么? 还有:在这种情况下，如何使用Dijkstry alghoritm的BFS找到从graph[x0][y0] graph[x1][y1]到graph[x1][y1]的最短路径？我试图在互联网上搜索合适的解决方案，但我只看到了基于向量、列表和结构的代码。重要编辑: 我很抱歉。我的图在开头是矩形的。然后，它得到一些变化(

浏览 5提问于2013-12-30得票数 0

2回答

有效的节点分组，可以到达彼此

javascript、jquery、algorithm、d3.js、underscore.js

我有一些图形数据，其中节点之间的边在这个表单上： var edges = [ ["A","B"], ["B","C"], ["B","D"], ["E","F"], ["E","G"] ]; 什么是最有效(运行时间)的方式来分组节点可以到达对方？就我而言： [["A","B","C","D"],["E","F","G"

浏览 4提问于2013-03-15得票数 1

2回答

DFS (深度优先搜索)树的DFS深度算法

algorithm、depth-first-search

根植于顶点的任何DFS (深度优先搜索)树的深度至少与根植于同一顶点的任何BFS树的深度相同。对还是错？我不明白这句话意味着什么？它要求的是堆栈深度吗？请用这个例子解释

浏览 3提问于2020-06-19得票数 1

回答已采纳

3回答

如何在不遍历所有图(有向图)的情况下找到导致节点A的节点

java、algorithm、graph、graph-algorithm

如何在不遍历所有图的情况下找到导致某些其他节点的所有节点？(有向图) 有办法做这个吗？是否有一些技术或算法可以帮助执行此任务而不必遍历所有图表？更新假设你的图有3条可以到达A的路径，你如何在不遍历所有图的情况下找到这3条路径？我不想要其中的一条路，而是所有的树。我来自关系数据库，在我看来，索引是索引，但是图表是不同的，所以我想问的是，是否有一种方法可以在不遍历所有图的情况下找到通向A的所有节点。或者在最坏的情况下，只遍历一次，然后我就可以查询结构中的路径。从SQL的角度来看，这类似于： SELECT nodes.id FROM Graph WHERE node.destinat

浏览 14提问于2020-05-15得票数 1

1回答

在python中使用dfs的euler电路

python、graph、depth-first-search

我正在尝试写一个程序来检查给定的矩阵是否有欧拉回路，我正在使用DFS进行检查，但我的递归调用中存在一些问题。对DFSvisited的第一个调用是DFSvisited(G<-如下所示，0，1，temp_path =0) def DFSvisited(G,i,j,temp_path): G[i][j]=0 G[j][i]=0 temp_path.append(j) for k in range(0,n): if G[j][k]==1: print 'j+++',j,"#### k",k

浏览 0提问于2014-05-12得票数 3

1回答

单连通有向图

java、c++、algorithm、graph、clrs

根据CLRS第三版的定义，单连通有向图是对每对顶点(u，v)最多有1条唯一路径的有向图，现在我读到的大多数答案是，我们从图中的每个顶点运行DFS，如果在任何情况下我们找到一个交叉边或前向边，那么该图就不是单连通的。我可以理解前向边的概念，但是在这张图上运行这个algo 1->2<-3给出的结果是不是单连通的，而这个图是单连通的。我们有一个来自3 -> 2或1 -> 2的交叉边，这取决于哪个版本开始了整个过程(1或3)。如果我们从顶点2开始DFS，那么我们有两个交叉边1 -> 2和3 -> 2。

浏览 0提问于2014-11-24得票数 3

回答已采纳

2回答