الگوریتم BFS

[miracle]

Bfs رو سرچ کردم اما چیزی پیدا نکردم... آیا این درسته که bfs برای پیدا کردن فاصله کوتاه ترین مسیر به سورس نود استفاده میشه؟ اگر اینطوره .. چطوری؟ کاربرد Bfs واسه پیمایش چیه؟
tnx

[someCoder]

http://en.wikipedia.org/wiki/Breadth-first_search#Applications_of_BFS

[miracle]

ممنون ...تو این لینکی که دادید یکی از کاربردهای bfs رو Finding the shortest path between two nodes u and v (in an unweighted graph)
خب چه جوری؟ پیدا کردن کوتاه ترین مسیر مگه خودش یه الگوریتم جداگانه نداره؟

[someCoder]

یک الگوریتم نه، هزار و یک الگوریتم داره.
اگر گراف بدون وزن باشه (به عبارتی وزن همه یالها برابر)، این هم میتونه یک روش باشه.

[miracle]

خب حالا الگوریتم bfs چه جوری تغییر داده بشه که کوتاه ترین مسیر رو هم حساب کنه

[someCoder]

فرض کن کوتاهترین فاصله بین نقطه A و B رو میخوای.
از A شروع کن BFS رو و هر وقت به B رسیدی، مسیری که در همون جا طی شده، کوتاهترین هست.

[miracle]

من وزن دار و فک کردم...
------------
مثل اعدادی که در این گراف بدست آورده؟
http://img.majidonline.com/pic/95046/fadia1.JPG
چرا اون دو تا یال قرمز نیستن؟

[someCoder]

گفته بودم که:

اگر گراف بدون وزن باشه (به عبارتی وزن همه یالها برابر)، این هم میتونه یک روش باشه.

[miracle]

حالا اون یالهای قرمز و مشکی چی هستن؟

[someCoder]

حالا اون یالهای قرمز و مشکی چی هستن؟

سوالتو اول ندیدم.
اون یالها تو پیمایش استفاده نشده. بالاخره وقتی گراف رو پیمایش میکنی به یه درخت میرسی که مسلما تعداد یالهاش کوچکتر مساوی گراف میشه.

[miracle]

در bfs برای پیدا کردن دور میشه بگیم اگر E بزرگتر مساوی v باشه اونوقت دور داریم؟ یا طبق اون ایمیج اگر دو گره خاکستری باشن حلقه داریم؟