0回答
如何对隐式图使用DFS算法？
、、、、
我必须找出隐式图中是否存在s和t之间的路径，即具有未知顶点数量的图，仅由函数NEXT(v)定义，该函数返回与v相邻的顶点列表。顶点用自然数标识。对于图的正常表示(邻接表)，我将使用这种DFS算法(在伪代码中)： if (G.marked[w] =
浏览 0提问于2016-07-11得票数 1
回答已采纳
1回答
关于DFS的运行时间，我有一个问题。我知道它的O(n + m)，但根据wikipedia，还有另一个运行时间: O(b^d)。两者的区别是什么，还是相同的表示。这就是维基百科中所写的：“O(区E)表示不重复遍历的显式图，O(b^d)表示隐式图”。
浏览 1提问于2013-08-12得票数 0
1回答
据我所知，有三种常用的表示图的方法：也就是说，我在LeetCode上解决的问题通常使用矩阵，解决方案需要DFS或BFS。这是因为这个矩阵代表了一个图，还是DFS和BFS也适用于矩阵，而不仅仅是树和图？
DFS和BFS是否总是/主要针对实现中的矩阵(2D数组)使用，还是在某些情况下对Graph使用？
浏览 3提问于2020-04-26得票数 0
回答已采纳
Boost BGL有一个A*算法的版本，可以处理隐式图，即astar_search_no_init()函数。隐式图可以建模为IncidenceGraphs。说：“请注意，astar_search_no_init()必须用于隐式图；基本的astar_search()函数需要一个对顶点列表图概念建模的图形。这两个版本都需要图形类型来建模关联图概念。”这不意味着
浏览 3提问于2011-12-29得票数 2
回答已采纳
1回答
如何在隐式图中找到多个连通分量？
、、、、
然而，我不清楚该如何做。我发现有隐式图(由返回给定顶点的所有邻域的函数定义的图)。在这种情况下，这样的函数很容易实现。
问题是：如何修改DFS算法以在这种图形中找到组件？
浏览 2提问于2017-09-27得票数 0
回答已采纳
4回答
如何利用算法或DFS算法设计一种算法来确定非连通图的连通分量，该算法必须能够表示每个连通构件的顶点集合。3)反转所有弧(或找到图的转置或反向)
4)在反图中将所有顶点标记为未访问的顶点。5)从同一顶点v(与步骤2相同)开始，对反
浏览 21提问于2013-11-01得票数 6
2回答
我知道如何使用DFS变体找到无向图的交点。但它似乎是对无向图和只寻找后缘。但是，如果我的图有前向边或交叉边，我知道我总是可以为每个节点运行dfs，并且计算出它，但是有更好的算法吗？
浏览 3提问于2017-05-14得票数 0
2回答
人们总是说，如果向下有无限个节点，那么DFS将被困在这个无限长的分支中，永远不会在另一个分支中找到答案。
这不也适用于BFS吗？
浏览 3提问于2021-12-02得票数 1
回答已采纳
1回答
是拓扑排序的方法BFS还是DFS，哪个是对的？的算法与BFS(或DFS)相同吗？或者BFS(或DFS)只是卡恩算法的工具？
浏览 3提问于2021-10-11得票数 3
3回答
不连通图的最大二部匹配
、、、、
当您的图有多个组成部分时，如何找到最大二部匹配？每个组件都可以用两种方式着色。为了运行最大匹配例程，您如何确定两个集合X和Y？
浏览 1提问于2011-04-19得票数 3
2回答
图形库API
、、、
我正在创建一个库来支持一些标准的图遍历。一些图是显式定义的:即，通过提供数据结构或通过重复调用相关方法来添加所有边。有些图只能隐式定义:即，我只能提供一个函数，该函数在给定节点的情况下将返回其子节点(特别是，当然，我遍历的所有无限图都必须隐式定义)。
遍历生成器需要是高度可定制的。例如，我应该能够指定是否需要DFS后序/前序/按序、BFS等；访问子节点的顺序(如果我提供了对它们进
浏览 0提问于2013-04-13得票数 3
回答已采纳
1回答
我使用BitSet来跟踪是否使用DFS方法访问了图中的节点。为此，我创建了一个BitSet[]数组。BitSets本身可以在100.000到500.000项之间。 dfs(v, w); } dfs(v, w);
浏览 0提问于2017-05-10得票数 0
回答已采纳
4回答
如果给定一个图问题，我们如何知道我们需要使用bfs算法还是dfs算法？或者我们什么时候使用dfs算法或bfs算法。其中一种与另一种有什么区别和优势？
浏览 0提问于2010-04-13得票数 67
回答已采纳
1回答
访问无向图中的边、顶点
、、、
问题:您有一个无向图G = (V, E) (V =顶点，E=边)，并且您必须访问每个顶点并在两个方向上传递每个边。
我所知道的图形算法只有DFS、BFS和一些MST (Kruskal等)。我和我的朋友正在讨论这个问题，如果它是有向的，我会简单地DFS，然后DFS转置，但不幸的是图是无向的。我的朋友建议我们执行MST，并对MST进行DFS，然后通过迭代那些不在MST中的边来找到剩余的边。另外，如果边是无方向的，我如何在两个方向上通过它？
浏览 3提问于2013-04-03得票数 0
1回答
当你考虑一个完全图时，这个问题是一个NP-完全问题。因为在两个顶点之间有"(V-2)!"不同的路径。然而，似乎可以使用一种图遍历算法(DFS-BFS)来实现这一点，其时间复杂度是O(|V|+|E|)的多项式。
我对在多项式时间内解决NP完全问题感到困惑？你知道这里缺少什么吗？
浏览 0提问于2013-10-29得票数 0
1回答
我试图确定“有向图”是否是强连通的。'Austin': {'Houston': 300}, 'SanFrancisco': {'Albany': 1000}, 'NewYorkCity': { 'SanDiego': True }}就像我有这个伪码：
浏览 0提问于2017-05-09得票数 3
回答已采纳
我在SO上看到了很多关于回溯解释的帖子，但让我感到困惑的是，我什么时候才能真正使用回溯模板(选择-探索-取消选择)，而不是在解决问题时使用正常的DFS思维模式？我知道它们本质上都是回溯，但从解决问题的角度来看，当你看到这样的问题时，传统的DFS方法感觉要直观得多。但是，我想知道你的大脑什么时候应该去“选择-探索-取消选择”。例如:如果你想打印所有从根到叶的路径，一个简单的DFS问题解决方法很有意义，而在打印字符串的排列时，我们采取“选择-探索-取消选择”策略。我很难把问题归类到这两个方面。(分类是我当前<
浏览 27提问于2020-10-03得票数 0
2回答
在Kosaraju算法中，我遇到了两个可能的实现：( 2)在原图中按反图顶点的拓扑顺序搜索强连通分量。我想这样做是错误的，它是错误的，在原来的图中搜索强连通的分量时，使用的是反向拓扑顺序的顶点。这在内存方面也会更好，因为不需要一个新的邻接列表。
资料来源:1) ，2) CLRS图书。
浏览 5提问于2018-11-02得票数 2
回答已采纳
1回答
我试图构造一个使用DFS的算法来决定给定的有向图是否有唯一的拓扑排序。
我处理这个问题的方法是，只有一个特定的图有一个唯一的拓扑排序。这个图是一个链状图，在这个图中，所有的顶点在一条线上互相连接。我的困境是如何做一个有效的DFS算法，以及我到底应该检查什么。
浏览 2提问于2017-12-30得票数 0
云服务器
ICP备案
实时音视频
即时通信 IM
对象存储
腾讯云开发者
