Er zijn twee manieren om een graaf voor te stellen: - Adjacency lijst - Adjacency matrix

In deze opdracht maak je een functie converteer_matrix(matrix) die een adjacency matrix omzet naar een expliciete graaf (deze klasse is al gegeven).

Een adjacency matrix is een matrix waarbij de index van de matrix de node is en de waarde in de matrix aangeeft of er een edge is of niet. Bijvoorbeeld:

[[0, 1, 0, 1],

[0, 0, 0, 1], [1, 0, 0, 1], [0, 0, 0, 0]]

er is een edge van node 0 naar node 1 en van node 0 naar node 3 omdat de eerste (index 0) rij in de matrix de edges representeert en er een 1 staat op kolom 2 (index 1) en kolom 4 (index 3).

Pas in de gevegeven klasse de functie addEdge aan zodat de graaf altijd een ongerichte graaf is.

Gegeven een gerichte graaf gerepresenteerd door een adjacency lijst adj, schrijf een functie heeft_cycle(adj) die teruggeeft of de graaf een cycle bevat (True) of niet (False).

Een cycle is een pad in een graaf dat begint en eindigt in dezelfde vertex, waarbij elke stap de richting van de edges volgt.

Gegeven een n x m grid matrix bestaande uit 1 (land) en 0 (water), schrijf een functie aantal_eilanden dat het totaal aantal eilanden telt gerepresenteerd in het grid zonder het originele grid aan te passen. Een eiland is gedefinieerd als een groep geconnecteerde 1 cellen dat aan elkaar liggen horizontaal, verticaal, of diagonaal, en omgeven zijn door water (0) of the zijkant van het grid.

Voorbeeld:

Deze matrix heeft 4 eilanden.

Een minimum spanning tree (MST) voor een gewogen, geconnecteerde, en ongerichte graaf is een spanning tree (geen cycles en connecteerd alle vertices) dat minimum gewicht heeft. Het gewicht van een spanning tree is de som van alle edges in de tree.

Hieronder vind je de stappen voor het vinden van een MST gebruikmakend van Kruskal's algorithm:

• Sorteer alle edges op gewicht van klein naar groot
• Neem de kleinste edge. Check of het een cycle vormt in de spanning tree. Als er geen cycle wordt gevormd, voeg de edge toe. Anders, verwijder het.
• Herhaal stap 2 tot er (V-1) edges zijn in de spanning tree.

Gegeven een lijst van strings woorden, en twee verschillende strings start en doel, dat twee woorden voorsteld. Schrijf een functie woord_ladder(start, doel, woorden) die de lengte vindt van de kleinste ketting van string start tot doel zodat enkel één karakter van de aangrenzende woorden verschild en elk woord bestaat in de lijst woorden.

Opmerking: Print 0 als het niet mogelijk is om een ketting te vormen of beide woorden al gelijk zijn aan elkaar. Elk woord in de lijst woorden is even groot en bevat geen hoofdletters.