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 represent a food web.

Using a graph to store London tube map.

Using a graph to store London tube map.

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

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

Using a graph to plan a flight route between airports.

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.
An undirected graph is when edges have no direction.

An undirected graph is when edges have no direction.

A directed graph is when vertices have a direction.

A directed graph is when edges have a direction.

A weighted graph is when edges have a numerical value.

A weighted graph is when edges have a numerical value.

A weighted and directed graph is where edges have a direction and a numerical value!

A weighted and directed graph is where edges have a direction and a numerical value!

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.

Graph #1Graph #2Graph #3Graph #4Graph #5Graph #6
Graph #1

graph_4_2
Adjacency Matrix #1

A B C D E
A
B
C
D
E
Graph #2

graph_1_3
Adjacency Matrix #2

A B C D E
A 4 5
B 4 7
C 7 3 6
D
E
Graph #3

graph_3_2
Adjacency Matrix #3

Complete the following adjacency matrix:

A B C D E F
A
B
C
D
E
F
Graph #4

graph_3_3
Adjacency Matrix #4

Complete the following adjacency matrix.

A B C D E F
A
B
C
D
E
F
Graph #5

graph_4_1
Adjacency Matrix #5

Complete the following adjacency matrix.

A B C D E
A
B
C
D
E
Graph #6

graph_2_3
Adjacency Matrix #6

Complete the following adjacency matrix.

A B C D E
A
B
C
D
E

Extension Task:


European-Airports-Graph

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
Tagged with: