  We define the cluster algebra associated with the Q-system for the
Kirillov-Reshetikhin characters of the quantum affine algebra $U_q(\hat{\g})$
for any simple Lie algebra g, generalizing the simply-laced case treated in
[Kedem 2007]. We describe some special properties of this cluster algebra, and
explain its relation to the deformed Q-systems which appeared on our proof of
the combinatorial-KR conjecture. We prove that the polynomiality of the cluster
variables in terms of the ``initial cluster seeds'', including solutions of the
Q-system, is a consequence of the Laurent phenomenon and the boundary
conditions. We also give a formulation of both Q-systems and generalized
T-systems as cluster algebras with coefficients. This provides a proof of the
polynomiality of solutions of generalized T-systems with appropriate boundary
conditions.
