Beispiel Masse-Feder: Tarjan-Algorithmus
- Ausgangspunkt:
- Gleichungen als bipartiter Graph
- 2 Knotenmengen: Gleichungen und Variablen
- Kante = Variable kommt in Gleichung vor
- Ziel:
- numerierte Gleichungen
- gefärbte Kanten
- rot: Gleichung wird nach Variable
aufgelöst
("steht
links")
- blau: Variable wird in Gleichung
verwendet
("steht
rechts")
- Verfahren:
- suche Gleichungen mit genau einer
ungefärbten Kante
- Gleichung bekommt kleinste freie Nummer
- Kante wird rot
- andere Kanten der zugehörigen Variablen
werden blau
- suche Variablen mit genau einer ungefärbten Kante
- zugehörige Gleichung bekommt größte freie
Nummer
- Kante wird rot
- andere Kanten der zugehörigen Gleichung
werden blau
- iteriere, bis es nicht mehr weiter geht