ruby – 邻接列表和图表

发布时间：2020-12-16 21:57:50 所属栏目：百科来源：网络整理

导读：我正在尝试通过邻接列表构建一个图,这意味着我需要一个所有节点的列表,在每个节点类中,我还需要一个数据结构来保存所有相邻的节点.只是想知道最好的结构是做什么(快速搜索目标节点类).一个数组可以工作吗？解决方法这是在 Ruby中构建有向图的一种方法,其中

我正在尝试通过邻接列表构建一个图,这意味着我需要一个所有节点的列表,在每个节点类中,我还需要一个数据结构来保存所有相邻的节点.只是想知道最好的结构是做什么(快速搜索目标节点类).一个数组可以工作吗？

解决方法

这是在 Ruby中构建有向图的一种方法,其中每个节点都维护对其后继者的引用,但可以通过名称引用节点.首先我们需要一个节点类：

class Node

  attr_reader :name

  def initialize(name)
    @name = name
    @successors = []
  end

  def add_edge(successor)
    @successors << successor
  end

  def to_s
    "#{@name} -> [#{@successors.map(&:name).join(' ')}]"
  end

end

每个节点都保留对其后继者的引用.不知道你需要什么样的操作,我没有定义任何实际上做图遍历,但是每个节点对它的后继都有引用,使得遍历该图很简单.

现在我们将创建一个类来表示整个图形：

class Graph

  def initialize
    @nodes = {}
  end

  def add_node(node)
    @nodes[node.name] = node
  end

  def add_edge(predecessor_name,successor_name)
    @nodes[predecessor_name].add_edge(@nodes[successor_name])
  end

  def [](name)
    @nodes[name]
  end

end

该类保留其节点的哈希,以名称键入.这使得特定节点的检索变得容易.

这是一个包含循环的图的示例：

graph = Graph.new
graph.add_node(Node.new(:a))
graph.add_node(Node.new(:b))
graph.add_node(Node.new(:c))
graph.add_edge(:a,:b)
graph.add_edge(:b,:c)
graph.add_edge(:c,:a)
puts graph[:a]    #=> a -> [b]
puts graph[:b]    #=> b -> [c]
puts graph[:c]    #=> c -> [a]

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!