-
2 votesanswersviews
无向DFS:我如何提供彩色图作为外部属性?
我正在使用无向DFS(Depth First Search)算法implemented in boost::graph . 此算法需要顶点和边上的颜色值以跟踪已解析的颜色值 . 在the provided example中,代码将这些颜色值存储为图形的内部属性: typedef adjacency_list< vecS, vecS, undirectedS, ... -
1 votesanswersviews
深度优先搜索和回溯拼图
我正在尝试在我的算法中添加深度优先搜索以找到Peg Solitaire游戏的解决方案 . 现在看来,当我的算法尚未找到解决方案时,它的退出速度太快了 . 如果电路板上只剩下1个挂钩,则会找到解决方案 . 下面是我的函数 findSolution() ,这是一个递归函数 . direction 包含在电路板上向上,向下,向左和向右移动的所有坐标 . doJump 在参数板上移动 . un... -
0 votesanswersviews
使用python中的递归在dfs中超出了最大递归深度
我已经编写了一个python代码来解决使用python中的递归dfs的传教士和食人族问题 . 但是我不断收到此错误:RecursionError:超出最大递归深度 我不知道该怎么办,而且我已经坚持了很久 . 任何帮助或建议都将为我节省生命 . 谢谢 . 这是代码: class State(object): #left = 1 #right = 0 for boat def __in... -
0 votesanswersviews
DFS算法迷宫生成器
我正在尝试使用DFS算法在ASCII中创建迷宫('#'表示墙和''自由空间),其左上角开始,右下角出口 . 问题是迷宫开始创建,然后它被阻止,因为它的所有邻居都已被访问过 . 我从左上角开始,将单元格标记为已访问并放置一个''(它代表一个自由空间),然后我随机选择了一个单元格的邻居,我也这样做 . 但是我把它放在一个while循环中,我确信这不是个好主意 . 在这里我尝试DFS: int ... -
0 votesanswersviews
如何使用递归深度优先搜索算法判断所有顶点之间是否存在路径?
我试图判断一个图是否强烈连接 . 要符合强连接的条件,图形应具有以下属性:1)DFS算法将声明所有节点都可以从起始顶点到达2)当所有边的方向颠倒(转置图)时,所有节点都可以从起始顶点到达 . 这是我的DFS实现: public void dfs(String startName) { Vertex v = getVertex(startName); v.dist =... -
4 votesanswersviews
递归深度优先搜索算法
我正在尝试编写递归深度优先搜索算法,该算法采用表示图形的邻接列表并打印顶点的访问顺序 . 我的输入是存储为邻接列表的图形: graphAL2 = {0 : [1,2,3], 1 : [0,3,4], 2 : [0,4,5], 3 : [0,1,5], 4 : [1,2], 5 : [2,3] } 从那里,我编写了2个... -
6 votesanswersviews
拓扑排序是否尝试对顶点或边进行排序?
大家都快乐 . 我目前正在学习拓扑排序,并对拓扑排序尝试排序的问题提出疑问 . Algorithm Design Manual以这种方式描述拓扑排序: 拓扑排序是有向无环图(DAG)上最重要的操作 . 它在一条线上对顶点进行排序,使得所有有向边从左向右 . 这个大胆的部分让我困惑 . 拓扑排序排序顶点或所有有向边也是如此? 让我们举一个也在书中的例子 . 因此对于上述DAG,我们可以得到拓扑... -
7 votesanswersviews
如果拓扑排序使用DFS,它如何在断开连接的图上成功?
那里's a gap in my knowledge but I'我不确定究竟在哪里 . 可以使用深度优先搜索来完成拓扑排序,如wikipedia explains . 但是我只看到了为树实现的深度优先搜索,其中拓扑排序是针对DAG的 . 是树的一种特殊情况,其中边的隐含方向来自根节点 是用于拓扑排序的算法,而不是真正做DFS,只有很多类似的东西? 例如,拓扑排序可以处理断开连接的图形... -
1 votesanswersviews
为什么在尝试DFS此图时会出现StackOverFlowError?
我正在尝试编写一个算法来确定图表是否已连接 . 我认为我的代码几乎是正确的,尽管我一直得到StackOverFlowError . 我个人认为,因为图中有一个循环,我正在测试我的算法,我的代码不理解它并且循环 . 但我正在使用数组来查看是否已访问过某个节点!所以这不应该发生!无论如何这是我的代码: public int isConnected(String s) { i... -
6 votesanswersviews
为什么使用DFS在无向图中查找周期和拓扑排序以在有向图中查找周期?
对于无向图,如果我们需要找到一个循环,我们使用深度优先搜索,如in this older question所述,这是一种众所周知的方法,也是最优的 . 但对于有向图,this other question建议使用拓扑排序 . 我的问题是,为什么我们不能使用我们用于无向图的相同技术来检查有向图中的周期?我已经想到了各种情况,算法似乎总是同意 . 任何人都可以提出一些示例有向图,其中DFS无法找到一个... -
1 votesanswersviews
c#使用邻接列表的DFS拓扑排序有向图
我试图在下图中完成拓扑排序(摘自Steven Skiena的算法设计手册) .Graph to be Sorted根据book的答案是H,A,B,D,E,G,I,J,C,F但我一直得到A,B,D,E,C,F,H,G,I,J . 我不明白当拓扑排序意味着具有到目标节点的有向边的起始节点应该首先出现时,H如何能够前进到前面 . 书中给出的答案是否可以实现甚至是正确的?这种图形是否可以进行拓扑排序(因... -
0 votesanswersviews
Pyspark - 深度优先搜索数据帧
我有以下pyspark应用程序,它从子/父进程id的csv生成子/父进程序列 . 考虑到树的问题,我使用从叶节点开始的迭代深度优先搜索(没有子节点的进程)并迭代我的文件来创建这些闭包,其中进程1是进程2的父进程,即进程3的父进程依此类推 . 换句话说,给定如下所示的csv,是否可以使用pyspark数据帧和适当的pyspark-isms来实现深度优先搜索(迭代或递归),以生成所述闭包而无需使用.c... -
3 votesanswersviews
C#图遍历 - 跟踪任意两个节点之间的路径
寻找一种好方法来跟踪两个节点之间的广度优先遍历,而不了解图形的任何信息 . 与深度优先(如果它没有平移你可以扔掉路径)你可能在遍历期间有相当多的“开放”可能性 . -
7 votesanswersviews
算法枚举所有可能的路径
请考虑以下图表: 我正在尝试找到一种方法来枚举从源节点到目标节点的所有可能路径 . 例如,从A到E,我们有以下可能的路径: A B C D E A B C E A C D E A C E 注意,对于A C D E,实际上有2条路径,因为其中一条路径使用边缘F3而另一条路径使用边缘F5 . 此外,由于A和C之间存在循环,因此最终可能会有无限数量的路径,但出于此目的,我只对从源到目标的路径上没有重... -
0 votesanswersviews
为什么在实施深度优先搜索时使用队列数据结构使其成为广度优先搜索?
我知道深度优先搜索是使用LIFO数据结构实现的,并且像队列一样使用FIFO结构会为您提供广度优先搜索,但为什么呢? -
1 votesanswersviews
您是否在递归算法中以广度或深度搜索?
深度优先搜索使用LIFO / Stack . 广度优先搜索使用FIFO /队列 . 递归算法使用什么?两者结合? -
0 votesanswersviews
关注深度优先搜索[关闭]
证明如果G是无向连通图,那么它的每个边都在深度优先搜索树中或者是后边缘 . 现在,根据Steven Skiena的直觉和课堂讲座,我知道上述情况属实,因为它一直向下潜水,然后将绳索扔回到前一个顶点 . 我也知道DFS很适合寻找周期 . 但是,我的问题在于我不知道如何“证明”边缘是树边缘还是后边缘 . -
6 votesanswersviews
查找图中所有路径的理想算法[重复]
这个问题在这里已有答案: Find all paths between two graph nodes 10个答案 我们以此图为例: 现在让我们说我从顶点3开始并想要找到顶点7.深度优先搜索(取决于实现)将首先查看子节点 . 现在,在我们的例子中,为了参数,我从顶点2开始,然后转到顶点4和顶点2,返回到顶点并转到顶点7,问题解决了 . 我想要的是:我想得到所有可能的路径,从x到y(例如3到7... -
2 votesanswersviews
如何在2D数组中找到所有路径?
我正在尝试编写javascript,它将映射从root到leaf的所有唯一路径,每个节点都可以连接到下一行的相邻节点 . 例如,根可以连接到下一行,如4,2或4,4 . 叶子的独特路径是4,2,4,2,1 4 2 4 6 4 2 7 4 2 1 9 4 2 1 4 我能够将三角形转换为像这样结构的2D数组 . a... -
4 votesanswersviews
如何跟踪此对象图深度优先搜索算法的深度?
我有这个代码迭代一棵树,进行深度优先搜索 . 每个元素都只处理一次 . 很好 . -(void)iterateOverTree:(TreeNode *)node { NSMutableArray * elements = [NSMutableArray array]; [elements addObject:node]; while([elements count]) ... -
0 votesanswersviews
Depth-First-Search:订单重要吗?
我用Python构建了一个Depth-First-Search脚本,它遍历了一个图形 . 由于我没有最优的排序算法,DFS的可视化看起来有点奇怪 . 我的意思是我的DFS获取节点的顺序是可重现的,但它看起来很奇怪,因为我的图形类在内部逐行读取文本文件并将边(节点的元组)存储在一个集合中 . 当我启动算法时,它会扩展起始节点,查找它的邻居,移动并继续这个但是因为边缘是集合中的元组,有时我的DFS所采... -
0 votesanswersviews
仅使用深度优先和/或广度优先遍历将表达式树转换回字符串形式
我正在研究涉及表达树的遗传编程问题 . 我正在使用的树数据结构在深度优先和广度优先遍历方面仅提供访问器 . 我只使用这些提供的方法从树中恢复表达式的有效方法是什么? -
2 votesanswersviews
在深度首次搜索有向图时跟踪时间
我正在尝试对有向图进行深度优先搜索,并且在执行此操作时,我还尝试跟踪有关图的数据 . 首先,这是我用来构建有向图的类 . class Node(object): def __init__(self, name): self.name = str(name) def getName(self): return self.name def __str__(... -
2 votesanswersviews
C中的递归深度优先搜索(DFS)算法
我已经在类 Graph 中将图形实现为邻接矩阵,其中包含访问和修改它所需的所有函数,我在DFS算法中需要的函数 // for a Graph x, node v string x.get_node_value(v) //returns the the label of the node queue x.neighbors(v) //returns a queue with the adjacen... -
0 votesanswersviews
利用负循环查找图上两个节点之间零/负权重的路径
我真的很难在 Headers 中描述这个,但我会用更长的格式来试试 . 我真的很难解决这个问题,我不是在寻找答案,只需要一些帮助或一些特定的主题来阅读 . 我所拥有的是一个带有各种权重边缘的有向图,包括负数和正数 . 我试图做的是编写一个算法,该算法提供有两个位于图上的节点(并假设它们已连接)在它们之间找到一条路径,导致路径的总权重为零或负 . 该路径可以多次包括节点(希望允许路径偏移所包含边的正... -
3 votesanswersviews
查找两个节点之间是否存在深度优先搜索
我正在使用深度优先搜索和图表来查找是否存在2个节点之间的路由 . 但由于某种原因,即使有路径,我的方法总是会导致错误 . Here is my search code: static boolean search(Graph g, Node start, Node end) { if(start == null || end == null) return false; start.state... -
1 votesanswersviews
避免深度优先搜索(DFS)从无限循环中找到两个给定单元格的所有路径
有一个2D数组,我将找到从Begin-cell到Goal-cell的所有路径(无论最短/最长) . 并且在阵列(图形)上使用了DFS解决方案,并将探索单元格(节点) . c#like pseudocode: //setin A and B setAB(beginNode,goalNode); //collect info from where we was to explore other sub... -
0 votesanswersviews
在单个BFS / DFS运行中查找以邻接列表的形式存储的图形中的所有节点的深度
我是图论的新手,最近一直在解决一些问题 . I was looking for a way to find the depth of every node in the graph . 这是我在纸上形式化的方式: 运行for循环迭代每个顶点 如果未访问顶点,请运行以该顶点作为源的DFS 在DFS中,只要我们有更多的顶点去,我们继续前进(如在深度优先搜索中),我们保留一个计数器,c... -
8 votesanswersviews
为什么深度优先搜索说遭受无限循环?
我已多次读到DFS和BFS但是我怀疑这个问题已经挥之不去 . 在很多文章中提到DFS可能陷入无限循环 . 据我所知,通过跟踪访问的节点可以很容易地消除这种限制 . 事实上,在我读过的所有书中,这个小支票都是DFS的一部分 . 那么为什么“无限循环”被提到是DFS的缺点呢?是不是因为原始DFS算法没有对访问过的节点进行此检查?请解释 . -
0 votesanswersviews
使用DFS进行图形和树搜索之间的差异是什么?
假设我有这个graph并且我想使用从A到G的DFS,如果我将其转换为树搜索,是否会进行任何更改?我试过,这就是我找到的,如果我错了,请告诉我 图搜索:Frontier(LIFO): A B C E D F C E * C E G E E G是目标状态 对于树搜索,事情将是相同的,但只有图表可以更简单 我忽略了A,因为它已被访问过,我们可以发现在Explored list **中,当有...