Ontwerp en implementeer een algoritme dat nagaat of de toppen van een gegeven graaf met slechts twee kleuren kunnen worden gekleurd, zodanig dat twee adjacente toppen een verschillende kleur hebben. Denk ook na over de tijdscomplexiteit van je algoritme.
Implementeer de interface TweeKleuringZoeker1 in een klasse genaamd BreedteEerstZoeker. Hiervoor schrijf je een methode public Tweekleuring kleur(UndirectedGraph<String> graph), die een ongerichte graaf als argument heeft. Deze methode geeft een mogelijke kleuring (type TweeKleuring2) van de gegeven graaf terug, of null als er geen kleuring mogelijk is. Zoals de naam suggereert is het de bedoeling om breedte-eerst te werken.
We maken bij deze oefening gebruik van een eenvoudige grafenbibliotheek graphlib3. Deze bevat onder meer de klassen UndirectedGraph en Node. De API van deze bibliotheek vind je hier4. Neem eerst en vooral eens de API door en stel eventueel vragen hierover voor je begint te programmeren.
Gebruik eventueel de testklasse SimpleTest5 om je oplossing lokaal te testen. Je kan hierin eenvoudig extra testgevallen toevoegen.
Belangrijke opmerking: om met de grafenbibliotheek te kunnen werken in IntelliJ, moet je het bestand graphlib.jar6 toevoegen aan je project. Hiervoor ga je naar File -> Project Structure…. Vervolgens kies je Libraries en klik je op de knop met het plusteken (+). Kies voor Java en navigeer naar het gedownloade bestand graphlib.jar.
Het is niet toegestaan om de input van de methode kleur aan te passen. Indien je dit wel doet, zal de test falen.