A graph is a collection of vertices V and edges E.
If we think of vertices as locations, then edges represent paths between pairs pf locations. The set V contains all possible locations and the set E contains all the paths between locations. Here is a representation of a graph:
The circles represent the vertices and the lines the paths between them.
In this example V = {1, 2, 3, 4, 5, 6} and E = {(1,3), (1,6), (2,5), (3,4), (3,6)}.
Each vertex is a member of the set V. A vertex is sometimes called a node. Each edge is a member of the set E.
The vertices whitch are not end points for any edge are isolated vertices.
An edge is a self-loop if it is of the form (u,u). The sample graph contains no self-loops.
A simple graph doesn't contain self-loops or edges that are repeated in E.
A graph that contains one edge more than once or contains self-loops is a multigraph.
An edge (u,v) is incident to both vertex u and vertex v.
The degree of a vertex is the number of edges which are incident to it. For example, vertex 3 has degree 3, while vertex 4 has degree 1.
Two vertices are adjacent if there is a path between them. In the image above vertices 1 and 3 are adjacent, while vertices 1 and 2 are not.
Graph Representation
The vertices are numbered and therefore represented by their numbers. The edges have several ways of representation:
Edge List
Keeping the edges in a list of the paris of adjacent vertices is one way of representing a graph. While it is easy to add an edge to the list, deleting one may take a lot of time if its position in the list is unknown. Also, determining the edges incident to a given vertex can take a lot of time.
Example
| V1 | V2 | |
| e1 | 4 | 3 |
| e2 | 1 | 3 |
| e3 | 2 | 5 |
| e4 | 6 | 1 |
| e5 | 3 | 6 |
Adjacency Matrix
An addjacency matrix A is a N by N array. The element A[i,j] is 1 if there is an edge between vertices i and j and 0 otherwise. For an undirected graph, this matrix is symmetric.
This representation is less space efficient than the edge list, but checking if two vertices are adjacent is very inexpensive.
For weighted graphs, the value of the (i,j) entry is used to store the weight of the edge.
Example
The sample undirected graph would be represented by the following adjacency matrix:
| V1 | V2 | V3 | V4 | V5 | V6 | |
| V1 | 0 | 0 | 1 | 0 | 0 | 1 |
| V2 | 0 | 0 | 0 | 0 | 1 | 0 |
| V3 | 1 | 0 | 0 | 1 | 0 | 1 |
| V4 | 0 | 0 | 1 | 0 | 0 | 0 |
| V5 | 0 | 1 | 0 | 0 | 0 | 0 |
| V6 | 1 | 0 | 1 | 0 | 0 | 0 |
It is sometimes helpful to use the fact that the (i,j) entry of the adjacency matrix raised to the k-th power gives the number of paths from vertex i to vertex j consisting of exactly k edges.
Adjacency List
This list is used to keep all the edges incident to a given vertex. The graph representation can be done by using an array of length N (the number of vertices), every i-th element of the array being a list of the edges incident to vertex i.
Finding the vertices adjacent to each node is very cheap in this structure, but checking if two vertices are adjacent requires checking all the edges adjacent to one of the vertices. Adding an edge is easy, but deleting an edge is difficult, if the locations of the edge in the appropriate lists are not known.
Example
| Adjacent | |
| Vertex | Vertices |
| 1 | 3, 6 |
| 2 | 5 |
| 3 | 6, 4, 1 |
| 4 | 3 |
| 5 | 2 |
| 6 | 3, 1 |
Implicit Representation
For some graphs, the graph itself does not have to be stored at all. For example, for the Knight moves and Overfencing problems, it is easy to calculate the neighbors of a vertex, check adjacency, and determine all the edges without actually storing that information, thus, there is no reason to actually store that information; the graph is implicit in the data itself.
If it is possible to store the graph in this format, it is generally the correct thing to do, as it saves a lot on storage and reduces the complexity of your code, making it easy to both write and debug.
If N is the number of vertices, M the number of edges, and d max the maximum degree of a node, the following table summarizes the differences between the representations:
| Efficiency | Edge List | Adj Matrix | Adj List |
| Space | 2xM | N2 | 2xM |
| Adjacency Check | M | 1 | d max |
| List of Adj Vertices | M | N | d max |
| Add Edge | 1 | 1 | 1 |
| Delete Edge | M | 2 | 2xd max |
