Graph (Computer Science)

Graphs are abstract data structures that create relations between elements (which are called nodes or vertices) via links (called edges). This forms an interconnected network and helps look at relationships between objects. They borrow definitions from a mathematical definition of a graph.

Generally, we are interested in a simple graph.

Properties §

• Stores nodes and edges
• Nodes are a set, i.e. no duplicate nodes
• Edges are a tuple of nodes. Edges are also a set (unique edges)
• Can check if nodes are connected i.e. edge exists, and we can ‘traverse’ through nodes via edges
• Most useful operations are path-finding, can we get from node $A$ to $B$ ?

ADT Signature §

name: Node
import data
ops:
	getData: Node -> data
	setData: Node x data -> Node

name: Edge
import Node
ops:
	newEdge: Node x Node -> Edge
	getFromNode: Edge -> Node
	getToNode: Edge -> Node

name: Graph; 
import Node, Edge, integer, boolean;  
ops:
	newGraph:→ Graph;
	addNode: Graph × Node → Graph;
	deleteNode: Graph × Node → Graph;
	nodeExists: Graph × Node → boolean;
	addEdge: Graph × Edge → Graph;
	deleteEdge: Graph × Edge → Graph;
	isAdjacent: Graph × Node x Node → boolean;
	neighbours: Graph × Node → Nodes;

Representations §

Graphs are usually represented either with either a:

• Adjacency List: Each node has an edge list which represents it’s neighbours. All these edge lists are then stored in a list. The usual implementation is an array of linked lists
• Adjacency Matrix: A matrix is constructed using a 2D array. If an edge $(u,v)$ exists, the entry $M_{u,v}$ is 1, else it is 0.

In most cases, an adjacency list is better, because it usually takes lesser space ($O(|E|+|V|)$ over $O(|V{|}^2)$) and is faster when graphs have more nodes than edges (are sparse), which is usually the case.

Time Complexity Analysis §

Adjacency List §

Basic Operation: Travelling to the next node

Operation	Worst Case (WC)	Best Case (BC)	Average Case (AC)	Case descriptions
Access an element at index $i$	$\Theta (1)$	$\Theta (1)$	$\Theta (1)$	Basic operation
Insert an element $x$ at index $i$, assuming there is space	$\Theta (1)$	$\Theta (1)$		WC ($i<n$): Increase $n$ by 1, and set $A[n]=A[i]$. Then insert the element by setting $A[i]=x$ BC ($i\ge n$): Inserting at index $n$ or higher involves no shifting
Delete an element at index $i$ (via overwriting )	$\Theta (1)$	$\Theta (1)$		WC ($i<n$): Swap the last element $A[n-1]$ with $A[i]$, then decrement $n$ by 1 BC ($i=n-1$): Decrement $n$ by 1.
Searching for an element $x$ (assuming comparison is $O(1)$)	$\Theta (n)$	$\Theta (1)$	$\Theta (n)$	WC ($A[n-1]=x$ or $x$ not in array): Have to Linear search through array BC ($A[0]==x$): One comparison at the first element AC ($A[0\dots n-1]=x$): See average case derivation

Adjacency Matrix §

Basic Operation: Array Access

Operation	Worst Case (WC)	Best Case (BC)	Average Case (AC)	Case descriptions
Access an element at index $i$	$\Theta (1)$	$\Theta (1)$	$\Theta (1)$	Basic operation
Insert an element $x$	$O(n)$	$\Theta (1)$		WC ($x$ is not the largest element) : Various methods exist: 1. Modified binary search that returns the index of greatest element lesser than $x$, then shift all elements to right by 1, then insert. 2. Add to the end, then use insertion sort, which runs well when there are few unsorted elements. BC ($x$ is the largest element) : Insert at $A[n]$, increment $n$ after
Delete an element at index $i$	$O(n)$	$\Theta (1)$		WC ($i=0$): Need to shift $n-1$ elements to the right by one using element swaps. BC ($i=n-1$): Decrement $n$ by 1
Searching for an element $x$ (assuming comparison is $O(1)$)	$\Theta (\log (n))$	$\Theta (1)$		See Binary Search Algorithm