3

我有一个简单的加权图

    A
 1 / \\ 0.5
  /   \\0.5
 B     C

假设这描述了一个家庭，A 是父亲，B 是儿子，C 是母亲。假设 B 在大学读书，A 为他买了一套公寓。A和C住在共同拥有的房子里，50-50。

我想将图形转换为一棵树，从 A: 即开始。

  • A拥有C居住地50%的股份
  • A 拥有 B 居住地的 100%
  • C拥有A居住地50%的股份

图表和生成的树可能更精细，但我希望你能得到更一般的画面。

在 SQL Server 2005 上，我有

Drop Table #graph;
Create Table #graph
    (FirstVertex VarChar(1) Not Null, 
     SecondVertex VarChar(1) Not Null, 
     Weight float);

Insert #graph Values('A','B',1);
Insert #graph Values('A','C',0.5);
Insert #graph Values('C','A',0.5);

我正在使用以下公用表表达式来遍历图形，从“A”开始：

With GraphRecursion (FirstVertex, SecondVertex, Weight, Level)
As
(
    Select FirstVertex, SecondVertex, Weight, 0 As Level
    From #graph
    Where FirstVertex='A'

    Union all

    Select a.FirstVertex, a.SecondVertex, a.Weight, b.Level+1
    From #graph a 
    Inner Join GraphRecursion b
    On a.FirstVertex=b.SecondVertex --And b.Level<=1
)
Select * From GraphRecursion;

这引起

Msg 530, Level 16, State 1, Line 11
The statement terminated. The maximum recursion 100 has 
been exhausted before statement completion.

通过取消注释来限制递归级别会And b.Level<=1给出预期的结果，但这显然对任何实际用途都不是很有用。

有没有办法引用以前的迭代，以便在上面的示例边缘（即 FirstVertex、SecondVertex 对）中不会重复？

4

1 回答 1

3

您可以在另一列中建立已访问节点的列表，然后防止在递归中重新访问它们。像这样的东西（不确定我选择了正确的列）：

With GraphRecursion (FirstVertex, SecondVertex, Weight, Level,Nodes)
As
(
    Select FirstVertex, SecondVertex, Weight, 0 As Level,CONVERT(varchar(8000),':' + FirstVertex + ':' + SecondVertex + ':')
    From #graph
    Where FirstVertex='A'

    Union all

    Select a.FirstVertex, a.SecondVertex, a.Weight, b.Level+1,b.Nodes + ':' + a.SecondVertex  + ':'
    From #graph a 
    Inner Join GraphRecursion b
    On a.FirstVertex=b.SecondVertex --And b.Level<=1
    where not b.Nodes like '%:' + a.SecondVertex + ':%'
)
Select * From GraphRecursion;

如果你想避免每次重新遍历一条边，而不是重新访问一个顶点，你会建立你的链接，例如':' + FirstVertex + '@' + SecondVertex + ':'。在这些示例中，我只是使用 ':' 和 '@' 作为不出现在顶点名称中的字符。（避免重新遍历 - 更接近 b.Level <= 1 的结果，但不完全）：

With GraphRecursion (FirstVertex, SecondVertex, Weight, Level,Nodes)
As
(
    Select FirstVertex, SecondVertex, Weight, 0 As Level,CONVERT(varchar(8000),':' + FirstVertex + '@' + SecondVertex + ':')
    From #graph
    Where FirstVertex='A'

    Union all

    Select a.FirstVertex, a.SecondVertex, a.Weight, b.Level+1,b.Nodes + ':' + a.FirstVertex + '@' + a.SecondVertex  + ':'
    From #graph a 
    Inner Join GraphRecursion b
    On a.FirstVertex=b.SecondVertex --And b.Level<=1
    where not b.Nodes like '%:' + a.FirstVertex + '@' + a.SecondVertex + ':%'
)

（请注意，原始 b.Level <= 1 版本从此示例中获得 5 行，而不是我上面第二个示例中的 4 行）。但我相信这是正确的。b.Level <= 1 版本为 a->c、c->a、a->c 返回 2 级行，我认为我们不需要

于 2010-03-05T07:55:56.193 回答