Skip to content

Graph structures in C++

Casey Williams edited this page Jun 15, 2017 · 2 revisions

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:

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:

graph-structure

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, representing alice's connections to bob and eve (follow the adjacent 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 from bob to alice.
  • The third entry is for eve. This is similar to the previous entry - it represents the connection from eve to bob.
  • The last entry is for trent. You'll notice that he head pointer is NULL - 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;
};
Clone this wiki locally