Programming Concepts: Graphs

From Wikibooks, open books for an open world
Jump to: navigation, search

UNIT 3 - ⇑ Programming Concepts ⇑

← Lists Graphs Trees →


Graphs - diagrams modelling relationships between objects of a certain collection, consisting of edges (lines) and vertices (dots)


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:

Road's between 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
Name all the neighbours of Tiptree:

Answer :

  • Feering
  • Maldon
  • Clacton
  • Harwich
What is the degree of Tiptree:

Answer :

4

What is the degree of Dunwich:

Answer :

2

How many edges and vertices on the following graph:
6v-color-graph.svg

Answer :

  • edges = 5
  • vertices = 6

Labelled or Weighted Graphs[edit]

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.

Weighted Road's between East Anglian Towns
Exercise: Labelled or Weighted Graphs
What is the shortest distance between Harwich and Feering?

Answer :

  1. Harwich to Tiptree = 31
  2. Tiptree to Feering = 3
  • Total = 34
What is the shortest distance between Blaxhall and Clacton?

Answer :

  1. Blaxhall to Harwich = 40
  2. Harwich to Clacton = 17
  • Total = 57
What is the shortest distance between Maldon and Dunwich?

Answer :

  1. Maldon to Feering = 11
  2. Feering to Blaxhall = 46
  3. Blaxhall to Dunwich = 15
  • Total = 72

You might also have:

  1. Maldon to Tiptree = 8
  2. Tiptree to Feering = 3
  3. Feering to Blaxhall = 46
  4. Blaxhall to Dunwich = 15
  • Total = 72

Picking best routes is a very complicated task

Directed Graphs or Digraphs[edit]

an example of a Digraph

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 one-way street and others bi-directional. How does this affect our East Anglian Transport system:

Weighted Road's between East Anglian Towns
Exercise: Labelled or Weighted Graphs
What is the shortest distance from Maldon to Dunwich?

Answer :

  1. Maldon to Tiptree = 8
  2. Tiptree to Feering = 3
  3. Feering to Blaxhall = 46
  4. Blaxhall to Dunwich = 15
  • Total = 72

There is now only one solution to this problem.

What is the shortest distance from Harwich to Clacton?

Answer :

  1. Harwich to Tiptree = 31
  2. Tiptree to Clacton = 29
  • Total = 60
What is the shortest distance from Dunwich to Maldon?

Answer :

There is no direct route in that direction

Undirected Graphs[edit]

Undirected graphs don't include arrows, there are no one way streets. Undirected graphs can be weighted and unweighted:

un-directed and un-weighted un-directed and weighted un-directed and un-weighted
CPT-Graphs-undirected-unweighted.svg CPT-Graphs-undirected-weighted.svg Undirected.svg
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]

Before we can define a simple graph we need to know what loop and multi-edge are:

  • a loop is a vertex with a connection edge to itself
  • a multi-edge is where there are two or more connections between each vertex
Simple Graph Non Simple Graph
This a simple graph as there are no loops or multiedges
This is NOT a simple graph
A loop in the above example is where someone going on a walk from Dunwich ends up back in Dunwich without visiting any other vertices.
There is a multi-edge between Harwich and Blaxhall, as you could take the ferry, or drive

Simple Graphs - an undirected graph that has no loops and no more than one edge between any two different vertices


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

simple graphs
CPT-Graphs-undirected-unweighted.svg CPT-Graphs-undirected-weighted.svg Undirected.svg
no-loops, no multi-edges, no directions
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.

Which of the following graphs are simple graphs?
A B C D
6n-graph2.svg CPT-Graphs-undirected-unweighted-ex1.svg CPT-Graphs-directed-weighted-ex2.svg CPT-Graphs-directed-weighted-ex1.svg

Answer :

A B C D
No as it has a loop (on 1) Yes No as it has a multiedge (FN) and is directed No, it is directed

How to store graphs on computers[edit]

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 hand-drawn diagrams. We are going to look at two methods: the adjacency matrix and the adjacency list.

Adjacency matrix[edit]

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:

Undirected-Unweighted Directed-Unweighted Undirected-Weighted Directed-Weighted
CPT-Graphs-undirected-unweighted.svg CPT-Graphs-directed-unweighted.svg CPT-Graphs-undirected-weighted.svg CPT-Graphs-directed-weighted.svg
B C D F H M T
B 0 0 1 1 1 0 0
C 0 0 0 0 1 1 1
D 1 0 0 0 1 0 0
F 1 0 0 0 0 1 1
H 1 1 1 0 0 0 1
M 0 1 0 1 0 0 1
T 0 1 0 1 1 1 0
B C D F H M T
B 0 0 1 0 0 0 0
C 0 0 0 0 1 1 0
D 1 0 0 0 0 0 0
F 1 0 0 0 0 1 0
H 1 0 1 0 0 0 1
M 0 0 0 0 0 0 1
T 0 1 0 1 0 0 0
B C D F H M T
B 15 46 40
C 17 40 29
D 15 53
F 46 11 3
H 40 17 53 31
M 40 11
T 29 3 31
B C D F H M T
B 15
C 17 40
D 17
F 46 11
H 40 53 31
M
T 29 3
edge exists between two vertices = 1
no edge between vertices = 0
edge exists between two vertices = use weighting
no edge between vertices = ∞ (infinity symbol)

