Graphs

Components

• vertex: each node of the graph
• edges: describe realationships between vertices

Types

• Weigthed / Not Weigthed
• Directed / Undirected

Representation

1. Adjacency Matrix

An adjacency matrix, once it has been formed can give us another piece of infromatio looking at rows and columns. Adjacency Lists which hive us the neighbours of a given node. For example if we want to know the node 4 neighbours we just look at row or column 4.

• For an undirected graph the SPACE USAGE is
• n^2 | For n vertices

2. Linked Lists storage

Properties

• For an undirected graph the SPACE USAGE is
• n + e*2*2 | For n vertices and e vertices

Maximum total number of edges with n vertices

Undirected graph

• (n*(n-1))/2

Directed graph

• (n*(n-1))