An element $x$ in a semigroup is said to be regular if there exists an element $y$ in the semigroup such that $x=xyx$. The element $y$ is said to be a regular part of $x$. Define the Cayley regularity graph of a semigroup $S$ to be a digraph with vertex set $S$ and arc set containing all ordered pairs $(x,y)$ such that $y$ is a regular part of $x$. In this paper, certain classes of Cayley regularity graphs such as complete digraphs, connected digraphs and equivalence digraphs are investigated. Furthermore, structural properties of the Cayley regularity graphs are theoretically applied to study perfect matchings of other algebraic graphs.