Graph Data Structure

Abstract

---

Cite

A graph $G=(V,E)$ is a Set of vertices $V$ and edges $E$ where each edge $(u,v)$ is a connection between vertices. $u,v\in V$.

• In layman term, graph is a Data Structure that offers a network structure that helps define and visualize relationships(known as edge) between various components(known as vertex/node)

Graph Theory

• The study of the properties of these Graph, and how they can be used to model and solve problems

Graph Basics

---

Neighbours

• Two nodes $u$, $v$ are neighbours if there is an edge $(u,v)$ connecting both nodes
• In the diagram above, node $0$ has $3$ neighbours which are $6$, $8$ and $4$

Degree

• The degree of a node $u$ is the total number of edges connected to it
• In the diagram above, node $0$ has a degree of $3$, since there are $3$ edges connected to it

Path

• A sequence of edges that connects a sequence of nodes
• In the diagram above, there are 2 paths, the path at the right side is a special path know as Cycle

Cycle

• Path that starts and ends at the same node
• In the diagram above, we start the path from node $0$ and ends at node $0$

Graph Connectivity

---

• Two vertices are connected if a Path exists between them
• A Graph is connected when there is a path between every pair of vertices, ensuring all vertices are reachable from every other vertex

Connected Component

• A connected component is a subset of vertices $V_i\subseteq V$ that form a connected graph

Directed Graph

---

• Edges are directed, and NOT Ordered Pair which means $(u,v)$ and $(v,u)$ are two different pairs
• Can be used to represent Relation which only involves one Set

Directed Cyclic Graph

• Directed Graph that has Cycle

Directed Acyclic Graph

• Known as DAG
• Directed Graph that doesn’t have Cycle

Important

A directed graph is a DAG if and only if it can be topologically ordered.

Topological Sort

• A linear ordering of vertices in a Directed Acyclic Graph. The direction of all edges are same

Important

This ordering is useful in various applications, such as task scheduling and dependency resolution etc.

Undirected Graph

• If edge $(u,v)$ exists, then edge $(v,u)$ must also exist
• Since all edges are double arrowed, we usually don’t draw out the arrows as shown above

Weighted Graph (加权图)

---

• Each Edge has a value which can be used to model things like distances between two cities

Graph Representation

---

Adjacency Matrix

• A matrix made of Array, the row index $i$ and column index $j$ indicate the id of a vertex
• $A_{ij}$ refers to a value at a particular cell of the matrix, the value is determined by $A_{ij}=\{\begin{array}{ll}1& edge(i,j)\\ 0& otherwise\end{array}$, $1$ if an edge exists from node $i$ to node $j$, otherwise $0$
• For Weighted Graph (加权图), the the value in the matrix cell can be used to represent the weight

Efficient relationship checker

Check if an edge exists between 2 nodes in $O(1)$.

Caution

The cost of space is $O(V^2)$, a big space wastage when there isn’t many edges among the nodes - Sparse Graph.

Adjacency List

• Each vertex is mapped to a list of its Neighbours

Most common representation

It gives us an easy access to the Neighbours of a node, a great tool that is very useful in graph algorithms.

Space efficient

The space complexity of adjacency list is $O(V+E)$, while it i$O(V^2)$ for Adjacency Matrix. So adjacency list is space friendly when there isn’t many edges among the nodes - Sparse Graph.

Caution

It isn’t as efficient as Adjacency Matrix when it comes to check if an edge exist between 2 nodes. We need to go through the neighbours of a node to check. We can use data structures like AVL Tree and Hash Map to hold the neighbours if a node has too many neighbours. This reduces the time complexity from $O(n)$ down to $log(n)$.

Edge Set

• A collection of all Edge

Important

For undirected graph, the edge definitions inside the adjacency set ARE NOT Ordered Pair, that means if we have 2 edges $(0,1)$ and $(1,0)$, both are considered as one single edge definition in edge set!

Caution

Not a common graph representation, it is hard to extract information about vertices and Graph.

Complete Graph

---

• A Graph that has an edge between every pair of vertices

How many edges does complete graph have?

Without considering the direction of edge and given $n$ nodes, we will have $\frac{n^2-n}{2}$ edges. $n^2$ represents the total possible edges we can have, $n^2-n$ removes all the edges that start and end from the same node. Lastly, $\frac{n^2-n}{2}$ to remove the duplicated edges since we are not considering the direction of edge, so edges that connect the same nodes are considered the same.

Another way to think about it is that given any node, we need to make $n-1$ edges to connect with another $n-1$ node. So the total edges we need is $n(n-1)$ since we have a total of $n$ nodes. However, this counts every edge twice, because every edge going out from one node is an edge going into another node, so we need to divide by $2$. Thus, we have $\frac{n(n-1)}{2}$ which is same as $\frac{n^2-n}{2}$.

Another way to think about is how many unique ways are there to pick 2 nodes from $n$ nodes, so $(u,v)$ and $(v,u)$ are considered as the same selection. This is basically Combination where we can apply Binomial Coefficient. Substituting the values into the formula, we will have $\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\frac{n!}{2!(n-2)!}$ which is $\frac{n(n-1)}{2}$.

Terminologies

---

Sparse Graph

• A Graph in which the number of edges is much less than the possible number of edges. One good example is Minimum Spanning Tree

References

---

• Introduction to Graph Theory: A Computer Science Perspective - YouTube
• Directed acyclic graph - Wikipedia
• combinatorics - Why a complete graph has $fracn(n-1)2$ edges? - Mathematics Stack Exchange