Understanding graphs

Graphs are the Swiss army knife of computer science data structures. Theoretically, any other data structure can be represented as a graph, although usually, it won't perform as well.

For example, binary trees can be seen as a graph in which each node has two outgoing edges at most. These edges link it to the node's children. Or, an array can be seen as a graph in which each item in the array has edges that link it to the items adjacent to it.

However, in this case, the data that we're working with is naturally represented by a graph. The people in the network are the nodes, and their relationships are the edges.

Graphs come in several flavors, but they all have some things in common. First, they are a series of nodes that are connected by edges. Edges can be unidirectional, in which case, the relationship they represent goes only one way (for example, followers on Twitter), or it goes bidirectional, in which the relationship is two-way (for example, friends on Facebook).

Graphs generally don't have any hierarchy or structure like trees or lists do. However, the data they represent may have a structure. For example, Twitter has a number of users (vertices) who have a lot of followers (inbound edges). However, most users only have a few followers. This dichotomy creates a structure to the graph, where a lot of data flows through a few vertices.

Graphs' data structures typically support a number of operations, including adding edges, removing edges, and traversing the graph. We'll implement a graph data structure later. At that point, we'll also look at these operations. This may not be the best performing graph, especially for very large datasets, but it should help make clear what graphs are all about.