A graph is a fundamental data structure that’s really useful for lots of different applications. It is a set of nodes with edges joining them; the edges may be directed or undirected. Examples of directed graphs are transport networks (e.g. the London tube map with stations as nodes), and the internet with pages as nodes and hyperlinks as edges. A good example of an undirected graph is a friendship network with people as nodes and friendships as edges.
Graphs are usually traversed, or searched, from a root node. In depth-first search, the children of a node are searched before its siblings. Hence, depth-first search can be done recursively. In breadth-first search, the siblings of a node are searched before its children, which can be implemented with a queue. Graphs may have cycles in, so during search it’s necessary to mark nodes that you’ve visited so that you don’t get stuck in a loop.
The three main ways of storing graphs are as a matrix, adjacency list and objects representing nodes and/or edges.
An nxn matrix can represent a graph with n nodes. A non-zero entry in the matrix at position (r,c) indicates an edge between the nodes r and c. This form of representation makes it really easy to add edges and to determine whether an edge exists, both O(1), but more difficult to insert nodes as the size of the matrix must be grown. For a sparse graph, this is an inefficient representation in memory.
A graph can be represented by a set of unordered lists, one for each node. Each list contains the nodes that the current node is connected to. Growing the graph in terms of nodes means adding a new list, and adding an edge simply requires adding it to the correct list. However, determining whether an edge exists is O(e), where e is the number of edges, as is means searching through the relevant list.
Objects and pointers
Graphs can be represented by custom edge and node data structures where pointers are used to link edges and nodes. This is a more complicated representation, but means that you can tailor your data structures to contain exactly the information you need for your particular problem. This representation fits well with object-oriented code, and can be easier to read.