Graph Terminology

Graphs are a data structure that can be used in computer science in a variety of context.

You can check the following Python challenges which are all being solved using a graph and a short path algorithm, one of the most useful algorithms used when manipulating graphs.

Using a graph to represent a food web.

Using a graph to store London tube map.

Using a graph to represent friendship relationships in a social network.

Using a graph to plan a flight route between airports.

Graph Terminology

A graph is a collection of nodes also called vertices which are connected between one another. Each connection between two vertices is called an edge (sometimes called a branch).

When designing a graph we can make decisions as to:

• Use a directed graph or an undirected graph,
• Use a weighted graph or an unweighted graph.

The weight of an edge can have different meanings:

• It could represent the distance (e.g. in miles) between two vertices,
• It could represent the time needed to travel (e.g. in minutes) between two vertices,
• etc…

The direction of an edge is not always needed.

For instance, in a social network like Facebook, there is no need to have directed edges to represent friendship, as if A if a friend of B, then B is also a friend of A. So all edges are both ways, hence an undirected graph is suitable to represent friendship relationships in Facebook.

Twitter however would use a directed graph, as if A follows B, it is not necessary the case that B is following A. With Twitter the edges represent the “Follow” relationship and are directed edges.

Adjacency Matrix

An adjacency matrix is sometimes used to represent a graph. It is based on a 2D-array to represent all the vertices and edges of a graph.

Extension Task:

Adjacency Matrix

Complete the following adjacency matrix:

	Amsterdam	Athens	Berlin	Bucharest	Budapest	Dublin	Geneva	Lisbon	London	Madrid	Oslo	Paris	Reykjavik	Rome
Amsterdam
Athens
Berlin
Bucharest
Budapest
Dublin
Geneva
Lisbon
London
Madrid
Oslo
Paris
Reykjavik
Rome