مولفه همبندی در جاوا (Connected Component)

در این قسمت تیم کدگیت را با آموزش مولفه همبندی در جاوا (connected component)همراهی کنید. پیش نیاز این آموزش، آشنایی با جستجوی اول عمق و رابطه برنامه نویسی گراف و صف است.

مولفه همبندی (connected component)

در نظریه گراف، هر گراف ساده دارای یک یا بیشتر مولفه همبندی است. یک زیر گراف مانند H از G یک مولفه همبندی برای G است اگر و فقط اگر بین هر دو راس در H، دست‌کم یک مسیر وجود داشته باشد و با افزودن هر راس (و یا یال) دیگری از G به H  این خاصیت از بین برود. به عبارت دیگر هر زیر گراف بیشینه و همبند از G، یک مولفه همبندی G است.

با استفاده از هر روش جستجو در گراف، مانند جستجوی اول سطح و یا جستجوی اول عمق، می‌توان مولفه‌های همبندی یک گراف را پیدا کرد. به عنوان نمونه، برای پیدا کردن تمامی راس‌هایی که با راس v در یک مولفه همبندی قرار دارند می‌توان جستجوی اول عمق را از راس v شروع کرد و تمامی راس‌هایی که در طول جستجو به آن‌ها وارد می‌شویم در همان مولفه همبندی قرار دارند که راس v در آن است.

برای پیدا کردن مولفه‌های همبندی یک گراف، (G(V,E، نیاز به زمان اجرای خطی نسبت به طول ورودی (|O(|E| + |V داریم.(ویکیپدیا)

مولفه همبندی در جاوا

برای پیاده سازی مولفه همبندی در جاوا ما به این شیوه عمل میکنیم که یک گراف میسازیم و  روی تمامی راس ها جستجوی اول عمق صدا میزنیم(راس هایی که قبلا دیده شدند را بررسی نمیکنیم) و به ازای هر راس که این جستجو را انجام میدهیم تمام راس هایی که به این راس مسیر دارند (حتی به هم نیز مسیر دارند) را ملاقات میکنیم و جزو یک مولفه همبندی میشوند. سپس برای بقیه راس ها نیز همین کار میکنیم که اگر جز مولفه همبندی قبلی نباشند پس مولفه همبندی جدیدی است و روی آن راس نیز جستجوی اول عمق انجام میدهیم تا بقیه اعضیا این مولفه همبندی نیز پیدا شوند.

کد مولفه همبندی در جاوا شامل فیلد های زیر است:

  1. Marked: آرایه ای به تعداد راس های ما است و اگر راسی را ملاقات کنیم مقدار اندیس آن راس در آرایه marked میشود true (یعنی اگر راس 3 را ملاقات کنیم مقدار marked[3]=true میشود).
  2. Id: هر مولفه همبندی یک شناسه دارد. آرایه id شناسه مولفه همبندی هر راس را در خود نگه میدارد(اگر راس 3 در مولفه همبندی شماره 5 قرار دارد مقدار id[3]=5 میشود).
  3. Size: آرایه size تعداد راسهای درون مولفه همبندی خاص را به ما میدهد.
  4. Count: متغیر count تعداد کل مولفه همبندی در گراف ما را میدهد.

کد مولفه همبندی در جاوا شامل متدهای زیر است:

  1. Id: شناسه راس ورودی را به ما میدهد.
  2. Count: تعداد کل مولفه های همبندی گراف را به ما میدهد.
  3. Size: تعداد راس های درون مولفه همبندی که راس ورودی در آن قرار دارد را به ما میدهد.
  4. areConnected: بررسی میکند که دو راس خاص به هم مسیری دارند(درون یک مولفه همبندی خاص هستند ).
  5. Dfs: جستجوی اول عمق(در آموزش های گذشته توضیح داده شده است)
  6. CC: متد constructor کلاس ما است. و در این متد شروع به پیدا کردن مولفه های همبندی مختلف میکنیم با استفاده از جستجوی اول عمق.

تست مولفه همبندی در جاوا

برای تست کد مولفه همبندی در جاوا کافیست کد main زیر را بزنید:

در کد بالا ما یک گراف ساختیم و مولفه های همبندی مختلف آن را پیدا کردیم و آن ها را به صورت جداگانه چاپ کردیم.

فقط نکته ای که باید به آن شاره کرد این است که ما از صف در کد بالا برای نشان داد مولفه های همبندی مختلف استفاده کردیم و میتوان از داده ساختارهای دیگری نیز استفاده کرد.

خروجی مولفه همبندی در جاوا

خروجی کد بالا به صورت زیر است

پسورد: www.codegate.ir

 

دسته : java, جاوا, ساختمان داده در جاوا, گراف در جاوا

دیدگاه بگذارید

نظر شما چیست؟

مطلع کردن شما از
avatar

wpDiscuz