FONForum

Saša Jovanović
Moderator
Programiranje - 2006/04/15 18:14

Tim koji će se baviti programiranjem nezavisno od programskog jezika. Želja je da se nauče algoritmi koji su nezavisni od programskog jezika, ali postoji mogućnost formiranja podtimova koji bi se bavili konkretnim jezikom.
Vođa tima je Janković Nemanja i tim se sastaje svake sedmice
utorkom od 18-20h


Saša Jovanović
Moderator
Re:Programiranje - 2006/04/23 04:45

Evo malo i mi da se aktiviramo na forumu. Do sada su održana dva sastanka, koja su više bila uvodnog tipa i gde smo se dogovorili kojim smerom cemo ici. Za početak ćemo se baviti grafovima i to po knjizi "Algorithms in Java, Part 5: Graph Algorithms". Ja ću za sledeći susret (koji će biti posle praznika, dogovorićemo se naknadno kad) da pripremim neko poglavljel koje mi se učini zanimljivo. Poslednji sastanak je održan u četvrtak 20. aprila i pošto mnogi nisu mogli da dođu ja ću ukaratko da ispričam šta smo radili. Naravno, to je ono što sam ja upamtio, pa se nadam da će Nemanja da me dopuni ili ispravi ukoliko nešto nije tačno.
Počeli smo da radimo grafove. Prvi deo sastanka je bio više teorijski, gde su grafovi definisani, a na drugom delu smo uradili program koji ispituje da li je graf povezan i da li u njemu postoje ciklusi.
Dakle, da krenemo iz početka. Graf predstavlja skup elemenata među kojima postoji binarna operacija. Grafički, graf se predstavlja tako što su elementi skupa čvorovi grafa, a relacije među tim elementima predstavljaju grane grafa. Znači, postoji skup kružića (čvorova) koji su povezani linijama (grane). Ukoliko dva čvora nisu povezana, to znači da među njima nije definisana relacija. Tako se dolazi do ideje da se graf predstavlja preko matrice (n x n) gde n broj cvorova. Ukoliko između cvora n1 i n2 postoji veza u polju (n1,n2) matrice se stavlja "1", a ukoliko ne postoji veza stavlja se "0".
Ima još puno toga da se kaže, ali mislim da je to mnogo bolje usmenim putem. Još šta je bitno. Graf može biti orijentisan ili neorijentisan (simetričan). To sve zavisi od vrste relacije (tj. da li je ona simetrična ili ne).
Ono što smo mi radili na prošlom sastanku, je bili ispitivanje povezanosti grafa. Povezan graf je onaj graf u kome su svaka dva čvora povezana, bilo posredno ili neposredno. Takođe, graf je jako povezan ukoliko između svaka dva elementa postoji direktna veza.
U sledećem postu se nalazi kod koji proverava da li je graf povezan.

Saša Jovanović
Moderator
Grafovi - 2006/04/23 04:56

public class Graf {
int brElemenata;
int brVeza;
int[][] veze;

public void napraviGraf() throws IOException{
BufferedReader unos = new BufferedReader(new FileReader("unos.tmp"));
int[] red = new int[2];
red = razdvojiElemente(unos.readLine());

brElemenata = red[0];
brVeza = red[1];

veze = new int [brElemenata][brElemenata]; //pravimo matricu za predstavljanje grafa
for(int k=0; k<brElemenata; k++)
for(int j=0; j<brElemenata; j++)
veze[k][j]=0;

for(int i=0; i<brVeza; i++){
red = razdvojiElemente(unos.readLine());
veze[red[0]][red[1]] = 1;
veze[red[1]][red[0]] = 1; //Posto je matrica simetricna
}
}

private int[] razdvojiElemente(String jedanRed){
int[] red = new int[2];
try{
int indexRazmaka = jedanRed.indexOf(" ");
red[0]= Integer.parseInt(jedanRed.substring(0, indexRazmaka));
red[1]= Integer.parseInt(jedanRed.substring(indexRazmaka+1));
}catch(NumberFormatException exception){
System.err.println("Los format broja!");
}
return red;

}
public boolean povezanost(){
int[] temp = new int[brElemenata]; //niz kojim se ispituje povezanost
//ukoliko su svi elementi jednaki graf je povezan
for(int k=0; k<brElemenata; k++){
temp[k]=k; //pocetna vrednost niza
}
//posmatramo samo gornju polovinu matrice jer je simetricna
for(int k=0; k<brElemenata; k++)
for(int j=k; j<brElemenata; j++){
if(veze[k][j]==1){
int elem = temp[k]; // elemenat za poredjenje
for(int m=0; m<brElemenata; m++)
if(temp[m] == elem)
temp[m] = temp[j];
}

}
for(int m=0; m<brElemenata-1; m++)
if(temp[m] != temp[m+1])
return false;
return true;
}
public static void main(String[] args) {
try{
Graf graf = new Graf();
graf.napraviGraf();
if(graf.povezanost())
System.out.println("Graf je povezan!");
else
System.out.println("Graf nije povezan!");
}catch(IOException e){}
}
}


Saša Jovanović
Moderator
Re:Grafovi - 2006/04/23 05:29

Iz fajla "unos.tmp" se čita graf. U prvom redu se nalazi broj elemenata i broj veza (koji su razdvojeni praznim karakterom), a u sledećim redovima se nalaze čvorovi koji su u vezi. Za sledeći sadržaj fajla

5 4
1 3
4 0
3 4
0 2

niz temp kojim se proverava povezanost bi imao sledeći sadržaj:
i 0 1 2 3 4
r(i) 0 1 2 3 4
r(i) 2 1 2 3 4
r(i) 4 1 4 3 4
r(i) 4 3 4 3 4
r(i) 4 4 4 4 4

U prilogu se nalazi projekata rađenu u eclipse-u.
File Attachment:
File name: Programiranje.zip
File size:3306 bytes

Nemanja
User
Re:Grafovi - 2006/04/26 20:35

Samo mala ispravka:

Cvorovi su elementi skupa
An:{a1,a2,...,an}
gde graf predstavlja graficku interpretaciju relacije
r gde veza(ivica) izmedju dva cvora ,i i k ,postoji ako je definisana relacija
r(ai,ak).

Bilo bi dobro da svi pogledaju po malo onu knjigu
kolko ko moze , pa da sledeci put ja malo manje pricam a malo vise svi drugi to je ideja!

@Nizam - dobrodosao u programerski tim

Eeeee, nizam, ko ti je kriv kad nisi predavac mladim programer(ka)ima ... as saki & klif...

Eeeee, nizam, ko ti je kriv kad nisi predavac mladim programer(ka)ima ... as saki & klif...