Overview

A graph can be considered to be a data structure that consists of a group of vertices and edges connecting them. The vertices or nodes in the graph can be anything as long it is an object (so people for example), and the edges are the relationships between them. The edges can be un-directional or directional, meaning that the relationship operates from one node to another. For instance, node A is the parent of node B.

In the following diagram, the circles represent the vertices or nodes (A to D), while the thick lines represent the edges or relationships between them (E1 to E6). Each node or edge may have properties, and these values are represented by the associated gray squares (P1 to P7):

So, if a graph represents a physical route map, the edges might represent minor roads or motorways. The nodes would be motorway junctions or road intersections. Node and edge properties might be road types, speed limits, distance, cost, and grid location.

There are many types of graph implementation...