Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def ciclo_k(grafo, k):
- '''Realiza una muestra de algun ciclo de la red con un recorrido dfs,
- donde al menos se debe mostrar k articulos.
- Pre: El grafo fue creado.
- Pos: Devuelve un ciclo de la red o una exepcion en caso de no tener ningun ciclo
- con esa cantidad de k articulos como minimo.'''
- orden, padre = dfs_aristas_retr(grafo,None,k)
- ciclo = []
- for x in orden:
- if orden[x] != None:
- ciclo.append(orden[x])
- ciclo.reverse()
- fin = len(ciclo)-1
- f = ciclo[fin]
- ciclo.insert(0,f)
- return ciclo
- def dfs_aristas_retr(grafo,inicio, k):
- '''Realiza un recorrido dfs sobre un grafo no dirigido, termina el recorrido
- cuando encuentra una arista de retorno, es decir, encuentra un ciclo.
- Pre: El grafo ha sido creado
- Pos: Devuelve una lista con el ciclo, o NULL si no encontro ciclo.'''
- if not inicio: #Si no recibí inicio, elijo uno cualquiera
- claves = grafo.vertices.keys()
- inicio = claves[0]
- padre = {}
- visitado = {}
- orden = {}
- for x in grafo.vertices:
- visitado[x] = False
- padre[x] = None
- orden[x] = 0
- dfs_recurs(grafo, inicio, visitado, padre, orden, k)
- return padre,orden
- def dfs_recurs(G, v, visitados, padre, orden, k):
- '''Funcion recursiva que desciende en profundidad sobre un grafo.'''
- visitados[v] = True
- for w in G.adyacentes(v):
- n = orden[v]
- encontro_ciclo = False
- if not visitados[w]:
- padre[w] = v
- orden[w] = orden[v]+1
- dfs_recurs(G, w, visitados, padre, orden, k)
- elif visitados[w]:
- padre[w] = v
- orden[w] = orden[v]+1
- if k <= n : #Encontro el ciclo correcto {EN ESTE IF NO ENTRA NUNCA}
- encontro_ciclo = True
- elif (encontro_ciclo):
- break
- return
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement