studenti.rs home page

 

 

Algoritmi i strukture podataka  (2+1+1)

Literatura:

1. Dovedan: Pascal i programiranje, ZOTK, Ljubljana, 1989.

2. Budin: Informatika 2, Element, Zagreb, 1998.

3. Lipschutz: Theory and Problems of Data Structures, Mc Graw Hill, 
    1986.

4. Knuth: The Art of Computer Programming, Vol. 1. Fundamental 
   Algorithms, Vol. 2.  Seminumerical Algorithms,
   Addison Wesley, 1997.

5. Lipschutz, Lipson: Discrete Mathematics, Mc Graw Hill,New York
    1997.

 

 

Sadržaj predmeta:

1. Osnovni pojmovi
2. Elementarni podaci
3. Slučajni brojevi
4. Linearne strukture
    a) Vektori i matrice
    b) Stogovi
    c) Redovi
5. Nelinearne strukture
    a) Stabla
    b) Grafovi
6. Rekurzije

background image

 

 

Primjer: Raskršće “Đakovština” (prije rekonstrukcije)

C
D

A B

E
F

G

H    I

AH

CE

DF

BI

AG

Fizikalna stvarnost

Matematički model

 

 

C
D

A B

E
F

G

H    I

AH

CE

FD

IB

AG

     5555

1.

2.

3.

4.

5.

background image

 

 

Algoritam bojanja grafa:
Boja=1

Sve dok

 graf nije obojan

   Obavljaj 

bojanje(Boja)

   Povećaj

 Boja 

za 1

   

Kraj sve dok

Algoritam procedure 

bojanje (Boja)

/*Neobojane čvorove čiji susjedi nisu obojani bojom 

Boja

 

   obojaj bojom 

Boja

*/

Stavi 0 u sve elemente vektora 

Obojani[] 

Nađi neobojani čvor

 i

Postavi 

Obojani[1]=i

Postavi

 nb

=1

Naznači da je 

i

-ti čvor obojan bojom 

Boja

Za svaki 

čvor

 j

 grafa činiti

    

Ako je 

čvor 

j 

neobojan i njegovi susjedi nisu u vektoru

    

Obojani[] 

postavi boju čvora

 j 

na

 Boja

Program

Bojanje.cpp

 

Želiš da pročitaš svih 102 strana?

Prijavi se i preuzmi ceo dokument.

Prijavi se Napravi nalog

Ovaj materijal je namenjen za učenje i pripremu, ne za predaju.

Slični dokumenti