پیمایش گراف

این شبیه‌سازی نشان می‌دهد رایانه چگونه یک گراف را کاوش می‌کند. دانش‌آموزان جستجوی عرضی (BFS) یا عمقی (DFS) را انتخاب می‌کنند، گرهٔ شروع و سرعت را تعیین می‌کنند و تماشا می‌کنند که گره‌ها با رنگ‌ها در انتظار، در حال پردازش یا بازدیدشده نشان داده می‌شوند. نمایشگرها تعداد گره‌های بازدیدشده، اندازهٔ صف یا پشته و ترتیب بازدیدها را نشان می‌دهند و یک دکمه گراف تصادفی تازه می‌سازد. اجرای هر دو روش از یک گرهٔ شروع نشان می‌دهد که BFS مانند حلقه‌ها گسترش می‌یابد و DFS عمیق فرو می‌رود. این شبیه‌سازی برای درس‌های علوم کامپیوتر دربارهٔ ساختار داده و الگوریتم مناسب است.

• BFS را از گرهٔ 1 اجرا کنید و نمایشگر «ترتیب بازدید» را بخوانید.
• «روش» را روی DFS با همان «گرهٔ شروع» بگذارید و ترتیب را مقایسه کنید.
• ببینید «اندازهٔ صف / پشته» برای هر روش چگونه بزرگ و کوچک می‌شود.
• «گرهٔ شروع» را تغییر دهید و ببینید کل پیمایش چگونه عوض می‌شود.
• «ساخت دوبارهٔ گراف» را بزنید و پیش از اجرا ترتیب را پیش‌بینی کنید.

1. 1توضیح دهید جستجوی عرضی و عمقی چگونه گراف را کاوش می‌کنند.
2. 2صف را از پشته تشخیص دهید و هر کدام را به یک روش جستجو ربط دهید.
3. 3ترتیب بازدید را برای یک گراف کوچک پیش‌بینی کنید.
4. 4توضیح دهید چرا BFS مسیرهایی با کمترین تعداد یال را پیدا می‌کند.

پرسش‌هایی که معلم‌ها می‌پرسند