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 en edge is not always needed.

For instance, in a social network like Facebook, there is no need to have directed edges to represent friendhsip, 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
London
Lisbon
Madrid
Oslo
Paris
Reykjavik
Rome
Share Button
Tagged with: