Graph Representation
Graphs can be represented in various ways:
- Adjacency Matrix:
- A 2D array where A[i][j]=1(or the weight of the edge) if there is an edge between vertices i and j, otherwise A[i][j]=0.
- Space Complexity: O(V2).
- Good for dense graphs.
Matrix Representation:
The adjacency matrix is a V×V table where:
- Rows and columns represent vertices.
- 1 indicates an edge from vertex i to vertex j.
- 0 indicates no edge.
2. Adjacency List:
- An array (or list) where each element contains a list of all adjacent vertices.
- Space Complexity: O(V+E).
- Good for sparse graphs.
List Representation:
3. Edge List:
- A list of all edges, where each edge is represented as a pair (u, v) (or triplet (u, v, w) for weighted graphs) of vertices.
- Space Complexity: O(E).
List Representation:
