Graphs

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.

Adjacency matrix

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.

Adjacency list

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.

Advertisements
This entry was posted in Technology and tagged , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s