Programming Concepts: Graphs
When there are two vertices connected by an edge, the two vertices are called neighbours. The degree of a vertex is how many other vertices it is connected to (or how many neighbours it has). Graphs are used to record relationships between things. Popular uses of graphs are mapping, social networks, chemical compounds and electrical circuits. We are going to focus on mapping where graphs will be used to model some East Anglian towns and find the shortest distance between two locations, for example in your direction finding GPS application on your phone. Below is an undirected graph (it has no arrows) showing a simplified map of East Anglian Towns:
In the graph above we have 7 vertices and 11 edges. Dunwich is neighbour with Blaxhall and Harwich. Clacton has 3 edges directly connecting it to 3 other vertices, it therefore has a degree of 3.
Exercise: Graphs

Labelled or Weighted Graphs[edit  edit source]
A Labelled Graph is almost the same as the graph above, but with something (usually numerical values) attached to the edges. This is useful in mapping applications when you want to find the shortest distance or time between vertices.
Exercise: Labelled or Weighted Graphs What is the shortest distance between Harwich and Feering?
Answer:
What is the shortest distance between Blaxhall and Clacton?
Answer:
What is the shortest distance between Maldon and Dunwich?
Answer:
You might also have:
Picking best routes is a very complicated task 
Directed Graphs or Digraphs[edit  edit source]
Directed graphs are much like normal graphs, but unsurprisingly they have directions. You should treat them a little like a road system in a town or city. Some roads will be oneway street and others bidirectional. How does this affect our East Anglian Transport system:
Exercise: Labelled or Weighted Graphs What is the shortest distance from Maldon to Dunwich?
Answer:
There is now only one solution to this problem. What is the shortest distance from Harwich to Clacton?
Answer:
What is the shortest distance from Dunwich to Maldon?
Answer: There is no direct route in that direction 
Undirected Graphs[edit  edit source]
Undirected graphs don't include arrows, there are no one way streets. Undirected graphs can be weighted and unweighted:
undirected and unweighted  undirected and weighted  undirected and unweighted 

A simple graph with three vertices and three edges. Each vertex has degree two, so this is also a regular graph. 
Undirected graphs allow you to travel both directions down each edge, it works in the same way as a directed graph with two edges between each vertices. See Blaxhall and Dunwich above.
Simple Graphs[edit  edit source]
Before we can define a simple graph we need to know what loop and multiedge are:
 a loop is a vertex with a connection edge to itself
 a multiedge is where there are two or more connections between each vertex
Simple Graph  Non Simple Graph 

In a simple graph with n vertices every vertex has a degree that is less than n.
simple graphs  

Exercise: Simple Graphs Give the definition of a simple graph
Answer: It is an undirected graph that has no loops and no more than one edge between any two different vertices. Answer:

How to store graphs on computers[edit  edit source]
So far we have seen how to draw graphs using edges and vertices. If we want to store them as digital data we have to think of a computer friendly way as computers aren't very good at reading handdrawn diagrams. We are going to look at two methods: the adjacency matrix and the adjacency list.
Adjacency matrix[edit  edit source]
An adjacency matrix records the relationship between every vertex to all other vertices. It records both when there is an edge between two vertices and when there isn't an edge:
Pros
Cons
Adjacency list[edit  edit source]
An adjacency list records the relationship between every vertex to all relevant vertices. It records only when there is an edge between two vertices.
UndirectedUnweighted  DirectedUnweighted  UndirectedWeighted  DirectedWeighted  




 
Pros
Cons
Exercise: Adjacency Matrices and Lists Answer:
Answer:
Answer:
Answer:
Draw a graph for the following Adjacency List:
Draw a graph for the following Adjacency List:
Draw a graph for the following Adjacency Matrix:
Draw a graph for the following Adjacency Matrix
When might you use an adjacency list instead of an adjacency matrix?
Answer:
An adjacency list takes up less space for graphs with smaller number of connections.
When might you use an adjacency matrix instead of an adjacency list?
Answer:
An adjacency matrix is preferable when the graph has lots of connections.
