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

问题描述

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

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

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

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

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

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

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

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

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

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

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

甚至行:

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

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

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

推荐答案

是这样的:

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 或更高版本)

(requires PostgreSQL 8.4 or higher)

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