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
最新問題