Algorismes de grafs

Fonaments de grafs

Havel-Hakimi: Permet, de manera recursiva, reconèixer si una seqüència és gràfica.

DFS (Depth First Search): S'aplica a problemes de connectivitat (cercar components connexes o biconnexes) i, també, pot comprovar si un graf és acíclic.
BFS (Breadth First Search): S'aplica a problemes de coloració, la cerca del cicle més curt d'un graf o al càlcul de distàncies.
Dijkstra: S'aplica sobre un graf ponderat i calcula la distància des d'un vèrtex inicial a la resta de vèrtexs del graf.
Floyd: Cerca els camins mínims entre totes les parelles de vèrtexs d'un graf.

Kruskal: Cerca un arbre generador minimal i tria, en cada cas, l'aresta de menys pes que no firmi cicle amb les ja escollides.
Prim: Cerca un arbre generador minimal i tria, en cada cas, l'aresta de menys pes de les adjuntes als vèrtexs ja escollits. D'aquesta manera el graf const

ruit sempre és connex.

TSP (Travelling Salesman Problem): Troba el recorregut més curt passant per tots els nodes.