Algorithms on Graphs: What is a graph?

the nodes (vertices) are connected by the lines (edges)

Graph Representation

Let’s take this graph as an example and see how we would represent it in code.

Adjacency Matrix

One way it could be represented would be by an adjacency matrix that looks like this.

Adjacency List

Another way we can condense space and search time of neighbors is through an adjacency list:

We could represent this using a hashmap or an array that contains ArrayList as elements

Summary

  • Graphs come in varying size and shape. We’ll discuss how they influence our algorithms in future posts.
  • A graph can be represented either as an adjacency matrix or an adjacency list.
  • An adjacency matrix allows us O(1) access if we know the node but take up O(V) times for searching neighbors and O(V²) space.
  • An adjacency list cuts our search time to O(E) and our memory to O(V + E).

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store