El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
HOME Els meus cursos Finalitzats
◄ Anterior
◄

Representació de Grafs

Següent ►
►

En aquest tema, explorarem les diferents maneres de representar grafs en la programació i l'anàlisi d'algoritmes. Els grafs són estructures de dades fonamentals en la informàtica, utilitzades per modelar relacions entre objectes. La representació eficient d'un graf és crucial per a l'execució eficient dels algoritmes que operen sobre ell.

Conceptes Bàsics

Abans de començar amb les representacions, és important entendre alguns conceptes bàsics sobre grafs:

  • Graf: Un graf \( G \) es defineix com un conjunt de nodes (o vèrtexs) \( V \) i un conjunt d'arestes \( E \) que connecten parelles de nodes.
  • Graf dirigit: Les arestes tenen una direcció, és a dir, van d'un node a un altre.
  • Graf no dirigit: Les arestes no tenen direcció, és a dir, la connexió entre nodes és bidireccional.
  • Pes: Algunes arestes poden tenir un valor associat, anomenat pes, que pot representar distància, cost, etc.

Representacions de Grafs

Hi ha diverses maneres de representar un graf en la memòria d'un ordinador. Les més comunes són:

  1. Matriu d'Adjacència
  2. Llista d'Adjacència
  3. Llista d'Arestes

Matriu d'Adjacència

Una matriu d'adjacència és una matriu \( n \times n \) on \( n \) és el nombre de nodes en el graf. Cada element \( A[i][j] \) indica si hi ha una aresta entre el node \( i \) i el node \( j \).

Avantatges:

  • Accés ràpid per verificar si hi ha una aresta entre dos nodes.
  • Fàcil d'implementar.

Desavantatges:

  • Requereix \( O(n^2) \) espai, fins i tot si el graf és escàs (amb poques arestes).

Exemple:

# Matriu d'adjacència per un graf no dirigit amb 4 nodes
# Nodes: 0, 1, 2, 3
# Arestes: (0-1), (0-2), (1-2), (2-3)

adj_matrix = [
    [0, 1, 1, 0],
    [1, 0, 1, 0],
    [1, 1, 0, 1],
    [0, 0, 1, 0]
]

# Verificar si hi ha una aresta entre el node 0 i el node 1
print(adj_matrix[0][1])  # Sortida: 1 (hi ha una aresta)

Llista d'Adjacència

Una llista d'adjacència és una col·lecció de llistes. Cada node té una llista que conté els nodes adjacents a ell.

Avantatges:

  • Requereix menys espai per a grafs escassos.
  • Fàcil de trobar tots els nodes adjacents a un node donat.

Desavantatges:

  • Pot ser més lent verificar si hi ha una aresta entre dos nodes específics.

Exemple:

# Llista d'adjacència per un graf no dirigit amb 4 nodes
# Nodes: 0, 1, 2, 3
# Arestes: (0-1), (0-2), (1-2), (2-3)

adj_list = {
    0: [1, 2],
    1: [0, 2],
    2: [0, 1, 3],
    3: [2]
}

# Verificar els nodes adjacents al node 2
print(adj_list[2])  # Sortida: [0, 1, 3]

Llista d'Arestes

Una llista d'arestes és simplement una llista de totes les arestes del graf. Cada aresta es representa com una parella de nodes (i possiblement un pes).

Avantatges:

  • Molt compacta per a grafs escassos.
  • Fàcil d'iterar sobre totes les arestes.

Desavantatges:

  • No és eficient per verificar si hi ha una aresta entre dos nodes específics.

Exemple:

# Llista d'arestes per un graf no dirigit amb 4 nodes
# Nodes: 0, 1, 2, 3
# Arestes: (0-1), (0-2), (1-2), (2-3)

edge_list = [
    (0, 1),
    (0, 2),
    (1, 2),
    (2, 3)
]

# Iterar sobre totes les arestes
for edge in edge_list:
    print(edge)
# Sortida:
# (0, 1)
# (0, 2)
# (1, 2)
# (2, 3)

Exercicis Pràctics

Exercici 1: Crear una Matriu d'Adjacència

Crea una funció que prengui una llista d'arestes i el nombre de nodes, i retorni la matriu d'adjacència corresponent.

def crear_matriu_adjacencia(arestes, num_nodes):
    matriu = [[0] * num_nodes for _ in range(num_nodes)]
    for (u, v) in arestes:
        matriu[u][v] = 1
        matriu[v][u] = 1  # Si és un graf no dirigit
    return matriu

# Prova
arestes = [(0, 1), (0, 2), (1, 2), (2, 3)]
num_nodes = 4
print(crear_matriu_adjacencia(arestes, num_nodes))

Exercici 2: Crear una Llista d'Adjacència

Crea una funció que prengui una llista d'arestes i el nombre de nodes, i retorni la llista d'adjacència corresponent.

def crear_llista_adjacencia(arestes, num_nodes):
    llista = {i: [] for i in range(num_nodes)}
    for (u, v) in arestes:
        llista[u].append(v)
        llista[v].append(u)  # Si és un graf no dirigit
    return llista

# Prova
arestes = [(0, 1), (0, 2), (1, 2), (2, 3)]
num_nodes = 4
print(crear_llista_adjacencia(arestes, num_nodes))

Exercici 3: Convertir una Matriu d'Adjacència a una Llista d'Adjacència

Crea una funció que prengui una matriu d'adjacència i retorni la llista d'adjacència corresponent.

def matriu_a_llista_adjacencia(matriu):
    num_nodes = len(matriu)
    llista = {i: [] for i in range(num_nodes)}
    for i in range(num_nodes):
        for j in range(num_nodes):
            if matriu[i][j] == 1:
                llista[i].append(j)
    return llista

# Prova
matriu = [
    [0, 1, 1, 0],
    [1, 0, 1, 0],
    [1, 1, 0, 1],
    [0, 0, 1, 0]
]
print(matriu_a_llista_adjacencia(matriu))

Conclusió

En aquesta secció, hem après sobre les diferents maneres de representar grafs: matriu d'adjacència, llista d'adjacència i llista d'arestes. Cada representació té els seus avantatges i desavantatges, i la selecció de la representació adequada depèn del tipus de graf i de les operacions que es necessiten realitzar. Els exercicis pràctics proporcionats ajudaran a consolidar aquests conceptes i a aplicar-los en situacions reals.

◄ Anterior
◄
Següent ►
►
El Projecte | Sobre nosaltres | Contribuir | Donacions | Llicència
© Copyright 2024. Tots els drets reservats