We have already discussed what are graphs

Represent G by a nXn, n being number of vertices 0-1 matrix A,

where Aij = 1 for every edge between 2 nodes.

Aij = b*1 where b is number of parallel edges between i and j.

Aij = w for every edge between 2 nodes with weight w

Aij = +1 if edge goes from node i to j, similarly for edge from j to i, it is -1.

Space required by adjacency matrix is θ (n

Adjacency lists

Adjacency lists contains:

**here**. Now graph can be represented in 2ways:- Adjacency matrix
- Adjacency list

**Undirected graph**Represent G by a nXn, n being number of vertices 0-1 matrix A,

where Aij = 1 for every edge between 2 nodes.

**Undirected graph with parallel edges**Aij = b*1 where b is number of parallel edges between i and j.

**Weighted Undirected graph**Aij = w for every edge between 2 nodes with weight w

**Directed graph**Aij = +1 if edge goes from node i to j, similarly for edge from j to i, it is -1.

**Space Complexity**Space required by adjacency matrix is θ (n

^{2}), no matter how many edges the graph has. In case of sparse graph it is super-wasteful implementation.Adjacency lists

Adjacency lists contains:

- array or list of vertices
- array or list of edges
- each edge points to its end points - i.e. each edge will have 2 end points
- each vertex points to edges incident on it.

**Space Complexity**

Space required by adjacency list is θ (m+n) OR θ(|V|=|E|).

Which method to use?

It depends on 2 items:

An adjacency matrix uses O(n*n) memory. It has fast lookups to check for presence or absence of a specific edge, but slow to iterate over all edges.

Which method to use?

It depends on 2 items:

- Density of the graph
- Operations needed

*Usage of adjacency list :*

For sparse matrix, there is lots of space wastage if we use Adjacency matrix, hence we use adjacency list method. In case of Operations we deal with, for graph search operations, adjacency lists suits more as it fast to iterate over adjacency list, but slow when finding the presence or absence of any edge.

*Usage of adjacency matrix:*

## 0 comments:

## Post a Comment