再帰with句08 最小全域木問題

SQLパズル

最小全域木を求める。

問題


答え

データ作成スクリプト

create table minTree(
ID     char(1),
nextID char(1),
cost   number);

insert into minTree values('A','B',5);
insert into minTree values('A','C',2);
insert into minTree values('B','C',4);
insert into minTree values('B','D',2);
insert into minTree values('C','D',3);
insert into minTree values('C','E',2);
insert into minTree values('D','E',6);
insert into minTree values('D','F',6);
insert into minTree values('E','F',4);

insert into minTree
select nextID,ID,cost from minTree;
commit;

SQL

col path for a30

with rec(LV,ID,NextID,cost,path) as(
select 1,ID,nextID,cost,
cast('(' || ID || nextID || ')' as varchar2(100))
  from minTree
 where ID = 'A'
union all
select a.LV+1,b.ID,b.nextID,
case when instr(a.path,b.ID || b.nextID) > 0
       or instr(a.path,b.nextID || b.ID) > 0
     then a.cost else a.cost+b.cost end,
a.path || '(' || b.ID || b.nextID || ')'
  from rec a,minTree b
 where a.nextID = b.ID
   and a.cost < 5+2+4+2+3+2+6+6+4
   and a.LV <= 10)
select cost,path
  from (select cost,path,rank() over(order by cost,LV) as rn
          from rec
         where path like '%A%' and path like '%B%'
           and path like '%C%' and path like '%D%'
           and path like '%E%' and path like '%F%')
 where rn=1;

解説

階層問い合わせでは、同じノードに再訪できませんが、
再帰with句では、同じノードに再訪できるのです。