**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.

#### 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.

##### Graph #1

##### Adjacency Matrix #1

A | B | C | D | E | |

A | ✔ | ✔ | |||

B | ✔ | ||||

C | ✔ | ||||

D | ✔ | ||||

E | ✔ |

##### Graph #2

##### Adjacency Matrix #2

A | B | C | D | E | |

A | 4 | 5 | |||

B | 4 | 7 | |||

C | 7 | 3 | 6 | ||

D | |||||

E |

##### Graph #3

##### Adjacency Matrix #3

Complete the following adjacency matrix:

A | B | C | D | E | F | |

A | ||||||

B | ||||||

C | ||||||

D | ||||||

E | ||||||

F |

##### Graph #4

##### Adjacency Matrix #4

Complete the following adjacency matrix.

A | B | C | D | E | F | |

A | ||||||

B | ||||||

C | ||||||

D | ||||||

E | ||||||

F |

##### Graph #5

##### Adjacency Matrix #5

Complete the following adjacency matrix.

A | B | C | D | E | |

A | |||||

B | |||||

C | |||||

D | |||||

E |

#### 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 |