ساختمان داده ها و الگوریتم

دیدگاه‌ها

2

سلام
چطور میشه تشخیص داد که دو راس مختلف همبند هستند یا نه؟
با تشکر

سلام ، اول اینکه "دو راس همبند" اصطلاح نادرستیه ، هم بندی از ویژگی های گرافه نه رئوس ، قسمت هایی از گراف که به هم مسیر داشته باشند اجزای هم بند گراف نامیده میشن ، درستش اینه بگیم چطور میشه فهمید از یک راس از یک گراف به راس دیگه مسیری وجود داره یا نه؟ 

متداول ترین روش استفاده از جست و جوی DFS هست ، اگر بخواهیم بررسی کنیم که از راس u به راس v مسیری وجود داره جست و جوی DFS رو از راس u آغاز می کنیم تا به راس v برسیم ، اگه به راس v رسیدیم که خب به خواسته مون رسیدیم ، اگر هم با DFS به v نرسیم یعنی مسیری از u به v وجود نداره.

 

افزودن دیدگاه جدید

Plain text

  • تگ‌های HTML مجاز نیستند.
  • نشانی صفحه‌ها وب و پست الکترونیک بصورت خودکار به پیوند تبدیل می‌شوند.
  • خطوط و پاراگراف‌ها بطور خودکار اعمال می‌شوند.