Grafenalgoritmen

Grafenalgoritmen är en samling algoritmer som arbetar på grafer, matematiska strukturer bestående av noder (vertices) och kanter (edges). Grafer kan vara riktade eller oriktade, viktade eller omärkta, och de representeras ofta med adjacenslistor eller adjacensmatriser. De används inom områden som nätverk, transportplanering, sociala strukturer och optimering.

Vanliga problem är traversering och sökning, där flirting med funktioner som djupet-först-sökning och bredden-först-sökning används för att besöka noder och avgöra anslutningar. Andra centrala problem är kortaste vägen och vägval i viktade grafer, där algoritmer som Dijkstra (för icke-negativa vikter), Bellman-Ford (tålig mot negativa vikter) och Floyd-Warshall (alla par vägar) används. För viktade grafer är också metoder för att hitta minimal kostnad att ansluta alla noder viktiga.

Minsta kostnads-spannträd (MST) utgör en annan viktig inriktning, där Prim och Kruskal hittar ett träd som kopplar samman alla noder med minimal total vikt. För flödesproblem finns algoritmer som Ford-Fulkerson, Edmonds-Karp och Dinic som beräknar maximal flöde och motsvarande min cut.

Andra viktiga tekniker inkluderar topologisk sortering för riktade acykler, cykel- och anslutningsdetektion samt algoritmer som hanterar dynamiska grafer där kanter eller noder tillkommer eller försvinner. Grafalgoritmer innebär ofta olika paradigm, såsom greedy, dynamisk programmering, randisering och heuristik, och deras komplexitet varierar beroende på grafens storlek och representation.

---