ruby 中的树和图数据结构 [英] Tree and graph data structures in ruby

问题描述

我很难找到要在 ruby​​ 中使用的树数据结构.有没有一些众所周知的我可以研究一下?我的要求很简单.我想创建一棵树(或者它可能是一个图形)并找到一些节点之间的距离.例如，我可能有一个如下所示的树/图

I'm having a hard time finding tree data structures to use in ruby. Are there some well known ones I can look into? My requirements are simple. I want to create a tree (or maybe it's a graph) and find the distance between some of the nodes. For example, I might have a tree/graph like the following

     A
   /   \
  B-----C
 / \     \ 
D   E     F

我希望能够找到根节点 (A) 和所有其他节点之间的距离.所以 (A, B) 之间的距离应该是 1，(A, E) 之间的距离应该是 2，等等.即使从节点 (A) 你可以通过 (A, B, C) 到达 (C)，长度应该仍然只是 1，因为有来自 (A, C) 的直接路径.

I want to be able to find the distances between the root node (A) and all the other nodes. So the distance between (A, B) should be 1, between (A, E) is 2, etc. Even though from node (A) you can get to (C) via (A, B, C), the length should still just be 1 since there is a direct path from (A, C).

是否有我可以在 ruby​​ 中使用的树/图形 gem ?

Is there a tree/graph gem I can use in ruby for this?

推荐答案

看看 gratr gem及其文档.它提供了用于表示各种类型图的类和用于查找顶点之间距离的基本算法(参见 距离模块).

Have a look at gratr gem and its documentation. It provides classes for representing various types of graphs and basic algorithms for finding distance between their vertices (see Distance module).

这篇关于ruby 中的树和图数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！