Tietorakenteet ja algoritmit harjoitustyö: Digraafit

Haettu syksyllä 1989. Alkuperäinen tarkastaja Kimmo Kari. Palautettu korjattavaksi 1990. Siirretty toiselle kääntäjälle (Borland C++ » GCC) ja käyttöjärjestelmään (MSDOS » Linux) 1996. Samalla ohjelman dokumentointi ja käyttöympäristö muutettu HTML-pohjaiseksi. Digraph '97:ssä (versio 2.1) C++-grafiikkaluokat poistettu ja käyttöliittymä kokonaan Javalle. Palautettu tarkistettavaksi: 8.9.1997 Kuvaus Tehtävänä oli tehdä: Perusoperaatiot digraafien käsittelylle Tallennusformaatti ja -operaatiot Editori digraafitiedostojen muokkaukselle Algoritmit: Lyhimmän polun etsintä. Tämä on ratkaistu käyttämällä Floydin algoritmia pienellä lisäyksellä. Kauppamatkustajan ongelma. Tämä on ratkaistu käyttämällä yksinkertaista rekursiivista generointifunktiota jonka avulla lyhin reitti etsitään. Jokaisesta kaupungista on oletettu kulkevan suora reitti jokaiseen toiseen kaupunkiin.

Graafiluokat (.h, .cc) Kauppamatkustajan ongelma Lyhimmän polun etsintä Pääohjelma, Makefile Common-luokat Editori (Java) Lähdekoodi Java Language Specification Kommentteja Ja tässä on sitten se Javapohjainen editori:

Lyhyt käyttöohje

Napit:

[Uusi] : Luo uusia solmuja

[Poista] : Poista solmuja klikkaamalla niitä

[Siirrä] : Siirrä solmuja painamalla niitä hiirellä ja vetämällä nappi painettuna

[Kytke] : Muodosta kytkentä solmusta toiseen painamalla hiirinappi alas solmun kohdalla ja vetämällä kytkentä toiseen solmuun

[Pura] : Pura olemassaoleva kytkentä samalla lailla kuin se tehtiinkin

[Merk. lähtö] : Merkitse lähtösolmu lyhimmän polun etsintää varten

[Merk. kohde] : Merkitse kohdesolmu lyhimmän polun etsintää varten

Algoritmit

• Kauppamatkustajan ongelma. Vaatii 1-10 solmua, joiden välille muodostaa lyhimmän reitin. Jos solmuja on enemmän, loput jätetään huomiotta. 10:llä solmulla voi kestää joitain minuutteja.

• Lyhimmän polun etsintä. Vaatii lähtö- ja kohdesolmun merkinnän, sekä ainakin yhden polun josta saa kuljettua.

Tekstimuotoinen muokkaus