e-commerce84
13-03-2010, 11:49
Ciao,
ho questo script che esplora un grafo. Lo script di fatto è una funzione che accetta un grafo rappresentato come una lista di liste e dovrebbe restituire il percorso compiuto durante l'esplorazione...ok...
Ora che ho tale funzione...dove e come gli posso passare una lista di liste? In pratica credo che dovrei dichiarare da qualche parte una lista di liste, passarla a tale funzione, mettere il risultato ritornato dalla funzione da qualche parte e stamparlo.
Non conosco Python...al corso di algoritmi ci hanno fornito tale listato...che devo fare per vederlo in funzione?
# ALOGORITMO DI VISITA DI UN GRAFO G:
#
# G è rappresentato per mezzo di una come una lista (indicizzata) di liste di
# adiacenza.
# Per esempio: G = [[1,2,3,4], [0,2], [0,1,4], [0,4], [0,2,3]] è un grafo in cui
# G[0] = [1,2,3,4] è la lista di tutti i nodi vicini al nodo 0 --> Il nodo 0 ha
# come vicini i nodi: 1,2,3,4. Il nodo 1 ha come vicini i nodi: 0,2 e così via.
def visit(G):
n = len(G) # Mette in n il numero di elementi di G (numero nodi del grafo)
A = set() # Insieme dei vicini al nodo corrente che dovranno essere visitati
A.add(0) # Metti il nodo 0 in A, il nodo 0 è stato visitato
# X rappresenta la lista degli n nodi che sono stati già visitati:
# Se X[i] = TRUE, allora l'i-esimo nodo è già stato visitato, se X[i] = FALSE
# significa che l'i-esimo nodo non è ancora stato visitato
X = [False]*n # Inizialmente non è stato visitato nessun nodo
# T è un array di n locazioni, inizialmente ogni locazione è settata al valore
# di default -1
T = [-1]*n
while len(A)>0: # Finchè l'insieme dei nodi A contiene ancora almeno un nodo
u = A.pop() # estrai un nodo da A e mettilo nella variabile u
# Setta a TRUE la u-esima posizione nella lista X dei nodi visitati
X[u] = True
# Per ogni elemento v presente nella u-esima sottolista della lista G ???
for v in G[u]:
if X[v] == False: # Se il nodo in posizione v di X non è stato ancora visitato
T[v] = u # metti il valore di u nella posizione v di T
A.add(v) # Aggiungi il valore v all'insieme A
return T # Ritorna T al chiamante
Grazie
ho questo script che esplora un grafo. Lo script di fatto è una funzione che accetta un grafo rappresentato come una lista di liste e dovrebbe restituire il percorso compiuto durante l'esplorazione...ok...
Ora che ho tale funzione...dove e come gli posso passare una lista di liste? In pratica credo che dovrei dichiarare da qualche parte una lista di liste, passarla a tale funzione, mettere il risultato ritornato dalla funzione da qualche parte e stamparlo.
Non conosco Python...al corso di algoritmi ci hanno fornito tale listato...che devo fare per vederlo in funzione?
# ALOGORITMO DI VISITA DI UN GRAFO G:
#
# G è rappresentato per mezzo di una come una lista (indicizzata) di liste di
# adiacenza.
# Per esempio: G = [[1,2,3,4], [0,2], [0,1,4], [0,4], [0,2,3]] è un grafo in cui
# G[0] = [1,2,3,4] è la lista di tutti i nodi vicini al nodo 0 --> Il nodo 0 ha
# come vicini i nodi: 1,2,3,4. Il nodo 1 ha come vicini i nodi: 0,2 e così via.
def visit(G):
n = len(G) # Mette in n il numero di elementi di G (numero nodi del grafo)
A = set() # Insieme dei vicini al nodo corrente che dovranno essere visitati
A.add(0) # Metti il nodo 0 in A, il nodo 0 è stato visitato
# X rappresenta la lista degli n nodi che sono stati già visitati:
# Se X[i] = TRUE, allora l'i-esimo nodo è già stato visitato, se X[i] = FALSE
# significa che l'i-esimo nodo non è ancora stato visitato
X = [False]*n # Inizialmente non è stato visitato nessun nodo
# T è un array di n locazioni, inizialmente ogni locazione è settata al valore
# di default -1
T = [-1]*n
while len(A)>0: # Finchè l'insieme dei nodi A contiene ancora almeno un nodo
u = A.pop() # estrai un nodo da A e mettilo nella variabile u
# Setta a TRUE la u-esima posizione nella lista X dei nodi visitati
X[u] = True
# Per ogni elemento v presente nella u-esima sottolista della lista G ???
for v in G[u]:
if X[v] == False: # Se il nodo in posizione v di X non è stato ancora visitato
T[v] = u # metti il valore di u nella posizione v di T
A.add(v) # Aggiungi il valore v all'insieme A
return T # Ritorna T al chiamante
Grazie