![[تصویر: 149452_1_1379087161.gif]](https://img.manesht.ir/149452_1_1379087161.gif)
سوال : درخت پوشای DFS گراف بالا را رسم کنید.
توی پاسخ زده: اگه از A شروع کنیم DFS میشه:
ABFECDGI
حالا بگید چرا آخرش IG نشده ؟
و ضمنا چرا درخت حاصل به صورت زیر شده ؟
![[تصویر: 149452_2_1379087161.gif]](https://img.manesht.ir/149452_2_1379087161.gif)
با سلام . این جواب کلا غلطه چون اصلا I به G در گراف اولیه وصل نیست که بخواد تو درخت DFS بیاد . یا شما اشتباه شکل رو کشیدین یا اون منبعی رو که میخونید. برای اون گرافی که شما رسم کردین درخت جستجوی اول عمقش به صورت زیر درمیاد.
اینجا اولویت پیمایش فرزندان یک گره همون برچسب الفبا ست . خوب از A شروع کنید. از بین بچه هاش اونی که اولویت بیشتری داره (B) انتخاب کنید و دوباره به همین ترتیب بچه هاش رو پیمایش کن.
آقا گزینه ها فقط ایناست :
۱)
![[تصویر: 149537_1_1379087042.gif]](https://img.manesht.ir/149537_1_1379087042.gif)
=====
۲)
![[تصویر: 149537_2_1379087042.gif]](https://img.manesht.ir/149537_2_1379087042.gif)
=====
۳)
![[تصویر: 149537_3_1379087042.gif]](https://img.manesht.ir/149537_3_1379087042.gif)
=====
۴)
![[تصویر: 149537_4_1379087042.gif]](https://img.manesht.ir/149537_4_1379087042.gif)
===========
گزینه ی ۳ رو فقط زده جواب
====
ضمنا اینو اساتید شریف توی کتاب پردازش جواب دادن(جناب حسن تکابی و جناب رضا حسامی فرد)
(hesami@ce.sharif.edu و takabi@ce.sharif.edu)
شاید به احتمال کم اشتب زده باشن.
اما از کجا مطمئن جواب شما درسته ؟
لطفا منبع موثقی بیارید تا مبحث مربوطه رو خوب توضیح داده باشه
===
مسلما جواب غلطه، اصلا از I به G که یال نداریم، بعد از ملاقات C,D توسط گره E به سراغ گره I می ریم و بعد تا B عقب بر می گردیم و در آخر هم از B به گره G می ریم.
وقتی B رو ملاقات کردیم حتما باید I رو هم ملاقات کنیم از طریق گره E و سپس برگردیم به گره B و بعد G رو ملاقات کنیم یا میشه اول G رو ملاقات کنیم و بعد بریم سراغ F و بعدش E و ...
(۲۸ آذر ۱۳۹۱ ۱۲:۳۱ ق.ظ)csharpisatechnology نوشته شده توسط: ضمنا اینو اساتید شریف توی کتاب پردازش جواب دادن(جناب حسن تکابی و جناب رضا حسامی فرد)
(hesami@ce.sharif.edu و takabi@ce.sharif.edu)
شاید به احتمال کم اشتب زده باشن.
اما از کجا مطمئن جواب شما درسته ؟
لطفا منبع موثقی بیارید تا مبحث مربوطه رو خوب توضیح داده باشه
===
مجدد سلام . اخه این که ۱ استادی از دانشگاه شریف اینو جواب داده که دلیل نمیشه . اول اینکه مگه اساتید شریف اشتباه نمیکنن ؟ دوم اینکه شاید اشتباه تایپی باشه . به هر حال بحث درخت های جستجو مبحث راحتیه و به همین دلیل حالا ۱ کتاب خاص گفتن شاید ضروری نباشه چون همه خوب گفتن به خاطر راحتیش . ولی بازم شما میتونید کتاب پوران یا کتاب پارسه رو بخونید.
احتمالا تو صورت سوال یک یال از B به I بوده که اشتباها این یال بین I و E رسم شده.
واسه همین گره I نزدیک به B رسم شده.
در اینصورت جواب همون گزینه ۳ می شه.
این سوال با تعاریفی که ما تو کتابا مقسمی و پوران خوندیم حل نمیشه درخت پوشا مطلب ساده ای هست بعید میدونم اونا اینو بلد نباشن من احتمال میدم یه تعریف دیگه ای از درخت پوشای عمقی باشه که ما نمیدونیم!