Large language models (LLMs) have demonstrated impressive success in a wide range of natural language processing tasks due to their extensive general knowledge of the world. The performance of LLMs is heavily dependent on the quality of prompts, while traditional prompt engineering is labor-intensive and challenging for prompt optimization. Recent advances in graph-based methods have shown that graphs can better depict the structural correlations in text data, providing LLMs with rich contextual information. Additionally, leveraging fully interactive feedback from LLMs further enhances their performance. To this end, we propose a novel LLM-agnostic framework for prompt optimization, namely GRL-Prompt, which aims to automatically construct optimal in-context prompts via heterogeneous graph-empowered reinforcement learning in an end-to-end manner. To provide structured action/state representation for optimizing prompts, we first construct a heterogeneous graph to better represent the correlation between the user query and candidate in-context examples. Moreover, a policy network is formulated to action on selecting a set of in-context examples in a rewardable order to construct the final prompt. The experimental results show that GRL-Prompt outperforms state-of-the-art methods, achieving average increases of 0.10 in ROUGE-1, 0.07 in ROUGE-2, 0.07 in ROUGE-L, and 0.05 in BLEU.