MySQL:提取子图？

Question

我把一个大图的邻接列表存储在一个表中。

v1 |  v2
1  |  2
1  |  3
1  |  4
2  |  5
3  |  5
3  |  6
4  |  7
7  |  9
5  |  10

我试图从顶点1中提取出2跳图，这样除了(7,9)和(5,10)外，它还会返回上面列表中的所有边。我做到了：

SELECT * FROM stub_graph WHERE v1 IN (SELECT v1 FROM stub_graph WHERE v1=1 UNION select v2 FROM stub_graph WHERE v1=1) ;

我对我的解决办法并不特别满意，原因有二：

1. IN的存在
2. 这是能够提取链接，如1-2和2-5，但不能提取链接，如6-7。

有什么好办法吗？

为了防止有人对创建表感兴趣，下面是sql代码：

create table stub_graph(v1 int(11), v2 int(11));
insert into stub_graph VALUES(1,2);
insert into stub_graph VALUES(1,3);
insert into stub_graph VALUES(1,4);
insert into stub_graph VALUES(2,5);
insert into stub_graph VALUES(3,5);
insert into stub_graph VALUES(3,6);
insert into stub_graph VALUES(4,7);
insert into stub_graph VALUES(6,7);
insert into stub_graph VALUES(7,9);
insert into stub_graph VALUES(5,10);

Answer 1

试试这个：

SELECT g1.v1 as Root, g2.v1 as Next g3.v1 as Final FROM stub_graph g1 
  LEFT JOIN stub_graph g2 on g2.v1 = g1.v2
  LEFT JOIN stub_graph g3 on g3.v1 = g2.v2
WHERE g1.v1 = 1

如果你想(6-7)，但你需要走三个层次，因为它是3跳离1 (1-3，3-6，6-7)。

如果您想深入到任意的深度，您将需要查看一个递归存储的proc，我认为它支持MySQL的后期版本，但这看起来适合您的需要。或者，下面的链接还有其他一些想法。

这应该会产生：

Root | Next | Final
   1 |    3 |     5
   1 |    3 |     6
   1 |    2 |     5
   1 |    4 |     7

另见在分层数据上的这个链接