Restgraphendarstellung beim Programmieren |
| 10.03.2010, 13:23 | plizzz | Auf diesen Beitrag antworten » |
| Restgraphendarstellung beim Programmieren das geht jetzt zwar ums Programmieren, aber da es sich nicht um speziellen Code dreht, sondern eher um eine Idee, denke ich dennoch, dass ich hier richtig bin. Und zwar ist die Situation folgende: Ich möchte den Algorithmus von Tarjan und Goldberg in C implementieren. Meine momentanen Graphenimplementierungen sahen immer so aus, dass ich den Graphen eingelesen habe als Array[struct Knoten] und jeder struct Knoten hatte dann bestimmte Einträge (eben die, die man jeweils gebraucht hat). Darunter war dann auch eine verkettete Liste von struct Kanten, also eine Adjazenzlistendarstellung. Da war es aber immer so, dass der Graph sich im Verlaufe nicht verändert hatte. Beim Tarjan-Goldberg-Algorithmus allerdings ist es nun mal so, dass immer der Restgraph betrachtet werden muss und ich überlege mir grade, wie man den möglichst gut implementieren kann. Dabei ist mir als erstes die folgende Lösung in den Sinn gekommen: Ich lese für jede Kante nebenher noch die gegenläufige ein und baue meinen Graphen dann praktisch aus der richtigen und der gegenläufigen Kantenmenge und speichere dann noch, welche Kante jetzt eine gegenläufige ist und welche nicht. Außerdem verbinde ich die jeweiligen Kantenpaare mir Pointern und speichere, welche Kanten jeweils aktuell im Graphen enthalten ist und welche nicht (als Eigenschaft der struct Kante). Damit habe ich dann doppelt so viele Kanten im Graphen und kann mit den Operationen die asymptotische Laufzeit einhalten. Allerdings sind es eben doch doppelt so viele und ich frage mich: Geht das evtl. besser, um Speicher/Laufzeit zu sparen? Da fällt mir dann aber keine Möglichkeit ein. Vielen Dank schonmal, plizzz |
||
| 10.03.2010, 16:06 | Reksilat | Auf diesen Beitrag antworten » |
| RE: Restgraphendarstellung beim Programmieren Hi plizz, Ich sehe gerade nicht, wie man da Speicher sparen könnte. Die Rückwärtskanten werden sowieso gebraucht, da es ja auch Netzwerke gibt, bei denen ein maximaler Fluss Kapazitäten auf allen Kanten benutzt und Du somit für alle Kanten eine Rückwärtskante implementieren musst. Dass Du so viel Speicher benötigst, musst Du also eh einplanen. Ansonsten dürftest Du die Rückwärtskanten immer erst dann einrichten, wenn sie gebraucht werden und anschließend wieder löschen. Das geht aber auf die Laufzeit. Ob eine Kante im aktuellen Residualgraphen enthalten ist, sieht man doch eigentlich daran, ob Ihr Fluss Null ist oder nicht. Muss man das extra speichern? Gruß, Reksilat. btw.: Wer hat das eigentlich nach "Bücher&Software/Programme" verschoben? Strenggenommen kann man den Thread mit Verweis aufs Infoboard schließen, aber wenn man ihn offen lässt gehört er imho zu Unimathe/Sonstiges. Zurückgeschoben. Gruß, Reksilat. |
||
| 11.03.2010, 11:59 | plizzz | Auf diesen Beitrag antworten » |
Ok, dann werde ich das mal so implementieren, wie ich mir das gedacht habe. Und es stimmt natürlich, dass man nicht extra speichern muss, ob eine Kante im Restgraphen enthalten ist, da man die Information ja aus dem Fluss bzw. der Restkapazität (>0 ?) bekommt. Danke jedenfalls. |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
