lowest-common-ancestor

    0热度

    1回答

    给定一棵树，在Log（n）中找到从节点'a'到节点'b'的路径中的第k个节点？

    给定一棵树，我需要找到从'a'到'b'的路径中'第k个节点。这意味着我需要在从节点'a'到节点'b'的路径中的'第k'位置找到节点。我正在思考最低共同祖先和/或重光分解的问题，但我不确定这是否是这样做的。任何正确的方向指导表示赞赏。 详情： 的树不是二叉树。它是一个具有n-1个边，n个顶点和无周期的无向图。只是你的常规树 树的顶点编号从1到n。有n-1个无向边连接这些顶点的n-1对 'a'和'b'
    algorithm decomposition lowest-common-ancestor 2016-01-25

    1热度

    1回答

    在一组嵌套

    查找最近公共祖先我正在寻找一种方式来找到一个嵌套集合内的最低共同祖先可以使用一个公式来找到。 例如，从图像在：https://commons.wikimedia.org/wiki/File:Clothing-hierarchy-traversal.svg 套装和妇女之间的LCA是服装。我可以使用基于级别的系统来确定父级会面的位置，但是这种情况的用例是在数据库设计中，因此提高级别会对性能造成不利影响
    nested-set-model lowest-common-ancestor 2017-03-07

    1热度

    1回答

    如何确定节点w是否位于树中节点u和节点v之间的路径中？

    我想解决一个问题，需要我确定一个节点是否位于节点u和节点v之间的路径中（不一定是二进制）。 例如，对于下面的树： 1 2 3 4 5 6 7 节点2个位于从节点4的路径上至7 一个明显的解决方案将是，以获得树和横越的欧拉回路在两个节点的第一次出现之间访问的节点。但是，在最坏的情况下，这将是一个O（n）解决方案，其中n是树中节点的数量。我在某处读到，这可以使用LCA（最低共同祖先）完
    algorithm tree lowest-common-ancestor 2017-06-20

    0热度

    2回答

    Neo4j最低共同祖先节点未找到

    我已经加载了DNA SNP的分层树（DAG）。我想确定最低的共同祖先。 此查询的工作，产生一个正确的节点： Match (n:SNPNode{SNP:'R-Z11'}), (m:SNPNode{SNP:'R-BY13828'}) match path=(n)-[:SNPParent*..99]->(MRCA)<-[:SNPParent*..99]-(m) return MRCA.SNP 然
    neo4j cypher shortest-path genetic lowest-common-ancestor 2017-09-28

    2热度

    1回答

    树中两个节点之间的距离加权

    我的问题非常直截了当。 甲加权树中给出。我们必须找到两个给定节点之间的距离。 因为每次bfs超时，查询次数非常高（约75000），所以我尝试了不同的方式来做到这一点。 我的算法是这样的： 我跑从顶点0 DFS和根计算的距离（0）所有顶点这样的事情 depth[v]=depth[u]+w,where u is parent of v and w is weight b/w (u,v) 一旦我计算
    algorithm graph lowest-common-ancestor 2015-11-06

    1热度

    1回答

    如何使用HLD查找LCA？

    我有一棵树。我要回答的查询，如：路径 我使用重轻分解上的路径 获取和 增值。树中有n个节点和m查询。对于HLD，当我知道最低公共祖先时，我可以将u和v的任何查询分成两个不同的查询：从u到lca和v到。因此，查询将在O(log^2n)时间（log从u和v到lca和log为重路径上的分段树）上回答。 如您所知，HLD内置于O(n)时间，因此总时间为O(n + m*log^2n)。我的问题是如何使用已建
    algorithm tree lowest-common-ancestor 2016-12-13

    0热度

    2回答

    最低公共祖先 - 代码说明

    LCA通过顺序和后序遍历很容易实现和理解我。 但是，有一个递归的自下而上的方法。 我看了一下代码网上，我不明白一个行： 下面是代码： public Node lowestCommonAncestor(int val1, int val2,Node root){ if(root == null){ return null; } if(root.data ==
    algorithm binary-tree lowest-common-ancestor 2015-10-06

    0热度

    3回答

    最快的非递归实施LCA？

    这是我提出的非递归寻找二叉树中两个节点的最低公共祖先的算法。这里的基本策略： 使用字典/散列表来存储树。每个键值对代表一个节点及其父节点。 从两个节点的每一个开始，通过将代表每个节点值的变量设置为其父节点的值，将散列值存储在散列集中（两个节点中的每个节点都存储一个值）来遍历树。 当满足以下任何条件时，搜索完成：（a）两个节点的值相等;或者（b）当两条路径相互交叉时（即，节点1的遍历值的散列集包含节
    algorithm dictionary tree lowest-common-ancestor 2017-01-01

    2热度

    1回答

    父母/小孩isa中最低的共同祖先？层次Clojure中

    比方说，我们有这样的父/子层次： (derive ::integer ::decimal) (derive ::positive-integer ::integer) (derive ::long ::integer) 什么是Clojure的惯用实施办法找到这种分级结构中最低的共同祖先？即： (lca ::positive-integer ::long) ; => ::integer
    clojure lowest-common-ancestor 2016-01-21

    0热度

    1回答

    在循环图的DAG中应用LCA的解决方案？

    我的问题的答案可能很明显，我知道纸上的明显答案。我的意思是，当涉及到一些示例时，我明白为什么我们不允许运行最低公共祖先算法的循环，但是我在理解为DAG中的LCA解决方案编写的论文时遇到问题。等的解决方案，它部分阻止我们使用它的循环图.. 什么，我愿意了解并会感谢有关通知： 你能解释的解决方案之一LCA DAG中的问题，没有太多的表述？ 你能确定哪一步有问题吗？为什么？ 在我的问题 ，对节点的找到自
    algorithm graph directed-acyclic-graphs lowest-common-ancestor cyclic-graph 2017-01-04
最新问题