SQL中的简单图形搜索算法（PostgreSQL）

问题描述

我在PostgreSQL中实现了一个节点图（不是树）。

表的结构是这种格式的。

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

这显示了节点1和它连接的节点之间的关系。

我的问题

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

我想调用像SELECT getGraphPath（startnode，targetnode）这样的函数，并且这将显示任何形式的路径（行或字符串）。

例如SELECT getGraphPath（1,18）给出：

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

甚至行：

 结果| 
 -------- 
 1 
 3 
 17 
 18 
  

我还想知道如何使用广度优先搜索和深度优先搜索来遍历图。 解析方案

使用递归graph_cte（node1，node2，node1，node2， start_id）
as
（
）选择node1，node2，id作为start_id $ b $ from图形
其中node1 = 1 - 或者使用where id = xyz选择起始元素
union all
从图表nxt
中选择nxt.node1，nxt.node2，prv.start_id
加入graph_cte prv on nxt.node1 = prv.node2
）
从graph_cte中选择start_id，node1，node2

按start_id排序;

（需要PostgreSQL 8.4或更高版本）

I've implemented a graph of nodes in PostgreSQL (not a tree)

the structure of the table is in this format

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

This shows the relationships between the node 1 and the nodes it is connected to.

My Problem

...is that i need a function or method to find a particular node path in sql.

I want to call a function like SELECT getGraphPath(startnode,targetnode) and this will display the path in any form(rows, or strings)

e.g. SELECT getGraphPath(1,18) gives:

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

or even rows:

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

I'd also like to know how to traverse the graph using breadth first search and depth first search.

解决方案

Something like this:

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;

(requires PostgreSQL 8.4 or higher)

这篇关于SQL中的简单图形搜索算法（PostgreSQL）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！