-
Notifications
You must be signed in to change notification settings - Fork 0
Graph structures in C++
In CS 163 and 202, you will typically be implementing a graph data structure at some point.
Like a list, a graph is a collection of items, each with their own data. But unlike in a list, the items may be connected to zero, one, or many other items (like a network or web).
Here's an example of a basic graph:
The red circles are the items in the graph, known as vertices. Each vertex has some data - in this case, just a name.
The vertices are interconnected by blue edges. You'll notice that these edges have arrows on the ends. This means we're looking at a directed graph - that is, a graph where the connections may go one way or both ways. For example, the edge between alice
and bob
goes both ways, so starting from alice
or bob
, we can always traverse to the other vertex across the connection. But The edge between alice
and eve
goes only one way - if we started at the alice
vertex, we'd be able to traverse to eve
, but we cannot traverse directly from eve
to alice
.
So how do we implement this structure in code?
In 163 and 202, this is typically done with adjacency lists (like a our hash tables). Here's the general idea:
- We represent the graph with an array of vertices. Each vertex contains:
- Whatever unique data needs to be stored for this item (like the names above), and
- A pointer to the head of a linear linked list of edges.
- A vertex's edge list contains nodes that represent connections to other vertices. Each node contains:
- A next pointer (just like a normal linked list) and
- A pointer to the adjacent vertex. The edge that the node represents is the one that runs from the vertex that holds the linked list to the adjacent vertex.
Here's is a diagram showing how you could represent the graph we saw above in this way:
As before, vertices are red, and edges are blue. The array of vertices is at the left - you'll notice that each item in the graph has an entry here.
- Take a look at the first entry, for
alice
: there are two nodes in this list, representingalice
's connections tobob
andeve
(follow theadjacent
pointers to find the connected vertices). The order of the nodes in the list doesn't matter. - The second entry is for
bob
. There is only one node in this edge list - the one representing the connection frombob
toalice
. - The third entry is for
eve
. This is similar to the previous entry - it represents the connection fromeve
tobob
. - The last entry is for
trent
. You'll notice that he head pointer isNULL
- this vertex doesn't have any connections yet.
Here's what our header file might contain:
struct vertex {
char* name;
struct edge_node* head;
};
struct edge_node {
vertex* adjacent;
edge_node* next;
};
class graph {
public:
// ...
protected:
// Holds the array of vertices:
vertex* adjacency_list;
};