数据库中如何存储有向图？

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 3492 天前的主题，其中的信息可能已经有所发展或是发生改变。

一个节点有多个父节点的结构

第 1 条附言 · 2015-05-15 10:46:31 +08:00

一个场景:知乎的话题结构，一个话题有多个父话题，可以有多个子话题，但没有循环。即有根无循环的有向图。

11 条回复 • 2017-03-14 10:26:20 +08:00

incompatible

2015-05-14 17:21:56 +08:00

两个表即可
node存储节点
transition存储边

davidlau

2015-05-14 17:45:00 +08:00

staticor

2015-05-14 18:30:41 +08:00

你可以参考 graphviz 的dot.language.

Grenadn

2015-05-14 19:35:22 +08:00 via Android

@davidlau 了解过，这种数据库太小众了，等几年说不定会流行。
@staticor 这个跟数据库好像没有关系诶。

omengye

2015-05-14 22:53:23 +08:00

两个字段,分别存每条边的始点,末点. 比如 A->C , B->E , C->E 这样,存的时候注意一下有没有环

Grenadn

2015-05-15 10:56:41 +08:00 via Android

@incompatible
@omengye
谢谢，二位应该说的是一个意思吧。添加了使用场景，场景中并没有特别使用图的特性计算，倒不如说恰巧实现了图结构，继续研究中。
（感觉自己好弱啊，数学成了瓶颈了(┯_┯)）

incompatible

2015-05-15 11:16:42 +08:00

@Grenadn 是一个意思。
你这场景就是个简单的多对多的关系嘛

Grenadn

2015-05-15 11:54:37 +08:00 via Android

@incompatible 实现是不难的，但多对多会不会有局限性？比如移除一个节点及其子节点这样的操作会很麻烦吧。

incompatible

2015-05-15 13:19:58 +08:00

@Grenadn 移除一个话题除了移除该话题与其子话题的关系，子话题也要一并移除？

Grenadn

2015-05-15 22:29:18 +08:00

@incompatible 的确，直接ban掉一个节点就行了。我是说类似的操作，需要构建的图的深度比较大的情况（从子节点回溯到原始节点），就不好办了。我可能想的有点多了:-P

EchoUtopia

2017-03-14 10:26:20 +08:00

发现一个现成的牛逼的ｄｊａｎｇｏ库，感觉满足我的要求了，如果树太深，可以把节点的祖先节点和子孙节点缓存起来就行了
https://github.com/elpaso/django-dag/tree/master/django_dag