АСП1/Јун 2020 — разлика између измена
м (Kategorizacija) |
м (Prebacivanje na jednostavno isticanje sintakse) ознака: visualeditor-wikitext |
||
Ред 8: | Ред 8: | ||
==== Rešenje ==== | ==== Rešenje ==== | ||
<syntaxhighlight lang="milo"> | |||
DEEP COPY(head) | |||
p = head | |||
q = r = new_node = nil | |||
new_head = new_tail = nil | |||
while p ≠ nil do | |||
new_node = GETNODE | |||
value(new_node) = value(p) | |||
other_p(new_node) = other_p(p) | |||
if new_head = nil then | |||
new_head = new_node | |||
else | |||
next(new_tail) = new_node | |||
end_if | |||
new_tail = new_node | |||
p = next(p) | |||
end_while | |||
p = head | |||
q = new_head | |||
while p ≠ nil do | |||
r = new_head | |||
while r ≠ nil do | |||
if other_p(r) = p then | |||
other_p(r) = q | |||
end_if | |||
r = next(r) | |||
end_while | |||
p = next(p) | |||
q = next(q) | |||
end_while | |||
return new_head | |||
</syntaxhighlight> | |||
=== 2. zadatak === | === 2. zadatak === | ||
Ред 44: | Ред 46: | ||
==== Rešenje ==== | ==== Rešenje ==== | ||
<syntaxhighlight lang="milo"> | |||
POST TO INF(expression) | |||
stack = nil | |||
expr1 = expr2 = nil | |||
for c in expression do | |||
if IS_BINARY_OPERATOR(c) then | |||
expr1 = POP(stack) | |||
expr2 = POP(stack) | |||
PUSH(stack, "(" + expr1 + c + expr2 + ")") | |||
else if IS_UNARY_OPERATOR(c) then | |||
expr1 = POP(stack) | |||
PUSH(stack, "(" + c + expr1 + ")") | |||
else | |||
PUSH(stack, c) | |||
end_if | |||
end_for | |||
return POP(stack) | |||
</syntaxhighlight> | |||
<syntaxhighlight lang="milo"> | |||
PUSH(stack, value) | |||
node = GETNODE | |||
value(node) = value | |||
next(node) = stack | |||
stack = node | |||
</syntaxhighlight> | |||
<syntaxhighlight lang="milo"> | |||
POP(stack, value) | |||
if stack = nil then | |||
ERROR(Underflow) | |||
else | |||
node = stack | |||
value = value(node) | |||
stack = next(stack) | |||
FREENODE(node) | |||
return value | |||
end_if | |||
</syntaxhighlight> | |||
=== 3. zadatak === | === 3. zadatak === | ||
Ред 235: | Ред 241: | ||
==== Rešenje ==== | ==== Rešenje ==== | ||
Struktura pogodna za dekodiranje Morzeovih kodova jeste binarno stablo gde grane ulevo označavaju da kod na tom mestu sadrži tačku a grane udesno da kod na tom mestu sadrži crtu i u svakom čvoru se čuva u koje slovo se dekodira kod čije su grane praćene da bi se stiglo do tog čvora, ili 0 ako se taj kod ne dekodira ni u jedno slovo. | Struktura pogodna za dekodiranje Morzeovih kodova jeste binarno stablo gde grane ulevo označavaju da kod na tom mestu sadrži tačku a grane udesno da kod na tom mestu sadrži crtu i u svakom čvoru se čuva u koje slovo se dekodira kod čije su grane praćene da bi se stiglo do tog čvora, ili 0 ako se taj kod ne dekodira ni u jedno slovo. | ||
<syntaxhighlight lang="milo"> | |||
DECODE MORSE(msg) | |||
i = 0 | |||
new_msg = "" | |||
while msg[i] ≠ 0 do | |||
p = root | |||
while (msg[i] ≠ ' ') and (p ≠ nil) do | |||
if msg[i] = '.' then | |||
p = left(p) | |||
else if msg[i] = '-' then | |||
p = right(p) | |||
else | |||
ERROR(Invalid code) | |||
end_if | |||
i = i + 1 | |||
end_while | |||
i = i + 1 | |||
if (p = nil) or (sign(p) = 0) then | |||
ERROR(Invalid code) | |||
end_while | |||
new_msg = new_msg + sign(p) | |||
end_while | |||
return new_msg | |||
</syntaxhighlight> | |||
=== 3. zadatak === | === 3. zadatak === | ||
Ред 360: | Ред 368: | ||
* Eksterna težinska dužina puta je zbir proizvoda dužina puteva od korena do svakog eksternog čvora i težine tih eksternih čvorova. | * Eksterna težinska dužina puta je zbir proizvoda dužina puteva od korena do svakog eksternog čvora i težine tih eksternih čvorova. | ||
Za potrebe ovog algoritma smatra se da su eksterni čvorovi izjednačeni sa listovima. | Za potrebe ovog algoritma smatra se da su eksterni čvorovi izjednačeni sa listovima. | ||
<syntaxhighlight lang="milo"> | |||
CALC EXT WPL(root) | |||
QUEUE_INIT(Q_nodes) | |||
QUEUE_INIT(Q_levels) | |||
INSERT(Q_nodes, root) | |||
INSERT(Q_levels, 0) | |||
node = nil | |||
level = 0 | |||
pwe = 0 | |||
while not QUEUE_EMPTY(Q_nodes) do | |||
node = DELETE(Q_nodes) | |||
level = DELETE(Q_levels) | |||
if (left(node) = nil) and (right(node) = nil) then | |||
pwe = pwe + level * weight(node) | |||
end_if | |||
if left(node) ≠ nil then | |||
INSERT(Q_nodes, left(node)) | |||
INSERT(Q_levels, level + 1) | |||
end_if | |||
if right(node) ≠ nil then | |||
INSERT(Q_nodes, right(node)) | |||
INSERT(Q_levels, level + 1) | |||
end_if | |||
end_while | |||
return pwe | |||
</syntaxhighlight> | |||
== Treći kolokvijum == | == Treći kolokvijum == | ||
Ред 391: | Ред 401: | ||
==== Rešenje ==== | ==== Rešenje ==== | ||
<syntaxhighlight lang="milo"> | |||
RELABEL(G, n) | |||
topsort_length = 0 | |||
for i = 1 to n do | |||
in_deg[i] = 0 | |||
for j = 1 to n do | |||
if M[j, i] then | |||
in_deg[i] = in_deg[i] + 1 | |||
end_if | |||
end_for | |||
if in_deg[i] = 0 then | |||
topsort_length = topsort_length + 1 | |||
topsort[topsort_length] = i | |||
end_if | |||
end_for | |||
for i = 1 to n do | |||
node = topsort[i] | |||
for j = 1 to n do | |||
if M[node, j] then | |||
in_deg[j] = in_deg[j] - 1 | |||
if in_deg[j] = 0 then | |||
topsort_length = topsort_length + 1 | |||
topsort[topsort_length] = j | |||
end_if | |||
end_if | |||
end_for | |||
end_for | |||
return topsort | |||
</syntaxhighlight> | |||
=== 2. zadatak === | === 2. zadatak === | ||
Ред 659: | Ред 671: | ||
==== Rešenje ==== | ==== Rešenje ==== | ||
Obilaskom po širini ili dubini se u neusmerenom grafu može detektovati ciklus tako što prilikom obilaska detektujemo da posećujemo čvor koji smo već posetili, a da to nije otac trenutnog čvora u stablu obilaska. | Obilaskom po širini ili dubini se u neusmerenom grafu može detektovati ciklus tako što prilikom obilaska detektujemo da posećujemo čvor koji smo već posetili, a da to nije otac trenutnog čvora u stablu obilaska. | ||
<syntaxhighlight lang="milo"> | |||
IS CYCLIC(G) | |||
for i = 1 to n do | |||
visited[i] = 0 | |||
end_for | |||
QUEUE_INIT(Q_nodes) | |||
QUEUE_INIT(Q_parents) | |||
INSERT(Q_nodes, 1) | |||
INSERT(Q_parents, 0) | |||
node = parent = 0 | |||
while not QUEUE_EMPTY(Q_nodes) do | |||
node = DELETE(Q_nodes) | |||
parent = DELETE(Q_parents) | |||
for (node, i) ∈ E do | |||
if i = parent then | |||
continue | |||
end_if | |||
if visited[i] then | |||
return true | |||
end_if | |||
INSERT(Q_nodes, i) | |||
INSERT(Q_parents, node) | |||
visited[i] = true | |||
end_for | |||
end_while | |||
return false | |||
</syntaxhighlight> | |||
[[Категорија:Рокови]] | [[Категорија:Рокови]] | ||
[[Категорија:АСП1]] | [[Категорија:АСП1]] |
Верзија на датум 28. август 2020. у 11:41
Prvi kolokvijum
1. zadatak
Postavka
Data je ulančana lista kod koje svaki element ima određeni informacioni sadržaj, pokazivač na sledeći element u listi, kao i pokazivač na neki proizvoljan element liste. Napisati u pseudokodu funkciju DEEP_COPY koja prihvata pokazivač na prvi element liste i pravi kopiju liste sa istim načinom i poretkom povezivanja kao u polaznoj listi (duboka kopija).
Rešenje
DEEP COPY(head)
p = head
q = r = new_node = nil
new_head = new_tail = nil
while p ≠ nil do
new_node = GETNODE
value(new_node) = value(p)
other_p(new_node) = other_p(p)
if new_head = nil then
new_head = new_node
else
next(new_tail) = new_node
end_if
new_tail = new_node
p = next(p)
end_while
p = head
q = new_head
while p ≠ nil do
r = new_head
while r ≠ nil do
if other_p(r) = p then
other_p(r) = q
end_if
r = next(r)
end_while
p = next(p)
q = next(q)
end_while
return new_head
2. zadatak
Postavka
Neka je datoj funkciji POST_TO_INF prosleđen neki aritmetički izraz u postfiksnom obliku (expression). Operandi su velika slova engleskog alfabeta. Napisati iterativnu implementaciju ove funkcije koja kao rezultat vraća dati aritmetički izraz transformisan u infiksnu formu. Rezultujući izraz formirati korišćenjem potpunih zagrada.
Rešenje
POST TO INF(expression)
stack = nil
expr1 = expr2 = nil
for c in expression do
if IS_BINARY_OPERATOR(c) then
expr1 = POP(stack)
expr2 = POP(stack)
PUSH(stack, "(" + expr1 + c + expr2 + ")")
else if IS_UNARY_OPERATOR(c) then
expr1 = POP(stack)
PUSH(stack, "(" + c + expr1 + ")")
else
PUSH(stack, c)
end_if
end_for
return POP(stack)
PUSH(stack, value)
node = GETNODE
value(node) = value
next(node) = stack
stack = node
POP(stack, value)
if stack = nil then
ERROR(Underflow)
else
node = stack
value = value(node)
stack = next(stack)
FREENODE(node)
return value
end_if
3. zadatak
Postavka
Vektorska implementacija prioritetnog reda
U prioritetni red se prvo redom ubacuju sledeći elementi 2, 18, 19, 1, 9, 6. Nakon toga se iz reda uklanjaju dva elementa i potom dodaju elementi 15, 17 i 11, redom. Kapacitet vektora u koji se smeštaju elementi je 7. Manji broj označava veći prioritet. Za svaki od datih načina implementacije prikazati izgled reda nakon inicijalnog umetanja, nakon svakog brisanja i svakog umetanja poslednja tri elementa (15, 17 i 11). Ukoliko implementacija koristi neke dodatne pokazivače, naznačiti ih ispod odgovarajućeg indeksa u vektoru.
- Implementacija održavanjem uređenosti reda
- Implementacija markiranjem elemenata, bez umetanja preko markiranog elementa
- Implementacija markiranjem elemenata, sa umetanjem preko markiranog elementa
Rešenje
1 | 2 | 6 | 9 | 18 | 19 | |
2 | 6 | 9 | 18 | 19 | ||
6 | 9 | 18 | 19 | |||
6 | 9 | 15 | 18 | 19 | ||
6 | 9 | 15 | 17 | 18 | 19 | |
6 | 9 | 11 | 15 | 17 | 18 | 19 |
2 | 18 | 19 | 1 | 9 | 6 | |
2 | 18 | 19 | X | 9 | 6 | |
X | 18 | 19 | X | 9 | 6 | |
X | 18 | 19 | X | 9 | 6 | 15 |
18 | 19 | 9 | 6 | 15 | 17 | |
18 | 19 | 9 | 6 | 15 | 17 | 11 |
2 | 18 | 19 | 1 | 9 | 6 | |
2 | 18 | 19 | X | 9 | 6 | |
X | 18 | 19 | X | 9 | 6 | |
15 | 18 | 19 | X | 9 | 6 | |
15 | 18 | 19 | 17 | 9 | 6 | |
15 | 18 | 19 | 17 | 9 | 6 | 11 |
4. zadatak
Postavka
Neka se blok-dijagonalna matrica definiše kao kvadratna matrica A dimenzija n x n čiji su nenulti elementi smešteni samo u okviru blokova dimenzije k x k koji se nalaze na glavnoj dijagonali matrice, kao na slici i važi uslov n mod k = 0. Ukratko objasniti postupak smeštanja i izvesti adresnu funkciju pri pristupu proizvoljnom elementu matrice A[1:n, 1:n] smeštene po vrstama. Smatrati da se jedan element matrice smešta u tačno jednu memorijsku reč.
- | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|
1 | X | X | ||||
2 | X | X | ||||
3 | X | X | ||||
4 | X | X | ||||
5 | X | X | ||||
6 | X | X |
Rešenje
- Prvo gledamo u kojem se "bloku" na dijagonali nalazi element koji biramo. Taj blok možemo naći kao .
- Nakon toga, možemo na osnovu indeksa bloka (koji kreće od 0) možemo naći i indekse za gornji levi ćošak tog bloka kao .
- Sada računamo indeks trenutnog elementa na osnovu tri podatka: koliko se elemenata nalazi u prethodnim blokovima, koliko se elemenata nalazi iznad trenutnog elementa u trenutnom bloku i koliko se elemenata nalazi levo od trenutnog elementa u trenutnom bloku.
- Prethodni blokovi: (u svakom bloku se nalazi po elemenata)
- Iznad: (u svakom redu nalazi se elemenata)
- Levo:
- Konačna adresna funkcija:
- Uslov:
Drugi kolokvijum
1. zadatak
Postavka
Postorder i preorder obilazak
- Da li je, pomoću datog preorder i postorder obilaska binarnog stabla moguće rekonstruisati jedinstveno binarno stablo? Detaljno obrazložiti odgovor.
- Ukoliko je preorder obilazak stabla VALDENJOM, a postorder obilazak stabla DLEAOMJNV, rekonstruisati stablo. Ukoliko postoji više mogućih stabala, dati izgled svakog od njih.
Rešenje
- Ne može, jer ako neki čvor ima samo jedno dete ne može se odrediti da li je to levo ili desno dete samo iz preorder i postorder obilaska tog stabla.
- Moguće su četiri rekonstrukcije, jer se ne zna da li je čvor D levo ili desno dete čvora L i takođe da li je čvor J levo ili desno dete čvora N.
V V V V / \ / \ / \ / \ A N A N A N A N / \ / / \ / / \ \ / \ \ L E J L E J L E J L E J / / \ \ / \ / / \ \ / \ D O M D O M D O M D O M
2. zadatak
Postavka
Slova Morzeove azbuke kodiraju se kao kombinacija crtica (-) i tačaka (.) (A = .- , B= -… , itd.). Neka je poznat način kodiranja svih slova azbuke i poznato je da su kodovi prefiksni, odnosno da kraći kod može biti prefiks dužeg koda.
- Predložiti i opisati strukturu stabla pogodnu za operaciju dekodovanja pojedinačnih simbola poruke.
- Implementirati funkciju DECODE_MORSE koja na osnovu strukture predložene pod a) dekodira neku zadatu poruku. Poruka je prosleđena kao argument funkcije (msg) i predstavlja nisku crtica i tacaka. Smatrati da su kodirana slova odvojena blanko znakovima.
Rešenje
Struktura pogodna za dekodiranje Morzeovih kodova jeste binarno stablo gde grane ulevo označavaju da kod na tom mestu sadrži tačku a grane udesno da kod na tom mestu sadrži crtu i u svakom čvoru se čuva u koje slovo se dekodira kod čije su grane praćene da bi se stiglo do tog čvora, ili 0 ako se taj kod ne dekodira ni u jedno slovo.
DECODE MORSE(msg)
i = 0
new_msg = ""
while msg[i] ≠ 0 do
p = root
while (msg[i] ≠ ' ') and (p ≠ nil) do
if msg[i] = '.' then
p = left(p)
else if msg[i] = '-' then
p = right(p)
else
ERROR(Invalid code)
end_if
i = i + 1
end_while
i = i + 1
if (p = nil) or (sign(p) = 0) then
ERROR(Invalid code)
end_while
new_msg = new_msg + sign(p)
end_while
return new_msg
3. zadatak
Postavka
Primenom LZW algoritma prikazati postupak kodiranja znakovnog niza BIBBIDIBOBBIDIBOO, ako je data početna tabela sa kodovima simbola. Napisati kodiranu poruku i izgled tabele simbola nakon postupka kodiranja.
Rešenje
Krajnje kodirano: 0204153628033
Slovo | Kod |
---|---|
B | 0 |
D | 1 |
I | 2 |
O | 3 |
BI | 4 |
IB | 5 |
BB | 6 |
BID | 7 |
DI | 8 |
IBO | 9 |
OB | 10 |
BBI | 11 |
ID | 12 |
DIB | 13 |
BO | 14 |
OO | 15 |
Unos | String | Ispis | Dodaje se u tabelu |
---|---|---|---|
B | B | ||
I | BI | 0 (B) | BI |
B | IB | 2 (I) | IB |
B | BB | 0 (B) | BB |
I | BI | ||
D | BID | 4 (BI) | BID |
I | DI | 1 (D) | DI |
B | IB | ||
O | IBO | 5 (IB) | IBO |
B | OB | 3 (O) | OB |
B | BB | ||
I | BBI | 6 (BB) | BBI |
D | ID | 2 (I) | ID |
I | DI | ||
B | DIB | 8 (DI) | DIB |
O | BO | 0 (B) | BO |
O | OO | 3 (O) | OO |
O | 3 (O) |
4. zadatak
Postavka
Dužine puteva u stablu
- Formalno definisati i objasniti internu, eksternu i težinsku eksternu dužinu puta u binarnom stablu.
- Napisati u pseudokodu implementaciju funkcije koja izračunava težinsku eksternu dužinu puta binarnog stabla na čiji koren ukazuje pokazivač root. Smatrati da listovi stabla poseduju informaciju o težini čvora. Dozvoljeno koristiti gotove linearne strukture podataka.
Rešenje
- Interna dužina puta je zbir dužina puteva od korena do svakog internog čvora.
- Eksterna dužina puta je zbir dužina puteva od korena do svakog eksternog čvora.
- Eksterna težinska dužina puta je zbir proizvoda dužina puteva od korena do svakog eksternog čvora i težine tih eksternih čvorova.
Za potrebe ovog algoritma smatra se da su eksterni čvorovi izjednačeni sa listovima.
CALC EXT WPL(root)
QUEUE_INIT(Q_nodes)
QUEUE_INIT(Q_levels)
INSERT(Q_nodes, root)
INSERT(Q_levels, 0)
node = nil
level = 0
pwe = 0
while not QUEUE_EMPTY(Q_nodes) do
node = DELETE(Q_nodes)
level = DELETE(Q_levels)
if (left(node) = nil) and (right(node) = nil) then
pwe = pwe + level * weight(node)
end_if
if left(node) ≠ nil then
INSERT(Q_nodes, left(node))
INSERT(Q_levels, level + 1)
end_if
if right(node) ≠ nil then
INSERT(Q_nodes, right(node))
INSERT(Q_levels, level + 1)
end_if
end_while
return pwe
Treći kolokvijum
1. zadatak
Postavka
Dat je usmeren, aciklični graf predstavljen pomoću matrice susednosti kod koga su čvorovi numerisani od 1 do n. Objasniti kako se korišćenjem odgovarajućeg grafovskog algoritma mogu prenumerisati čvorovi tako da matrica susednosti postane gornja trougaona i napisati u pseudokodu funkciju RELABEL koja prenumerisanje.
Rešenje
RELABEL(G, n)
topsort_length = 0
for i = 1 to n do
in_deg[i] = 0
for j = 1 to n do
if M[j, i] then
in_deg[i] = in_deg[i] + 1
end_if
end_for
if in_deg[i] = 0 then
topsort_length = topsort_length + 1
topsort[topsort_length] = i
end_if
end_for
for i = 1 to n do
node = topsort[i]
for j = 1 to n do
if M[node, j] then
in_deg[j] = in_deg[j] - 1
if in_deg[j] = 0 then
topsort_length = topsort_length + 1
topsort[topsort_length] = j
end_if
end_if
end_for
end_for
return topsort
2. zadatak
Postavka
Floyd-ov algoritam. Na slici je dat usmereni težinski graf.
- Predstaviti dati graf odgovarajućom matričnom reprezentacijom.
- Pronaći najkraća rastojanja među čvorovima upotrebom Floyd-ovog algoritma. Postupak prikazati po koracima.
- Na osnovu rezultat pod b) rekonstruisati najkraću putanju između čvorova b i d.
Rešenje
Rešenje stavke pod c je bfaced.
- | a | b | c | d | e | f |
---|---|---|---|---|---|---|
a | ∞ | 7 | 3 | 10 | 8 | ∞ |
b | ∞ | ∞ | ∞ | 22 | ∞ | 1 |
c | ∞ | ∞ | ∞ | 5 | 2 | ∞ |
d | ∞ | ∞ | ∞ | ∞ | ∞ | 12 |
e | ∞ | ∞ | ∞ | 1 | ∞ | ∞ |
f | 6 | ∞ | ∞ | ∞ | ∞ | ∞ |
∞ | 7 | 3 | 10 | 8 | ∞ |
∞ | ∞ | ∞ | 22 | ∞ | 1 |
∞ | ∞ | ∞ | 5 | 2 | ∞ |
∞ | ∞ | ∞ | ∞ | ∞ | 12 |
∞ | ∞ | ∞ | 1 | ∞ | ∞ |
6 | 13 | 9 | 16 | 14 | ∞ |
0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 |
0 | 1 | 1 | 1 | 1 | 0 |
∞ | 7 | 3 | 10 | 8 | 8 |
∞ | ∞ | ∞ | 22 | ∞ | 1 |
∞ | ∞ | ∞ | 5 | 2 | ∞ |
∞ | ∞ | ∞ | ∞ | ∞ | 12 |
∞ | ∞ | ∞ | 1 | ∞ | ∞ |
6 | 13 | 9 | 16 | 14 | 14 |
0 | 0 | 0 | 0 | 0 | 2 |
0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 |
0 | 1 | 1 | 1 | 1 | 2 |
∞ | 7 | 3 | 8 | 5 | 8 |
∞ | ∞ | ∞ | 22 | ∞ | 1 |
∞ | ∞ | ∞ | 5 | 2 | ∞ |
∞ | ∞ | ∞ | ∞ | ∞ | 12 |
∞ | ∞ | ∞ | 1 | ∞ | ∞ |
6 | 13 | 9 | 14 | 11 | 14 |
0 | 0 | 0 | 3 | 3 | 2 |
0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 |
0 | 1 | 1 | 3 | 3 | 2 |
∞ | 7 | 3 | 8 | 5 | 8 |
∞ | ∞ | ∞ | 22 | ∞ | 1 |
∞ | ∞ | ∞ | 5 | 2 | 17 |
∞ | ∞ | ∞ | ∞ | ∞ | 12 |
∞ | ∞ | ∞ | 1 | ∞ | 13 |
6 | 13 | 9 | 14 | 11 | 14 |
0 | 0 | 0 | 3 | 3 | 2 |
0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 4 |
0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 4 |
0 | 1 | 1 | 3 | 3 | 2 |
∞ | 7 | 3 | 6 | 5 | 8 |
∞ | ∞ | ∞ | 22 | ∞ | 1 |
∞ | ∞ | ∞ | 3 | 2 | 15 |
∞ | ∞ | ∞ | ∞ | ∞ | 12 |
∞ | ∞ | ∞ | 1 | ∞ | 13 |
6 | 13 | 9 | 12 | 11 | 14 |
0 | 0 | 0 | 5 | 3 | 2 |
0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 5 | 0 | 5 |
0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 4 |
0 | 1 | 1 | 5 | 3 | 2 |
14 | 7 | 3 | 6 | 5 | 8 |
7 | 14 | 10 | 13 | 12 | 1 |
21 | 28 | 24 | 3 | 2 | 15 |
18 | 25 | 21 | 24 | 23 | 12 |
19 | 26 | 22 | 1 | 24 | 13 |
6 | 13 | 9 | 12 | 11 | 14 |
6 | 0 | 0 | 5 | 3 | 2 |
6 | 6 | 6 | 6 | 6 | 0 |
6 | 6 | 6 | 5 | 0 | 5 |
6 | 6 | 6 | 6 | 6 | 0 |
6 | 6 | 6 | 0 | 6 | 4 |
0 | 1 | 1 | 5 | 3 | 2 |
3. zadatak
Postavka
Na slici je dat protočni graf u okviru koga postoji već uspostavljen protok po pojedinim granama. Nacrtati rezidualni graf i navesti sve moguće puteve povećanog protoka u sledećoj iteraciji, uz navođenje kapaciteta za te puteve.
Rešenje
Mogući putevi povećanog protoka:
- SCBT (2)
- SACBT (2)
- SDECBT (2)
- SADECBT (2)
4. zadatak
Postavka
Neka se posmatra se neusmeren netežinski graf.
- Na koji način se u ovakvom grafu može ostvariti provera cikličnosti grafa korišćenjem algoritama za obilazak po širini i po dubini? Objasniti i nacrtati primer.
- Napisati u pseudokodu implementaciju funkcije koja korišćenjem obilaska po širini određuje da li je prosleđeni graf cikličan. Smatrati da je graf predstavljen matricom susednosti. Dozvoljeno je koristiti gotove linearne strukture podataka.
Rešenje
Obilaskom po širini ili dubini se u neusmerenom grafu može detektovati ciklus tako što prilikom obilaska detektujemo da posećujemo čvor koji smo već posetili, a da to nije otac trenutnog čvora u stablu obilaska.
IS CYCLIC(G)
for i = 1 to n do
visited[i] = 0
end_for
QUEUE_INIT(Q_nodes)
QUEUE_INIT(Q_parents)
INSERT(Q_nodes, 1)
INSERT(Q_parents, 0)
node = parent = 0
while not QUEUE_EMPTY(Q_nodes) do
node = DELETE(Q_nodes)
parent = DELETE(Q_parents)
for (node, i) ∈ E do
if i = parent then
continue
end_if
if visited[i] then
return true
end_if
INSERT(Q_nodes, i)
INSERT(Q_parents, node)
visited[i] = true
end_for
end_while
return false