Grafs

Capítols

1. 5.1
   Grafs: representació

   Matriu d'adjacència o llistes d'adjacència: cada representació va millor per a un tipus de graf.

   Llegit
2. 5.2
   BFS i DFS

   Recórrer un graf en amplada o en profunditat. Són la base de molts altres algorismes.

   Llegit
3. 5.3
   Ordenació topològica

   Ordenar els vèrtexs d'un graf dirigit acíclic perquè cada aresta vagi cap endavant.

   Llegit
4. 5.4
   Dijkstra

   Trobar els camins mínims des d'un vèrtex quan els pesos no són negatius.

   Llegit
5. 5.5
   Prim i Kruskal

   Dues maneres de trobar l'arbre d'expansió mínim d'un graf: fent créixer un arbre o ajuntant arestes.

   Llegit
6. 5.6
   Consolidació

   Repàs de tot el tema en una sola pàgina: les idees clau de cada capítol, com encaixen entre elles i els errors més habituals. Ideal per repassar abans de l'examen.

   Llegit