Graph consists of set of vertices, \(V\) and set of edges, \(E\) as in \(G = (V,E)\). Each edge consists of a pair of vertices, such in \((v, w)\) where both \(v\) and \(w\) are in the set of \(V\), thus \(v,w \in V\).
There are two kinds of graph:
Terminology
A path is a sequence of vertices where \((w_i, w_{i+1}) \in E\). Its length could be determined by the number of vertices that it contains. A 0-length path indicates that there is no vertex in the path.
A simple path is a path that all vertices are distinct except for the first and the last vertex.
A cycle is a path where the first and the last vertex are the same required that the path must be at least of length 1. If the path is simple, then the cycle is simple.
A Graph is complete if there is an edge between every vertex.
Representation
A graph could be represented in two ways: adjacency matrix representation and adjacency 202110191710 representation.
Adjacency matrix representation basically is a 2D array. If there is an edge between \(u\) and \(v\), set \(A[u][v]\) as 1 or the corresponding weight if the edge could be measured in weight. Set it to 0 or any value that indicate that the edge is non-existent. This will result in \(\Theta(\vert V \vert^2)\) space complexity.
Adjacency list representation keeps a list of adjacent vertices (put it null if there is none) for each vertex. This will result in \(O(\vert E \vert + \vert V \vert)\) space complexity.
Name Lookup
Sometimes vertices could have their own names which is not ideal to be used for indexing. We could use 202112122035 to assign those names to an associated number.
For output convenience, we could either store those names in an array of string according to their indexing number or use an array of pointers that point to the cell of hash table. The first method could cost more spaces, the second method makes the hash table’s cells too accessible since it bypasses the basic hash table operations.