الگوریتم کروسکال چگونه کار می کند؟

در الگوریتم کروسکال از لبه هایی با کمترین وزن شروع می کنیم و لبه ها را تا رسیدن به هدف ادامه می دهیم. مراحل پیاده سازی الگوریتم کروسکال به شرح زیر است:

ابتدا تمام لبه ها را از وزن کم تا زیاد مرتب کنید.
حالا لبه را با کمترین وزن بردارید و به درخت پوشا اضافه کنید. اگر لبه ای که باید اضافه شود چرخه ایجاد می کند، لبه را رد کنید.
به اضافه کردن لبه ها ادامه دهید تا به همه رئوس برسیم و یک درخت پوشا حداقل ایجاد شود.
توجه: باید توجه داشته باشد که با اضافه کردن لبه ها باعث ایجاد دور نشود که در این صورت اشتباه به دست خواهد امد.
کاربردهای الگوریتم کروسکال عبارتند از:

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

به مثاال بالا توجه کنید.

📣👨‍💻 @AlgorithmDesign_DataStructuer

اثبات 3 شرط قیضه Master


📣👨‍💻 @AlgorithmDesign_DataStructuer

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

📣👨‍💻 @AlgorithmDesign_DataStructuer

درخت به دو صورت قابل پیاده سازی است که یکی از آن ها آرایه می باشد.
برای درخت هایی که دارای گره زیاد پر یا کامل هستند ، آرایه مناسب خواهد
بود.چرا که تعداد خانه های خالی موجود درآرایه کمتر است.
فلذا ایجاد یک درخت کامل با استفاده از آرایه اگر درخت پر یا کامل باشد مناسب
است. اما اگر از نوع دیگر درخت مثال : اوریب به راست باشد مقرون و به صرفه
نخواهد بود.زیرا بییشتر خانه های آرایه خالی می شود و این برای ما به صرفه نیست.


📣👨‍💻 @AlgorithmDesign_DataStructuer

الگوریتم فلوید
در این الگوریتم از روش Dynamic Programming استفاده شده است که این روش از مرتبه n^3 می باشد که از هزینه بسیار کمتری نسبت به الگوریتم عادی آن دارد که اگر به صورت عادی بخواهیم کوتاه ترین مسیر رو پیدا کنیم فاکتوریلی خواهد شد و این اصلا مناسب نخواهد بود.

📣👨‍💻 @AlgorithmDesign_DataStructuer

جدول هش(Hash Table)
جدول هش یکی از مهم ترین ساختارهای داده است که از یک تابع خاص به نام تابع هش استفاده می کند که یک مقدار داده شده را با یک کلید برای دسترسی سریعتر به عناصر ترسیم می کند.

جدول هش یک ساختار داده ای است که برخی از اطلاعات را ذخیره می کند و اطلاعات اساساً دارای دو جزء اصلی است، یعنی کلید و مقدار. جدول هش را می توان با کمک یک آرایه انجمنی پیاده سازی کرد. کارایی نگاشت بستگی به کارایی تابع هش مورد استفاده برای نگاشت دارد.

به عنوان مثال، فرض کنید مقدار کلید John و مقدار شماره تلفن است، بنابراین وقتی مقدار کلید را در تابع هش به صورت زیر ارسال می کنیم:

Hash(key)= index;

وقتی کلید را در تابع هش پاس می دهیم، ایندکس را می دهد.

Hash(john) = 3;

مثال بالا جان را در شاخص 3 اضافه می کند.

اشکال تابع Hash

یک تابع Hash به هر مقدار یک کلید منحصر به فرد اختصاص می دهد. گاهی اوقات جدول هش از یک تابع هش ناقص استفاده می کند که باعث برخورد می شود زیرا تابع هش کلید یکسانی با دو مقدار متفاوت تولید می کند.

📣👨‍💻 @AlgorithmDesign_DataStructuer