I thought it was about time that I tackle those tricky data structures: graphs.
I'm still learning about them myself, but I thought it'd be a good idea to go over the basic types of graphs so they'll be easier to recognize when you come across one.
Graphs are a data structure typically made up of vertices or nodes and edges.
Graphs are useful for connecting pieces of information into a network and showing how each piece is related to another. This is why they are typically used for real-life network problems like maps of phone lines or social network designs.
Graphs are slow and take a long time to implement and thus aren't used generally for scaling. They also aren't made to run well with algorithms built across the vertices.
There are two main categories when it comes to graphs: are they directed or undirected?
Directed graphs are graphs structures that have edges which have directions and will point to a specific vertex.
Undirected graphs are graph structures that don't have any specified directions and simply connect vertices to each other vertices.
It is also a very important distinction in graphs if they are cyclical or acyclic.
Cyclical graphs are graph structures that can eventually point back at their own vertex.
Acyclic graphs are graph structures that will never point back at their own vertex.
Graphs can also be distinguished by whether or not their edges are weighted. Weighted edges simply means they have an integer value attached to them. This would be typical of measuring distances on a map.
As you can imagine, unweighted edges are simply empty of any type of measuring value.
So when referring to graphs, we can now decide if they are either cyclic or acyclic and undirected or directed and weighted or unweighted. The most common combination of theses that you will find out in the wild are DAGs, directed acyclic graphs.
I've wrote the simplest implementation for a graph class in Ruby which can be used to build off many of the different types of graphs.
class GraphNode attr_accessor :value, :neighbors def initialize(value) @value = value @neighbors =  end def add_edge(neighbor) @neighbors << neighbor end end class Graph attr_accessor :nodes def initialize @nodes =  end def add_node(value) @nodes << GraphNode.new(value) end end
It isn't always easy to find resources in Ruby and I adored these articles about graphs in Ruby I came across:
- Graphs in Ruby
- Graph Data Structure in Ruby
- InterviewCake's Intro to the Graph Data Structure
- GeeksForGeeks Brief Overview of Graphs
Hopefully they'll be helpful for you as well. Next time I plan to go more in depth on each type of graph with code as well. Happy coding!