无向无权根图的查找树
我是斯坦纳树问题领域的初学者，我需要确定我的问题的名称，如果存在：给定无向、无权重、根图和一些顶点（模板节点）。我想构建树，其中所有的终端节点都是叶子，具有最小数量的斯坦纳顶点。有谁能为我找出这个问题的类（名称）以便阅读更多关于这个的信息。谢谢你们所有人
共有1个答案
我想你是在寻找终端斯坦纳树问题。一个更常见的名字似乎是full Steiner树，例如这里。
还有一项关于未加权的全斯坦纳树的研究，它更接近于你所寻找的东西。
当你考虑一个未加权图时，减少树的顶点数量相当于减少边的数量，因为|V（T）|=|E（T）|1代表每棵树T。
为了确保根节点r包含在树中，您可以向图形中添加一个额外的节点r'和边{r，r'}，并使r'成为终端。
-
给定一个节点和边的加权无向图。边缘权重（整数）最大可达。存在查询。每个查询给出两个节点和一个整数绑定的。如果和之间存在路径，使得路径中的每个边权重都是，那么回答是else。 请注意，路径不一定要最短。路径上的最大权重是。天真的方法当然是行不通的。如何快速回答查询（在O(n，lg，n)或类似的情况下）？
-
考虑以下无向非循环图: 如果我们定义“根”为A和E，有没有算法可以确定产生的有向无环图？： 我考虑过从根开始尝试某种DFS或BFS，但我不确定如何处理“等待”的需要，以查看另一个根是否可能到达给定的节点。
-
我想知道什么是实现无向加权图的有效方法。我想在上面执行Prims和Kruskal算法。我知道邻接列表，但这不会浪费内存；为。假设我有两个顶点A和B，由权重为“x”的边连接，所以我需要在邻接列表中添加两个条目： 我是不是漏掉了什么？
-
我有一个无向图，我想从一个起始节点列出所有可能的路径。2个节点之间的每个连接在列出的路径中是唯一的，例如，给出以下图表示： 我无法使用现有的算法来完成它，我知道像DFS。任何帮助都将非常感谢。
-
我遇到了一个问题，我必须找出给定图形中的最长路径。我有一个边列表（例如，{AB，BC}），它表明在顶点/节点（A，B，C）之间有一条边。现在我想计算出可能的最长路径（不重复顶点），这样它可以覆盖从任何顶点/节点开始的最大节点。 解决这个问题的最佳方法是什么？我必须把它作为一个计划来实施。 我在谷歌上查找最小生成树、Dijkstra的算法等等。但我想不出什么最适合解决这个问题。 任何帮助或阅读参考资
-
A-B-C-D A-B-C-E A-B-C-F 我的想法是，我需要同时使用DFS和BFS，但我不确定这是否有效？