Search code examples
data-structuresgraphgraph-algorithmadjacency-matrixadjacency-list

Is there any other Data structure to represent Graph other than Adjacency List or Adjacency Matrix?

I was looking for different Data structures for representing Graph and I came accross Nvidia CUDA Toolkit and found out new way to represent graph with the help of source_indices, destination_offsets.

Fascinated by this innovative representation of graph, I searched out for other ways of representing Graphs. But not found anything new.

I was wondering if there was any other way to represent Graph other than Adjacency Matrix or Lists...

Solution

  • I was wondering if there was any other way to represent Graph other than Adjacency Matrix or Lists...

    There are alternatives to the adjacency list or the adjacency matrix, such as edge list, adjacency map or forward star to name a few. Given this graph (images taken from here):

    Example graph

    • this is the adjacency matrix representation:

    adjacency matrix representation

    • this is the adjacency list representation:

    enter image description here

    • this would be another alternative, the edge list:

    enter image description here

    • and another pretty common one is the forward star representation:

    enter image description here

    If you get into this research field you will find a good number of approaches, mainly optimizations for specific cases, taking into account factors such as:

    • Graph size (number of nodes)
    • Density of the graph
    • Directed or undirected graph
    • Static or dynamic graph
    • Graph known at compile time or constructed at runtime
    • Node IDs (labeled sequentially or not)
    • ...

    These optimizations can, for example, support reordering of the nodes in a preprocessing stage to increase reference locality. There is a lot of work for shortest path algorithms, specially when calculating the shortest path in a world map.

    One example of optimization would be a dynamic graph structure (Packed-Memory Graph (PMG)) which is suited for large-scale transportation networks.