[es] - [Zadatak] Struktura (klasa) podataka Graph

moki21

Član broj: 144879
Poruke: 1
*.sava.sczg.hr.

Profil

[Zadatak] Struktura (klasa) podataka Graph

^{10.05.2007. u 10:27 - pre 206 meseci}

Pozdrav svima!

Dobio sam zadatak da napisem strukturu Graph koja omogucava pohranjivanje i obradu usmjerenih grafova. Treba napisati neke metode tipa dodavanja cvora, grane, brisanja cvora, grane...
Cvor (node) je neka struktura koja vraca jedinstven ID i ima metodu za to...
Problem je u tome jer se grafu prilikom stvaranja mora moci odrediti koje ce se strukture koristiti za spremanje liste cvorova i pohranu liste susjeda za svaki cvor...
Napravio sam verziju koja sprema cvorove u <vector> i listu susjeda u <list> iz STL-a, ali to prof. nije dovoljno...
Zato bih molio nekoga za pomoc ako ima ideju kako to izvesti.

Hvala

Odgovor na temu

rumpl

Član broj: 54959
Poruke: 156
*.net81-66-199.noos.fr.

Profil

Re: [Zadatak] Struktura (klasa) podataka Graph

^{12.05.2007. u 13:07 - pre 206 meseci}

Citat:

Problem je u tome jer se grafu prilikom stvaranja mora moci odrediti koje ce se strukture koristiti za spremanje liste cvorova i pohranu liste susjeda za svaki cvor...

A koje strukture hoce da koristis?

"The problem with the world is that everyone is a few drinks behind."
-Humphrey Bogart

Odgovor na temu

K-up

Član broj: 142706
Poruke: 10
*.ns.ac.yu.

Profil

Re: [Zadatak] Struktura (klasa) podataka Graph

^{14.05.2007. u 11:09 - pre 206 meseci}

Ocigledno zeli da omogucis da cvorovi budu ili u listi ili u vektoru, a da u svakom cvoru susedi budu ili u listi ili u vektoru. Prakticno, da napravis razlicite implementacije grafa i cvora... Ne znam da li sve moras da zamotas u nekakve templejte ili ne, pitaj coveka.

Ovo je sasvim validan, stavise interesantan zahtev. Imao sam prilike da pisem nekakve dekodere koji rade sa grafovima pomocu STL kontejnera, i zaista je vrlo znacajno kakva ce biti implementacija grafa. Obrada grafa je gomila stalnih prolaza kroz listu cvorova, pa u svakom cvoru kroz njegovu listu grana. U nekim primenama, cvorovi se stalno brisu; u nekim drugim se grane stalno raskidaju (odn. cvorovi brisu iz liste suseda); ali cesto je i zahtev da nekoj grani pristupis indeksiranjem, pa performanse jako zavise od implementacije.

Vredi procitati nesto i o boost::graph klasi iz biblioteke Boost, mozda. Ne znam kako su oni pisali...

Odgovor na temu

K-up

Član broj: 142706
Poruke: 10
*.ns.ac.yu.

Profil

Re: [Zadatak] Struktura (klasa) podataka Graph

^{15.05.2007. u 09:28 - pre 206 meseci}

Evo ga -- sigurno ti je previse, al mozda ti da neku ideju o tome sta graph klasa treba da ima: http://www.boost.org/libs/graph/doc/table_of_contents.html

Odgovor na temu