الگوریتم‌های گراف

توضیحات

در جلسه هفدهم درس طراحی الگوریتم دکتر حمید حاج سیدجوادی که اهمیت به سزایی در کنکور ارشد کامپیوتر و کنکور ارشد آی تی و نیز کنکور دکتری کامپیوتر و کنکور دکتری آی تی دارد، مطالب مهمی در باره الگوریتم‌های گراف ارائه می‌شود. ابتدا دو روش استاندارد برای ارئه گراف G = (V, E) مطرح می‌شود: 1- ليست مجاورت 2-ماتريس مجاورت. سپس الگوريتم جستجوی سطح-اول (BFS) تشریح می‌شود. شبه کد این الگوریتم و مرتبه زمانی آن و قضایا و نکات مربوطه مورد بحث قرار می‌گیرد. بعد از آن الگوريتم جستجوی عمق-اول (DFS) تشریح می‌شود. شبه کد این الگوریتم و مرتبه زمانی آن و قضایا و نکات و ویژگی‌های مربوطه مورد بحث قرار می‌گیرد. سپس طبقه‌بندی لبه‌ها در جنگل عمق اول ارائه شده و 4 نوع لبه معرفی و تشریح می‌شوند: لبه‌های درخت، لبه‌های پسین، لبه‌های پیش‌رو و لبه‌های صلیبی.