DataStructures Series #15 – The Graph ADT

The Graph ADT is meant to implement the directed and undirected graph concepts from the field of graph theory within mathematics.

A graph data structure consists of vertices (nodes) and edges connecting the vertices. A graph with direction on the edges are called directed graphs while edges without direction are called undirected graphs as shown in the image below.

Image source: https://www.differencebetween.com/

Representations

The graph ADT can be represented in the different data structures shown below:

  • Adjacency matrix
Representing Graphs -
image source: http://occcwiki.org/

The matrix above is a 6 by 6 matrix representing the vertices (nodes) in the labelled graph.

The ones represent nodes that have edges while zeros shows that there are no edges connecting the nodes.

For example, position 1,1 on the matrix is 1, and we can see on the graph that there is indeed an edge connecting 1 to itself. Position 2,3 or 3,2 also has 1 indicating a connection between node 2 and 3. Position 3,5 or 5,3 for example is 0 and can be seen on the graph that there isn’t indeed an edge connecting node 3 and 5.

Please Note: We can pick both directions for an undirected graph, this of course will change if the graph is directed for example, 3,5 can be 1 while 5,3 is 0.

  • Adjacency list
image source: http://occcwiki.org/

The graph above can be represented in a list form as shown below:

ab,c
ba,c
ca,b

The column on the left are the nodes in the graph and the column on the right contains all the connected nodes.

Please Note: We can pick both directions for an undirected graph, this of course will change if the graph is directed for example, a can point to vertix b and not vice versa.

  • Incidence matrix

image source: https://en.wikipedia.org/

In the incidence matrix, the edges are labelled and then a matrix is created from the labelled edges and the nodes as shown in the table and matrix below.

e1e2e3e4
11110
21000
30101
40011
{\displaystyle {\begin{pmatrix}1&1&1&0\\1&0&0&0\\0&1&0&1\\0&0&1&1\\\end{pmatrix}}.}
image source: https://en.wikipedia.org

Operations

  • Adjacent (x, y) – tests if there is a direct edge linking x and y
  • Neighbours (x) – gets all vertices linked directly to x
  • AddVertex (x) – add vertex x if it doesn’t already exist
  • RemoveVertex (x) – removes vertex x if it exists
  • AddEdge (x, y) – adds vertex x to y if it doesn’t exist
  • RemoveEdge (x, y) – removes vertex x to y if it doesn’t exist
  • GetVertexValue (x) – returns vertex x value
  • Graph Traversal

The graph traversal is the most important operation as all other operations depend on it.

The Depth First Traversal

Similar to tree traversal, the DFS (depth first traversal) visits the child vertices before visiting the sibling vertices, the difference being that visited nodes are marked during the traversal.

The Breadth First Traversal

Similar to tree traversal, the BFs (breadth first traversal) visits the sibling vertices first before the child vertices, the difference being that visited nodes are marked during the traversal.

Real life Applications

  • Relationships between people on social media (facebook, instagram etc)

References