11/07/08 12:29
FranCich
Qual è il codice dell'ordinamento topologico?
Es: Ho questo grafo (rappresentato con l'array delle adiacenze):
0->2->3->nil
1->4->nil
2->1->5->nil
3->nil
4->5->nil
5->3->nil
Ordine topologico: {0, 2, 1, 4, 5, 3}.
L'algoritmo è questo:
- seleziono i nodi nel grafo che non hanno archi entranti
- cancello i loro archi uscenti e costruisco l'ordine dei nodi dell'ordinamento topologico
- L'algoritmo va ovviamente iterato fino a quando non verifico più la prima condizione.
Ma qual è il codice (o pseudocodice)?
aaa
11/07/08 17:28
pierotofy
L ← Empty list where we put the sorted elements
Q ← Set of all nodes with no incoming edges
while Q is non-empty do
remove a node n from Q
insert n into L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into Q
if graph has edges then
output error message (graph has a cycle)
else
output message (proposed topologically sorted order: L)
Fonte:
en.wikipedia.org/wiki/…
Ultima modifica effettuata da pierotofy 11/07/08 17:30
12/07/08 15:32
FranCich
Ce l'ho fatta!!!
Ecco il codice:
procedure topological_sort(G:grafo);
var
col:colore;
dist,pred:vettore;
i,u:integer;
time:integer;
l:lista;
begin
l:=nil;
setlength(col,length(G));
setlength(dist,length(G));
setlength(pred,length(G));
time:=0;
for i:=0 to length(G)-1 do
begin
col[i]:='B';
dist[i]:=-1;
pred[i]:=-1;
end;
for u:=0 to length(G)-1 do
begin
if col[u]='B' then
DFS_topological(G,u,l,col,time,dist,pred);
end;
stampa(l);
end;
procedure DFS_topological(G:grafo; s:integer; var L:lista; var col:colore; var time:integer; var dist:vettore; var pred:vettore);
begin
col[s]:='G';
time:=time+1;
dist[s]:=time;
while g[s]<>nil do
begin
if (col[g[s]^.inf]='B') then
begin
pred[g[s]^.inf]:=s;
DFS_topological(G,g[s]^.inf,L,col,time,dist,pred);
end;
g[s]:=g[s]^.next;
end;
col[s]:='N';
time:=time+1;
dist[s]:=time;
ins_testa(L,s);
end;
Ultima modifica effettuata da FranCich 12/07/08 15:34
aaa
11/08/08 17:36
FranCich
Postato originariamente da inuyasca:
a occhio e croce dal'istruzione DFS_topological() e dalle fariabili settate cosi a a che vedere con la grafica ma in definitiva quando passi quelle informazioni perfino di tipo timer cosa dovrebbe produre quell'istruzione DFS.... ecc??? se tiro a indovinare è un filtro su un'immagine sparandola dovrebbe modificare un'immagine ma potrei sbagliarmi
No... non centra niente la grafica. Semplicemente va visitando il grafo ed una volta che il colore di un nodo visitato è nero ('N', ovvero è stato visitato e non ha più nodi adiacenti da visitare) viene inserito in testa ad una lista. In fine verrà stampata la lista (stampa(l) ovviamente non è una procedura di libreria del delphi)... ed ecco l'ordinamento topologico!!!
Ultima modifica effettuata da FranCich 11/08/08 17:38
aaa