La méthode la plus naïve de construction est de parcourir chaque ligne et de se poser les questions suivantes :
- Quelles sont les variables qui sont modifiées après l'exécution de cette ligne (nœuds de départs).
- Quelles sont les variables que j'ai besoins pour réaliser l'opération (nœuds d'arrivés (dépendances)).
A savoir que le graphe n'est pas orienté.

La construction du graphe est assez simple en soit, le plus lourd c'est le calcul des couleurs qui n'est pas forcément optimal suivant l'algo choisi. L'algo de Welsh-Powel serait soit dit en passant suffisante mais comme dit précédemment n'assure pas une coloration optimal.
Ainsi, chaque couleur représente un registre. Si le nombre de couleur dépasse le nombre de registre de la machine, l'utilisation de la pile est nécessaire sauf si on augmente de façon virtuelle le nombre de registres. Par exemple partitionner un registre de 32 bits en 2 registres de 16 bits mais cela nécessite l'ajout d'instructions.

Mais une optimisation optimale est lié au ré ordonnancement des instructions. L'allocation des registres n'est pas suffisant en soit.

Ah oui sur un code conséquent, il risque d'y avoir énormément de nœuds (de variables) et donc l'algo de coloration risque d'être gourant en calculs (NP complet). L'idée est donc lors de la création du graphe d'essayer de minimiser le nombre de variables par prédiction. C'est-à-dire pondérer les nœuds avec une ancienneté. Un noeud avec une anciennetée élevée (c'est-à-dire avec une affectation la plus ancienne) aura une plus faible probabilité d'être réutilisé à x lignes d'instructions plus lointaines.