SQL中的简单图搜索算法(PostgreSQL)

Question

我在PostgreSQL(不是树)中实现了节点图

表格的结构采用这种格式

id | node1  | node2 
--------------------
1  |   1    |   2
2  |   1    |   3
3  |   4    |   1
4  |   5    |   1
5  |   1    |   6

这显示了节点1与其连接的节点之间的关系.

我的问题

...是我需要一个函数或方法来在sql中查找特定的节点路径.

我想调用SELECT getGraphPath(startnode,targetnode)之类的函数,这将以任何形式显示路径(行或字符串)

例如SELECT getGraphPath(1,18)给出:

[1]-->[3]-->[17]-->[18]
[1]-->[4]-->[10]-->[18]

甚至是行:

Result  |
--------
1
3
17
18

我还想知道如何使用广度优先搜索和深度优先搜索来遍历图形.

Answer 1

像这样的东西:

with recursive graph_cte (node1, node2, start_id) 
as
( 
  select node1, node2, id as start_id
  from graphs
  where node1 = 1 -- alternatively elect the starting element using where id = xyz
  union all
  select nxt.node1, nxt.node2, prv.start_id
  from graphs nxt
    join graph_cte prv on nxt.node1 = prv.node2
)
select start_id, node1, node2
from graph_cte
order by start_id;

(需要PostgreSQL 8.4或更高版本)

Answer 2

SQL最适合操作图形和查找路径.您可能最好将图形加载到过程语言中,并使用Floyd-Warshall算法或Johnson算法来查找节点之间的路径.

但是,如果您真的必须使用SQL,那么我建议您选择一份Joe Celko的Smarties SQL,其中有一整章专门讨论SQL中的图形.