Pros

plus pointGood for graphs with more edges than nodes

Cons

minus point Bad for graphs with less edges than nodes, as it will be very inefficient and will take up a lot of memory


Adjacency list[edit]

An adjacency list records the relationship between every vertex to all relevant vertices. It records only when there is an edge between two vertices.

Undirected-Unweighted Directed-Unweighted Undirected-Weighted Directed-Weighted
CPT-Graphs-undirected-unweighted.svg CPT-Graphs-directed-unweighted.svg CPT-Graphs-undirected-weighted.svg CPT-Graphs-directed-weighted.svg
Connected to
Blaxhall D; H; F
Clacton H; M; T
Dunwich B; H
Feering B; M; T
Harwich B; C; D; T
Maldon C; F; T
Tiptree C; F; H; M
Connected to
Blaxhall D
Clacton H; M
Dunwich B
Feering B; M
Harwich B; D; T
Maldon T
Tiptree C; F
Connected to
Blaxhall D,15; H,40; F,46
Clacton H,17; M,40; T,29
Dunwich B,15; H,53
Feering B,46; M,11; T,3
Harwich B,40; C,17; D,53; T,31
Maldon C,40; F,11; T,8
Tiptree C,29; F,3; H,31; M,8
Connected to
Blaxhall D,15
Clacton H,17; M,40
Dunwich B,17
Feering B,46; M,11
Harwich B,40; D,53; T,31
Maldon T,8
Tiptree C,29; F,3
List each connection
List each connection and the weighting

Pros

plus pointGood for graphs with fewer edges than nodes

Cons

minus point Bad for graphs with more edges than nodes, as it inefficient and takes up a lot of memory
Exercise: Adjacency Matrices and Lists
Draw an Adjacency List and an Adjacency Matrix for the following graph:
6v-color-graph.svg

Answer :

A B C D E F
A 0 1 0 0 1 1
B 1 0 1 0 0 0
C 0 1 0 0 0 0
D 0 0 0 0 0 0
E 1 0 0 0 0 1
F 1 0 0 0 1 0
Connected to
A B; E; F;
B A; C
C B
D
E A; F
F A; E
Draw an Adjacency List and an Adjacency Matrix for the following graph:
6n-graph2.svg

Answer :

1 2 3 4 5 6
1 1 1 0 0 1 0
2 1 0 1 0 1 0
3 0 1 0 1 0 0
4 0 0 1 0 1 1
5 1 1 0 1 0 0
6 0 0 0 1 0 0
Connected to
1 1; 2; 5
2 1; 3; 5
3 2; 4
4 3; 5; 6
5 1; 2; 4
6 4
Draw an Adjacency List and an Adjacency Matrix for the following graph:
4-tournament.svg

Answer :

1 2 3 4
1 0 1 0 1
2 0 0 0 1
3 1 1 0 0
4 0 0 1 0
Connected to
1 2; 4
2 4
3 1; 2
4 3
Draw an Adjacency List and an Adjacency Matrix for the following graph:
Weighted K4.svg

Answer :

A B C D
A 20 42 35
B 20 30 34
C 42 30 12
D 35 34 12
Connected to
A B,20; C,42; D,35
B A,20; C,30; D,34
C A,42; B,30; D,12
D A,35; B,34; C,12
Draw a graph for the following Adjacency List:
Connected to
A B
B A; C; D
C B; D
D B; C

Answer :

CPT-Graphs-undirected-unweighted-ex1.svg
Draw a graph for the following Adjacency List:
Connected to
A C,12; D,60
B A,10
C B,20; D,32
D B,22
E A,7

Answer :

CPT-Graphs-directed-weighted-ex1.svg
Draw a graph for the following Adjacency Matrix:
A B D F N
A 0 0 1 1 0
B 0 0 0 1 1
D 0 0 1 0 1
F 1 0 1 0 0
N 0 0 1 0 0

Answer :

CPT-Graphs-directed-unweighted-ex1.svg
Draw a graph for the following Adjacency Matrix
A B D F N
A 14
B 23 13
D 5
F 43 33
N 22 11

Answer :

CPT-Graphs-directed-weighted-ex2.svg
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.