سلام در گراف چه موقع پیمایش اول عمق و اول سطح برابر هستند؟
(۰۷ بهمن ۱۳۹۰ ۰۸:۰۶ ب.ظ)payman84ce نوشته شده توسط: سلام در گراف چه موقع پیمایش اول عمق و اول سطح برابر هستند؟
سلام در صورتی این دو یکسانند که درخت حاصل از پیمایش آنها همان گراف اولیه باشد. یعنی گراف اولیه هیچ یال اضافه تری نسبت به درخت حاصل از پیمایش نداشته باشد و با پیمایش گراف دوباره به درخت اولیه برسیم. پس گراف باید دور نداشته باشد و لزوما هم هر گرافی که دور ندارد پیمایش BFS و DFS آن یکسان نیست.
![[تصویر: 64845_1_1379095681.png]](https://img.manesht.ir/64845_1_1379095681.png)
مثلا در شکل اول با وجود نبودن دور ولی دو پیمایش یکسان نیستند ولی در دومی دو پیمایش یکسانند.
(۱۰ بهمن ۱۳۹۰ ۱۱:۱۸ ب.ظ)mjjoon نوشته شده توسط: خانم سعیده جوابتون درست نیست چون ربطی به دور نداره . مثال نقضش هم اینه . یک گراف حلقوی . هر دو پبمایش یکی هستند.
من فکر کنم این طوری بگیم بهتر باشه
درخت عمق اول و سطح اول برابرند هرگاه اگر در درختی رأسی دارای بیشتر از ۱ فرزند است نباید از فرزند چپ خود دارای نوه باشد.
بله حق باشماست.
این نکته که دور نداشته باشه مربوط به زمانی هست که بخواهیم درخت حاصل از دو پیمایش یکسان بشه و اینطوری نیست که حتما پیمایش bfs و dfs آن یکسان باشند. و درخت هم جهتدار نباشه.