En aquest tema, explorarem les diferents maneres de representar grafs en la programació. Els grafs són estructures de dades que consisteixen en nodes (o vèrtexs) i arestes que connecten aquests nodes. La representació adequada d'un graf és crucial per a l'eficiència dels algoritmes que operen sobre ell.
Tipus de Representació de Grafs
Hi ha diverses maneres de representar un graf, cadascuna amb els seus avantatges i inconvenients. Les representacions més comunes són:
- Matriu d'Adjacència
- Llista d'Adjacència
- Matriu d'Incidència
Matriu d'Adjacència
Una matriu d'adjacència és una matriu 2D de mida n x n on n és el nombre de nodes en el graf. Cada element A[i][j] de la matriu indica si hi ha una aresta entre el node i i el node j.
Avantatges:
- Accés ràpid per verificar si existeix una aresta entre dos nodes.
- Senzillesa en la implementació.
Inconvenients:
- Requereix
O(n^2)espai, la qual cosa pot ser ineficient per a grafs esparsos.
Exemple:
Considerem un graf amb 4 nodes (0, 1, 2, 3) i les següents arestes: (0-1), (0-2), (1-2), (2-3).
La matriu d'adjacència seria:
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 | 0 |
| 2 | 1 | 1 | 0 | 1 |
| 3 | 0 | 0 | 1 | 0 |
Llista d'Adjacència
Una llista d'adjacència és una col·lecció de llistes. La llista a la posició i conté tots els nodes adjacents al node i.
Avantatges:
- Requereix menys espai per a grafs esparsos.
- Més eficient per iterar sobre els nodes adjacents.
Inconvenients:
- Accés més lent per verificar si existeix una aresta entre dos nodes comparat amb la matriu d'adjacència.
Exemple:
Considerem el mateix graf amb 4 nodes (0, 1, 2, 3) i les següents arestes: (0-1), (0-2), (1-2), (2-3).
La llista d'adjacència seria:
Matriu d'Incidència
Una matriu d'incidència és una matriu 2D de mida n x m on n és el nombre de nodes i m és el nombre d'arestes. Cada element B[i][j] indica si el node i està connectat per l'aresta j.
Avantatges:
- Pot ser útil per a certs tipus d'algoritmes que necessiten informació sobre les arestes.
Inconvenients:
- Requereix més espai que la llista d'adjacència per a grafs esparsos.
- Més complexa de gestionar.
Exemple:
Considerem el mateix graf amb 4 nodes (0, 1, 2, 3) i les següents arestes: (0-1), (0-2), (1-2), (2-3).
La matriu d'incidència seria:
| e1 | e2 | e3 | e4 | |
|---|---|---|---|---|
| 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 0 |
| 2 | 0 | 1 | 1 | 1 |
| 3 | 0 | 0 | 0 | 1 |
Implementació en Python
Matriu d'Adjacència
class GrafMatriuAdjacencia:
def __init__(self, nombre_nodes):
self.nombre_nodes = nombre_nodes
self.matriu = [[0] * nombre_nodes for _ in range(nombre_nodes)]
def afegir_aresta(self, u, v):
self.matriu[u][v] = 1
self.matriu[v][u] = 1 # Per a grafs no dirigits
def mostrar_matriu(self):
for fila in self.matriu:
print(fila)
# Exemple d'ús
graf = GrafMatriuAdjacencia(4)
graf.afegir_aresta(0, 1)
graf.afegir_aresta(0, 2)
graf.afegir_aresta(1, 2)
graf.afegir_aresta(2, 3)
graf.mostrar_matriu()Llista d'Adjacència
class GrafLlistaAdjacencia:
def __init__(self, nombre_nodes):
self.nombre_nodes = nombre_nodes
self.llista = [[] for _ in range(nombre_nodes)]
def afegir_aresta(self, u, v):
self.llista[u].append(v)
self.llista[v].append(u) # Per a grafs no dirigits
def mostrar_llista(self):
for i in range(self.nombre_nodes):
print(f"{i}: {self.llista[i]}")
# Exemple d'ús
graf = GrafLlistaAdjacencia(4)
graf.afegir_aresta(0, 1)
graf.afegir_aresta(0, 2)
graf.afegir_aresta(1, 2)
graf.afegir_aresta(2, 3)
graf.mostrar_llista()Matriu d'Incidència
class GrafMatriuIncidencia:
def __init__(self, nombre_nodes, nombre_arestes):
self.nombre_nodes = nombre_nodes
self.nombre_arestes = nombre_arestes
self.matriu = [[0] * nombre_arestes for _ in range(nombre_nodes)]
self.aresta_index = 0
def afegir_aresta(self, u, v):
if self.aresta_index < self.nombre_arestes:
self.matriu[u][self.aresta_index] = 1
self.matriu[v][self.aresta_index] = 1
self.aresta_index += 1
def mostrar_matriu(self):
for fila in self.matriu:
print(fila)
# Exemple d'ús
graf = GrafMatriuIncidencia(4, 4)
graf.afegir_aresta(0, 1)
graf.afegir_aresta(0, 2)
graf.afegir_aresta(1, 2)
graf.afegir_aresta(2, 3)
graf.mostrar_matriu()Exercicis Pràctics
- Implementació de Grafs Dirigits: Modifica les classes anteriors per suportar grafs dirigits.
- Conversió entre Representacions: Escriu funcions per convertir un graf representat com a matriu d'adjacència a una llista d'adjacència i viceversa.
- Càlcul del Grau dels Nodes: Implementa una funció que calculi el grau de cada node en un graf representat com a llista d'adjacència.
Resum
En aquesta secció, hem explorat les diferents maneres de representar grafs: matriu d'adjacència, llista d'adjacència i matriu d'incidència. Cada representació té els seus propis avantatges i inconvenients, i la selecció de la representació adequada depèn de les necessitats específiques de l'aplicació i dels algoritmes que s'utilitzaran. Hem proporcionat exemples de codi per a cada tipus de representació i suggerit exercicis pràctics per reforçar els conceptes apresos.
Curs d'Estructures de Dades
Mòdul 1: Introducció a les Estructures de Dades
- Què són les Estructures de Dades?
- Importància de les Estructures de Dades en la Programació
- Tipus d'Estructures de Dades
Mòdul 2: Llistes
- Introducció a les Llistes
- Llistes Enllaçades
- Llistes Doblement Enllaçades
- Llistes Circulars
- Exercicis amb Llistes
Mòdul 3: Piles
- Introducció a les Piles
- Operacions Bàsiques amb Piles
- Implementació de Piles
- Aplicacions de les Piles
- Exercicis amb Piles
Mòdul 4: Cues
- Introducció a les Cues
- Operacions Bàsiques amb Cues
- Cues Circulars
- Cues de Prioritat
- Exercicis amb Cues
Mòdul 5: Arbres
- Introducció als Arbres
- Arbres Binàries
- Arbres Binàries de Cerca
- Arbres AVL
- Arbres B
- Exercicis amb Arbres
Mòdul 6: Grafs
- Introducció als Grafs
- Representació de Grafs
- Algoritmes de Cerca en Grafs
- Algoritmes de Camins Mínims
- Aplicacions dels Grafs
- Exercicis amb Grafs