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.

An undirected graph is when edges have no direction.

A directed graph is when edges have a direction.

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!

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.

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

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

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

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

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

 A B C D E A B C D E