A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition

Object-Oriented Graph Implementation

I demonstrated how a hash table can be used to implement a graph, but going forward, we’ll work with an object-oriented approach.

Here’s the beginning of an object-oriented graph implementation, using Ruby:

class Vertex
  attr_accessor :value, :adjacent_vertices

  def initialize(value)
    @value = value
    @adjacent_vertices = []
  end

  def add_adjacent_vertex(vertex)
    @adjacent_vertices << vertex
  end
end

The Vertex class has two primary attributes, the value and an array of adjacent_vertices. In our social network example, each vertex represents a person, and the value might be a string containing the person’s name. With a more complex application, we’d probably want to store ...