Hoe kan ik het beste een graaf programmeren in Java?

[Rob]

Ik heb een opgave gekregen waarin een gewogen, gerichte, zwaksamenhangde graaf centraal staat (terzijde: Wat is in godsnaam een 'zwaksamenhangende graaf'? Ik weet wat een samenhangde graaf is, maar niet wat een zwaksamenhangende graaf is...).

Eventjes uitleg over PERT zodat je weet waar ik het over heb:

Deze graaf representeert een PERTNetwerk (PERT = Program Evaluation and Review Technique). In deze graaf moet iedere vertex gezien worden als een taak die moet gebeuren in een project.
Neem bv dit:

A ----------------> B ----------------> C
Gewicht van A-B: 2
Gewicht van B-C: 1

Het duurt dus 2 tijdseenheden om van A naar B te gaan, en 1 om van B naar C te gaan. Je moet ook eerst A->B doen voordat er verder kan worden gegaan met B->C. A->C is dus niet mogelijk.
Een ander eigenschap van deze specifieke graaf, is dat er vroegste en laatste tijden zijn.
De vroegste tijd is het vroegste tijdstip waarop alle activiteiten, samenkomend in dat knooppunt, voltooid kunnen zijn.
De laatste tijd is het laatste tijdstip waarop alle activiteiten, samenkomend in het knoop punt kunnen worden voltooid, zonder de voortgang van de overige activiteiten in het netwerk te vertragen.
Het gewicht van de edge is dus de tijdsduur.




De vroegste en laatste tijd voor een Vertex v zijn te bepalen via een algoritme, en dat is dan ook de opdracht.

Maar het lukt mij niet een graaf fatsoenlijk te modelleren. Mijn idee was om van een Vertex iedere buur en de afstand tot die buur in een collection op te slaan (ik weet nog niet welke) en dat per buur te doen. Dan zou je bijvoorbeeld zoiets als dit krijgen:
A -> B, kost 3
A -> D, kost 1
Maar ik kan nergens een collection vinden die zoiets in één keer op kan slaan.
Dan kan ik gewoon door die collection itereren en als ie een neighbour heeft, die nakijken, etc..

Is er dus een manier waarop ik dit makkelijk op kan slaan en kan gebruiken om er het kortste pad mee te bepalen, of moet ik misschien een andere aanpak proberen?

[DelftseStudent]

Adjacency lists worden veel gebruikt voor graven,
zwaksamenhangend ik denk dat er knopen zijn met graad 1
maar dat wel alles met elkaar verbonden is

verder haat ik PERT diagrammen!

[WelVrolijk]

Voor zover ik heb begrepen (van een google-actie op de dag dat je deze vraag stelde), is een gerichte graaf zwaksamenhangend als er tussen elk tweetal knopen een pad bestaat,
en sterksamenhangend als er tussen elk tweetal knopen een *gericht* pad bestaat.