如何找到图形的末端节点？

我的代码当前输出图中遍历的所有节点。如何找到图形的末端节点？

CREATE TABLE DAG(
    pid NUMBER, 
    cid NUMBER, 
    PRIMARY KEY(pid, cid) 
); 

WITH Ancestor(ancestor, descendant) AS 
( SELECT d.pid, d.cid 
    FROM DAG d 
    UNION ALL 
    SELECT d.pid, a.descendant 
    FROM Ancestor a 
    JOIN DAG d 
    ON d.cid = a.ancestor 
) 
SELECT * FROM Ancestor;

如何获取它以显示图形的所有末端节点？

来源

2014-05-17 JKL

对不起，现在这样也懒得离开来写这个伸到一个答案，但你想[这]（http://technology.amis.nl/2009/11/14/oracle-11gr2-alternative-for-connect_by_isleaf-function-for-recursive-subquery-factoring-dedicated-to-anton /） – Ben

怎么样;

SELECT * FROM dag WHERE cid NOT IN (SELECT pid FROM dag)

基本上它只是找到所有节点并删除所有作为另一个节点的父节点的节点。

编辑：在您编辑问题后，您似乎想要递归查找所有没有孩子的父母和祖父母;这里

WITH Ancestor(grandparent, parent, child) AS 
( SELECT 0, d.pid, d.cid FROM DAG d WHERE pid=1 
    UNION ALL 
    SELECT a.parent, a.child, d.cid 
    FROM Ancestor a 
    LEFT JOIN DAG d 
     ON d.pid = a.child 
    WHERE a.child IS NOT NULL 
) 
SELECT grandparent ancestor, parent descendant 
FROM Ancestor 
WHERE ancestor.child IS NULL;

你的基本情况是根节点（PID = 1），使用LEFT JOIN以递归找到所有祖父母/父母没有孩子，并将其显示为祖先/后代。

An SQLfiddle to test with。

来源

2014-05-17 20:40:37

一个非常聪明的方法！它确实假设表只包含完整的，一致的树，但没有循环... – Ben

我是算法和SQL的初学者。这将在我的代码中去哪里？ – JKL

@MNRC它取代你的递归查询。 http://sqlfiddle.com/#!4/d7beb/29 –

从评论

扩展答案：

WITH Ancestor(ancestor, leaf) AS 
( SELECT d.pid, d.cid 
    FROM DAG d 
    UNION ALL 
    SELECT d.pid, a.leaf 
    FROM Ancestor a 
    JOIN DAG d 
     ON d.cid = a.ancestor 
) 
SELECT leaf, ancestor 
FROM Ancestor a1 
WHERE NOT EXISTS (
    select 1 from ancestor a2 
    where a2.ancestor = a1.leaf 
)

来源

2014-05-17 21:12:14 Lennart

谢谢，这有助于很多。什么是“选择1”呢？我以前从来没有在SQL中看到过这个。 – JKL

这是一个重要的行的存在，而不是它的内容。选择1是一种古老的习惯，可以使用另一个常数，如-36，'a'或甚至*。如果列保证不包含可能已经使用的null – Lennart

如何找到图形的末端节点？

回答

相关问题