فرض کنید طراح شهری می خواهد چند شهر معین را با جاده به هم وصل کند،
به قسمی که مردم بتوانند از هر شهر به شهر دیگر بروند. اگر محدودیت بودجه
ای در کار باشد ، ممکن است طراح بخواهد این کار را با حداقل مقدار جاده
کشی انجام دهد.
برای این مسئله دو الگوریتم حریصانه متفاوت : پریم و کروسکال بررسی می شود.
هر یک از این الگوریتم ها از یک ویژگی بهینه محلی استفاده می کند.
تضمینی وجود ندارد که یک الگوریتم حریصانه همواره حل بهینه بدهد، ثابت
می شود که الگوریتم های کروسکال و پریم همواره درخت های پوشای کمینه را
ایجاد می کنند.
پیچیدگی زمانی این دو الگوریتم:
(T (n) = 2 ( n – 1) ( n – 1) Є θ ( n²