Graph data structures
How should we feed graph data into computer programs so that we can apply graph-based algorithms to solve problems? This will be addressed in this section. Each representation has its advantages and disadvantages, and we’ll explore them from the perspective of the time complexity of determining whether an edge exists and updating the graph.
Adjacency matrix
The adjacency matrix aims to record the graph structure via a matrix. A matrix, say 
, of size 
is created (where 
denotes the number of nodes, or mathematically, 
). We start with all entries of 
being 0. Next, if 
, 
, then element 
of is labeled 1. If the graph is undirected, then if 
, 
, then both elements of , 
, and 
, are labeled 1.
The time complexity to check whether an edge exists in an adjacency matrix is 
since it just involves checking a particular cell in the matrix. However, adding a new vertex to the graph would be difficult, and depending on the matrix implementation, it might need...
