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