当前位置: 首页 > 知识库问答 >
问题:

无向/无权图节点集的枚举

钱德元
2023-03-14

A-B-C-D

A-B-C-E

A-B-C-F

我的想法是,我需要同时使用DFS和BFS,但我不确定这是否有效?

共有1个答案

公冶谦
2023-03-14

您基本上可以使用带有额外变量的DFS,该变量通过length递归传递,每次迭代都会减少。停止条件将是当这个额外变量达到0时。

类似于:

DFS(source,length,path):
   print path //this is always done, because we want all paths up to n
   if (length == 0): //stop clause
      return
   for each (source,u) is an edge:
       path.append(u)
       DFS(u,length-1,path)
       path.removeLast() //clean up environment

另一个(效率较低,但可能更优雅)是执行迭代深化DFS,使用length=1,2,...,n(并将打印内容仅放在stop子句中)

 类似资料:
  • 我需要帮助在一个未加权无向图中找到两个节点之间的所有最短路径。 我能够使用BFS找到一条最短路径,但到目前为止,我还不知道如何找到并打印出所有路径。 知道我可以使用的算法/伪代码吗?

  • 我正在编写一个使用电网格分析的程序。所以我有电路的节点[A,B,C,D]和连接节点[0,1,2,3,4,5,6,7,8]的分支。 如何在具有多条边的无向图中找到最短的循环? 图形图像(4个节点,9条边/分支): 周期: 我需要的循环数是:循环=分支-(节点-1),在本例中我需要6个循环。 我将这些数据存储在这样的数组中: 我很乐意看到任何语言的算法。

  • 我是斯坦纳树问题领域的初学者,我需要确定我的问题的名称,如果存在:给定无向、无权重、根图和一些顶点(模板节点)。我想构建树,其中所有的终端节点都是叶子,具有最小数量的斯坦纳顶点。有谁能为我找出这个问题的类(名称)以便阅读更多关于这个的信息。谢谢你们所有人

  • 总结 因此,我有一个有向无环加权图,其中每条边都有一个输入和输出节点,每个节点都有一个ID,我使用一个字典将所有传入的边映射到一个节点的ID,并使用另一个字典对所有传出的边进行同样的操作,这样,当出现节点ID时,我可以在大约O(1)时间内告诉所有传入和传出的边。 要求 我需要能够添加新的随机边(即连接两个随机节点),以保证无论图有多大,它都不会有任何循环。 我试过的 由于我完全控制如何构建我的图,

  • 我想知道什么是实现无向加权图的有效方法。我想在上面执行Prims和Kruskal算法。我知道邻接列表,但这不会浪费内存;为。假设我有两个顶点A和B,由权重为“x”的边连接,所以我需要在邻接列表中添加两个条目: 我是不是漏掉了什么?

  • 给定:有权边的有向无环图,其中一个节点可以有多个父节点。 问题:对于根节点的每个子节点,找到一条从该子节点到某个叶的最小代价(权重之和)路径。一个节点只能存在于一个这样的最小开销路径中。 图表示例: > 这个逻辑有道理吗?我担心这种消除冲突的迭代方式可能对某些图不收敛。例如,在重新计算节点2的最小路径时,如果现在发现2->5是最小路径,并且假设在第一次迭代期间,节点5在其他节点的最小路径中使用,那