در گراف G سمت چپ یک گراف وزن دار همبند غیر جهت است. دو گراف دیگر زیر مجموعه ای از گراف G هستند که در شامل تمام راس ها می باشد و دوری در آن تشکیل نشده است. درختT اول دارای هزینه 11 و درخت دوم دارای هزینه 7 می باشد پس هر دو درخت، درخت پوشا هستند ولی درخت دوم به دلیل هزینه کمتر درخت پوشای کمینه است.

درخت پوشاي مینیمم یا درخت فراگیر مینیمم در گرافهاي وزن دار ساخته می شود. فرض کنید گراف، یک گراف همبند باشد (یعنی بین هردو رأس متمایز آن یک مسیر وجود داشته باشد). منظور از یک درخت پوشا از این گراف درختی است که شامل همه رئوس این گراف باشد ولی فقط بعضی از یالهاي آنرا دربر گیرد. منظور از درخت پوشاي مینیمم (براي گراف همبند وزن دار) درختی است که بین درخت هاي پوشاي آن گراف، مجموع وزن یالهاي آن، کمترین مقدار ممکن باشد. براي به دست آوردن درخت پوشاي بهینه یک گراف جهت دار متصل می توان از الگوریتم هاي متفاوتی استفاده نمود. سه الگوریتم معروف برای پیدا کردن درخت پوشاي کمینه عبارتند از : الگوریتم کروسکال، الگوریتم پریم و الگوریتم سولین.

الگوریتم های دیگری نیز برای حل مسئله پیدا کردن درخت پوشای مینیمم ارائه شده اند که با رویکرد تکاملی مسئله را حل می کنند از جمله مهمترین آنها می توان به الگوریتم ژنتیک، PSO، رقابت استعماری و کرم شب تاب اشاره کرد.