What is a graph and why should I care?

A graph is an abstract data type (ADT) that is often used to model real-world situations and changes in state. Graphs also happen to be a superset of trees, another commonly used ADT.

  • A graph is made up of vertices or nodes, in Javascript a possible representation is an object.
  • Vertices may or may not be connected to each other by edges or arcs.
    • Edges can be either non-directional, uni-directional, or bi-directional.
    • If all of the edges are non-directional the graph is considered an undirected graph and if all of the edges are uni-directional than the graph is considered a directed graph. (Bidirected graphs are outside of the current scope of these articles, for now)
  • Edges can have a weight to them, in real-world situations this may represent something like distance.

This is all fine and dandy, but why should you give a crap about a seemingly obsure ADT that you may never have to implement? The only reason I can give you (ignoring learning for the sake of learning) are interviews. Graph traversal is a heavily discussed topic in software engineering interviews and many problems can be looked at and analyzed using traversal algorithms such as Breadth First and Depth First searches. Many interviewees struggle with graph traversal and this set of articles will help you and I perform better in interviews and understand computer science fundamentals more thoroughly.

Formal definition

Let's represent a graph using the syntax G = (V, E) with V being a set of vertices and E being a set of edges. Each edge is made up of a tuple (v, w) where v, w ∈ V and optionally including the weight of the edge.

Below is an illustration of a undirected graph with 8 vertices and 9 edges.

In the next installment we will go over an introduction to graph traversal and the breadth-first search!