Pregunta 1 · Matemática Discreta UAB 2026
Tema: Recorreguts BFS i DFS · Del examen Examen de seminaris Parcial 1 (20/04/2026) (2026)
Enunciado
Pregunta 1 (5 punts). Algorisme BFS i detecció de cicles
Considereu la implementació en Python d'un recorregut en amplada (BFS):
1. def bfs(graph, start):
2. to_visit = []
3. visited = []
4. to_visit.append(start)
5. while to_visit:
6. # CUA (FIFO): traiem el primer
7. actual = to_visit.pop(0)
8. veins = graph.neighbors(actual)
9. for v in veins:
10. if v not in to_visit:
11. to_visit.append(v)
12. visited.append(actual)
13. return visited
I el graf dirigit definit per les següents arestes dirigides:
a.
(2 punts) Efectueu el seguiment de l'execució de la crida bfs(G, 'A') completant la taula amb l'estat de les variables al final de cadascuna de les primeres 5 iteracions del bucle while. La fila INICIAL reflecteix l'estat just abans d'entrar al bucle.
Iteració
actual
visited
to_visit
INICIAL
—
[]
['A']
1
2
3
4
5
b.
(1 punt) Raoneu quin inconvenient o error presenta l'algorisme i per quina raó es manifesta.
c.
(2 punts) Assenyaleu el número de línia que cal esmenar i escriviu la correcció necessària.
Solución
Según los criterios oficiales de corrección
a) Iteració 1: actual
Solución: 'A'
a) Iteració 1: visited
Solución: ['A']
a) Iteració 1: to_visit
Solución: ['B']
a) Iteració 2: actual
Solución: 'B'
a) Iteració 2: visited
Solución: ['A', 'B']
a) Iteració 2: to_visit
Solución: ['C', 'D']
a) Iteració 3: actual
Solución: 'C'
a) Iteració 3: visited
Solución: ['A', 'B', 'C']
a) Iteració 3: to_visit
Solución: ['D', 'A']
a) Iteració 4: actual
Solución: 'D'
a) Iteració 4: visited
Solución: ['A', 'B', 'C', 'D']
a) Iteració 4: to_visit
Solución: ['A']
a) Iteració 5: actual
Solución: 'A'
a) Iteració 5: visited
Solución: ['A', 'B', 'C', 'D', 'A']
a) Iteració 5: to_visit
Solución: ['B']
b) Raoneu quin inconvenient o error presenta l'algorisme i per quina raó es manifesta.
Solución: L'algorisme entra en un bucle infinit (no acaba mai). Això passa perquè a la condició de la línia 10 només es verifica que el veí no es trobi a la llista d'espera (to_visit), però no es comprova si el vèrtex ja ha estat visitat i processat prèviament (és a dir, si és present a visited). Com que el graf té un cicle orientat (), els vèrtexs del cicle es reintrodueixen a la cua una vegada i una altra.
c) Assenyaleu el número de línia que cal esmenar.
Solución: 10
c) Escriviu la correcció necessària.
Solución: ```python if v not in to_visit and v not in visited: ```
La explicación paso a paso, hecha con IA, es Premium. Premium
Resuélvelo aquí mismo: corrección automática, pistas y solución paso a paso.