teach-ict.com logo

THE education site for computer science and ICT

1. Introduction to Graphs

In the previous section, we learned about the queue and stack data structures. If you haven't already completed that section, you should read it before continuing, as we will be building on what has been explained there.

Queues and stacks arrange items in careful linear order, with items coming one after another. But this isn't the only way that data can be arranged. In this section, we will discuss the graph data structure, which excels at modelling connections and relationships between data items.

For example, here is a basic graph structure:

As you can see, this data would be very awkward to map out using simpler data structures.

Graphs use slightly different terminology to other data structures.

  • Each connected item or node in a graph is called a vertex (plural: vertices).
  • Each line connecting two vertices is called an edge. You can have a vertex connecting to itself to form a cycle or loop, as shown in 'E'.
  • Each vertex has a 'degree', which describes how many connections that vertex has. In the above graph, for example, 'B' is degree 3. 'A' is degree 1.