Representation
Adjacency Matrix
- |V| = no of vertex
- size of matrix = |V| x |V|
- M [ i ][ j ] = 1 if (edge from i to j) else 0
- For undirected graph: matrix is symmetric
- When vertex values are not numbers = map matrix index with array and dictionary
| Vertex | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 | 0 |
| 2 | 1 | 1 | 0 | 1 |
| 3 | 0 | 0 | 1 | 0 |
Properties
- Space:
O(V ^ 2) - Operations:
- Check if u and v are adj:
O(1) - All vertex adj to u:
O(V) - degree of u:
O(V) - Add/remove edge
O(1) - Add/remove vertex
O(V ^ 2)
- Check if u and v are adj:
Adjacency List
- Represented as:
- Dynamic size array
- Linked list
Properties
- Space:
O(V + E)Directed GraphO(V + 2E)Undirected Graph
- Operations:
- Check if u and v are adj:
O(V) - All vertex adj to u:
O(degree(u)) - degree of u:
O(1) - Add edge
O(1) - Remove edge
O(V) - Add/remove vertex
O(V ^ 2)
- Check if u and v are adj:
- Python
adj = [[] for _ in range(V)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
note
use defaultdict
adj = defaultdict(list)
for u, v in edges:
adj[u].append(v)
adj[v].append(u)