Fundamentals of data structures- Graph

Table of Contents

1 Abstract data type - Graph

Graphs Basics

  • Graphs are data strcutures that consist of a finite number of vertices/nodes/points and edges/arcs/lines connecting those vertices/nodes/points.
  • Graphs can be undirected, directed and weighted.
  • The edges/arcs/lines between nodes can be used to represent complex relationships.
    • Arrows on edges/arcs/lines can be used for directional relationships.
      • If edges on a graph are all one-way, the graph is a directed graph or digraph.
    • Attributes/values can be associated with edges/arcs/lines to specify the nature of relationships. Those edges with values are weighted edges.

An example of undirected graph:

undirected.svg An example of directed graph/digraph:


An example of directed graph with weighted edges: directedWeighted.svg

Applications of Graphs

  • finite state machine
  • roads between towns and cities with distances as weights
  • computer networks: computers and devices as nodes and bandwidth as weights.
  • Website: the vertices represent web pages and directed edges represent links from one page to another.
  • In chemistry a graph makes a natural model for a molecule, where vertices represent atoms and edges bonds.
  • In biology and conservation efforts where a vertex can represent regions where certain species exist (or inhabit) and the edges represent migration paths, or movement between the regions.

Operations on a Graph

  • Adding a node
  • Deleting a node
  • Adding an edge
  • Deleting an edge
  • Checking if there is an edge between node A and B
  • Finding the successors of a given vertex
  • Finding a path between two vertices

Implementing Graphs - adjacent matrix and adjacent list

  • Adjacency matrix:
    • Using a two-dimensional array, a weighted or unweighted graph can be implemented. adjacency-matrix-of-graph.jpg


    • Advantages of adjacency matrix:
      • easy to add or remove an edge
      • easy to check if an edge existing
    • Disadvantages of adjacency matrix:
      • The larger the graph (more nodes), the more memory is needed.
      • For a sparse graph, space will be wasted for not storing many edges.
      • If static array is used for the matrix, adding or deleting nodes may not be easy.
  • Adjacency list:
    • For a sparsely connected graph, adjacency list implementation is more space efficient. In this implementation:
      • All nodes are stored in a list
      • Each node in the list then points to a list of adjacent nodes it connects directly.
      • the adjacent node lists can contain a list of key value pairs of node and the weight.


  • Advantages of adjacency list:
    • Easy to find successors of a node
    • Easy to find all neighbouring nodes
    • Space efficient as it only stores connected nodes
  • Disadvantage of adjacency list:
    • It is time consuming to check if an edge is part of a graph