ارائه یک راهکار برای حل مسئله فوق

با فرض آنکه یک گراف n عضوی داریم ماتریس مجاورت آن را چنانکه همه یالها بدون جهت فرض شده اند تشکیل می دهیم . مقادیر مثلث بالایی ماتریس از کاربر دریافت می شود چنانکه به ازای وجود یال مقدار یک و در غیر اینصورت مقدار صفر می پذیرد(مشابه فوق مقدار دهی کنید) اگر عدد غیر از این اعداد به برنامه داده شود با احتمال زیاد برنامه کارش را به درستی انجام نمی دهد و همچنین چنانچه گراف غیر همبند باشد در بیشتر موارد پاسخ صحیح نمی باشد (مگر در موارد خاص) . در نهایت کاربر بایستی داده های ورودی را صحیح وارد نماید مراحل دریافت اعداد برای یک گراف 3 عضوی در ادامه نمایش داده شده است .

[1,2] = 1
[1,3] = 1
[1,4] = 0
[2,3] = 1
[2,4] = 0
[3,4] = 1

آنچه در این الگوریتم صورت می گیرد به طور کلی بدین صورت است که فرض کنیم اندیس های ماتریس مجاورت، متناظر با گره های گرافمان باشد در این حالت اگر از گره A به گره B مسیر باشد آنگاه مختصات مربوط به A,B در ماتریس مجاورت ، مقدار یک خواهد داشت و لاغیر
A B C D
A 0 1 1 0
B ... 0 ... ...
C ... ... 0 ...
D ... ... ... 0

، بنابراین بررسی کرده ایم که از گره ای مثل A به کدام گره ها مسیر موجود است بنابراین بعد از این هیچیک از آن گره ها حق ندارند رنگ A را بپذیرند پس به سراغ گره B رفته و الی آخر . کار آرایه دوبعدی Deadline همین است که همه گره هایی را که به هر گره در ارتباط هستند را ذخیره نماید بطور نمونه از شکل مفابل می توان نتیجه گرفت B,C با گره A در ارتباطند و D ارتباطی با گره A ندارد پس می توان نتیجه گرفت B,C نمی توانند ( الزاماً ) هم رنگ A باشند ولی D می تواند ( ترجیحاً ) هم رنگ A باشد - در اینجاست که اگر از مفاهیم مجموعه ها استفاده کنیم می توانیم سادگی و گویایی الگوریتم و نهایتاً زمان اجرای آن را بهبود بخشیم ـ سپس بررسی می کنیم برای گره ای مثل x چه اتصالهایی برقرار است در نتیجه رنگ آن گره های متصل را نمی تواند بپذیرد ، بنابراین اولین رنگ امکان پذیر بعدی را می پذیرد حال ممکن است رنگی موجود نباشد و مجبور شویم یک رنگ اضافه نماییم ، در این الگوریتم این کار(انتخاب رنگ) با شماره اعداد انجام می شود در انتها رنگ انتخابی توسط زیر روال Select_color در آرایه ای به نام color و در خانه متناظر با آن گره ذخیره می شود همچنین آرایه دوبعدی Matrix به عنوان ماتریس مجاورت در این الگوریتم در نظر گرفته شده است ، آرایه دیگری به نام Last موجود است که که در واقع اشاره گری است به آخرین عنصر از آرایه Deadline به منظور ذخیره سازی عنصر بعدی در مکان مناسب .

در پیاده سازی این الگوریتم زیر تابعی به نام Select_color وجود دارد که رنگ مناسب را به گره در حال پردازش نسبت می دهد این کار با توجه به رنگهای انتساب داده شده صورت می گیرد.