3

Algoritmi:

onkoKolmiota(G):
    for i = 1 to solmumaara:
        for j = i+1 to solmumaara:
            for k = j+1 to solmumaara:
                if A[i][j] and A[j][k] and A[k][i]:
                    return true
    return false

Yllä olevassa algoritmissa on käytössä verkon vierusmatriisiesitys.
Algoritmi käy suoraviivaisesti läpi kaikki kolmen solmun joukot ja
tarkistaa, muodostaako jokin niistä kolmion.

Algoritmin aikavaativuus on O(|V|^3), jossa |V| on verkon solmujen
määrä. Algoritmin tilavaativuus on O(1).

Vastaavan algoritmin voi toteuttaa myös verkon vieruslistaesityksen
avulla, mutta silloin algoritmi on hieman monimutkaisempi.

Arvostelu:

* algoritmin kuvaus: 3 p
* algoritmin koodi: 3 p
* vaativuusanalyysi: 2 p

Yllä oleva algoritmi ei ole kovin tehokas, mutta se on toimiva.
Tehokkaammissa algoritmeissa onkin usein ongelmana, että ne eivät
toimi jossain erikoistapauksessa.