👍7👨💻1
الگوریتم کروسکال چگونه کار می کند؟
در الگوریتم کروسکال از لبه هایی با کمترین وزن شروع می کنیم و لبه ها را تا رسیدن به هدف ادامه می دهیم. مراحل پیاده سازی الگوریتم کروسکال به شرح زیر است:
ابتدا تمام لبه ها را از وزن کم تا زیاد مرتب کنید.
حالا لبه را با کمترین وزن بردارید و به درخت پوشا اضافه کنید. اگر لبه ای که باید اضافه شود چرخه ایجاد می کند، لبه را رد کنید.
به اضافه کردن لبه ها ادامه دهید تا به همه رئوس برسیم و یک درخت پوشا حداقل ایجاد شود.
توجه: باید توجه داشته باشد که با اضافه کردن لبه ها باعث ایجاد دور نشود که در این صورت اشتباه به دست خواهد امد.
کاربردهای الگوریتم کروسکال عبارتند از:
از الگوریتم کروسکال می توان برای چیدمان سیم کشی برق در بین شهرها استفاده کرد.
می توان از آن برای برقراری اتصالات LAN استفاده کرد.
به مثاال بالا توجه کنید.
📣👨💻 @AlgorithmDesign_DataStructuer
در الگوریتم کروسکال از لبه هایی با کمترین وزن شروع می کنیم و لبه ها را تا رسیدن به هدف ادامه می دهیم. مراحل پیاده سازی الگوریتم کروسکال به شرح زیر است:
ابتدا تمام لبه ها را از وزن کم تا زیاد مرتب کنید.
حالا لبه را با کمترین وزن بردارید و به درخت پوشا اضافه کنید. اگر لبه ای که باید اضافه شود چرخه ایجاد می کند، لبه را رد کنید.
به اضافه کردن لبه ها ادامه دهید تا به همه رئوس برسیم و یک درخت پوشا حداقل ایجاد شود.
توجه: باید توجه داشته باشد که با اضافه کردن لبه ها باعث ایجاد دور نشود که در این صورت اشتباه به دست خواهد امد.
کاربردهای الگوریتم کروسکال عبارتند از:
از الگوریتم کروسکال می توان برای چیدمان سیم کشی برق در بین شهرها استفاده کرد.
می توان از آن برای برقراری اتصالات LAN استفاده کرد.
به مثاال بالا توجه کنید.
📣👨💻 @AlgorithmDesign_DataStructuer
👨💻4👍2🙏2
👨💻6👌2
👍3👨💻1
👍6🤔2👨💻1
الگوریتم بازگشتی برای یافتن بیشترین مقدار در یک آرایه از اعداد صحیح.
📣👨💻 @AlgorithmDesign_DataStructuer
📣👨💻 @AlgorithmDesign_DataStructuer
👍4👌2👨💻1
👍5👨💻2🎉1
👨💻3👍2
درخت به دو صورت قابل پیاده سازی است که یکی از آن ها آرایه می باشد.
برای درخت هایی که دارای گره زیاد پر یا کامل هستند ، آرایه مناسب خواهد
بود.چرا که تعداد خانه های خالی موجود درآرایه کمتر است.
فلذا ایجاد یک درخت کامل با استفاده از آرایه اگر درخت پر یا کامل باشد مناسب
است. اما اگر از نوع دیگر درخت مثال : اوریب به راست باشد مقرون و به صرفه
نخواهد بود.زیرا بییشتر خانه های آرایه خالی می شود و این برای ما به صرفه نیست.
📣👨💻 @AlgorithmDesign_DataStructuer
برای درخت هایی که دارای گره زیاد پر یا کامل هستند ، آرایه مناسب خواهد
بود.چرا که تعداد خانه های خالی موجود درآرایه کمتر است.
فلذا ایجاد یک درخت کامل با استفاده از آرایه اگر درخت پر یا کامل باشد مناسب
است. اما اگر از نوع دیگر درخت مثال : اوریب به راست باشد مقرون و به صرفه
نخواهد بود.زیرا بییشتر خانه های آرایه خالی می شود و این برای ما به صرفه نیست.
📣👨💻 @AlgorithmDesign_DataStructuer
👨💻4👍2
الگوریتم فلوید
در این الگوریتم از روش Dynamic Programming استفاده شده است که این روش از مرتبه n^3 می باشد که از هزینه بسیار کمتری نسبت به الگوریتم عادی آن دارد که اگر به صورت عادی بخواهیم کوتاه ترین مسیر رو پیدا کنیم فاکتوریلی خواهد شد و این اصلا مناسب نخواهد بود.
📣👨💻 @AlgorithmDesign_DataStructuer
در این الگوریتم از روش Dynamic Programming استفاده شده است که این روش از مرتبه n^3 می باشد که از هزینه بسیار کمتری نسبت به الگوریتم عادی آن دارد که اگر به صورت عادی بخواهیم کوتاه ترین مسیر رو پیدا کنیم فاکتوریلی خواهد شد و این اصلا مناسب نخواهد بود.
📣👨💻 @AlgorithmDesign_DataStructuer
👨💻5
👨💻2
جدول هش(Hash Table)
جدول هش یکی از مهم ترین ساختارهای داده است که از یک تابع خاص به نام تابع هش استفاده می کند که یک مقدار داده شده را با یک کلید برای دسترسی سریعتر به عناصر ترسیم می کند.
جدول هش یک ساختار داده ای است که برخی از اطلاعات را ذخیره می کند و اطلاعات اساساً دارای دو جزء اصلی است، یعنی کلید و مقدار. جدول هش را می توان با کمک یک آرایه انجمنی پیاده سازی کرد. کارایی نگاشت بستگی به کارایی تابع هش مورد استفاده برای نگاشت دارد.
به عنوان مثال، فرض کنید مقدار کلید John و مقدار شماره تلفن است، بنابراین وقتی مقدار کلید را در تابع هش به صورت زیر ارسال می کنیم:
Hash(key)= index;
وقتی کلید را در تابع هش پاس می دهیم، ایندکس را می دهد.
Hash(john) = 3;
مثال بالا جان را در شاخص 3 اضافه می کند.
اشکال تابع Hash
یک تابع Hash به هر مقدار یک کلید منحصر به فرد اختصاص می دهد. گاهی اوقات جدول هش از یک تابع هش ناقص استفاده می کند که باعث برخورد می شود زیرا تابع هش کلید یکسانی با دو مقدار متفاوت تولید می کند.
📣👨💻 @AlgorithmDesign_DataStructuer
جدول هش یکی از مهم ترین ساختارهای داده است که از یک تابع خاص به نام تابع هش استفاده می کند که یک مقدار داده شده را با یک کلید برای دسترسی سریعتر به عناصر ترسیم می کند.
جدول هش یک ساختار داده ای است که برخی از اطلاعات را ذخیره می کند و اطلاعات اساساً دارای دو جزء اصلی است، یعنی کلید و مقدار. جدول هش را می توان با کمک یک آرایه انجمنی پیاده سازی کرد. کارایی نگاشت بستگی به کارایی تابع هش مورد استفاده برای نگاشت دارد.
به عنوان مثال، فرض کنید مقدار کلید John و مقدار شماره تلفن است، بنابراین وقتی مقدار کلید را در تابع هش به صورت زیر ارسال می کنیم:
Hash(key)= index;
وقتی کلید را در تابع هش پاس می دهیم، ایندکس را می دهد.
Hash(john) = 3;
مثال بالا جان را در شاخص 3 اضافه می کند.
اشکال تابع Hash
یک تابع Hash به هر مقدار یک کلید منحصر به فرد اختصاص می دهد. گاهی اوقات جدول هش از یک تابع هش ناقص استفاده می کند که باعث برخورد می شود زیرا تابع هش کلید یکسانی با دو مقدار متفاوت تولید می کند.
📣👨💻 @AlgorithmDesign_DataStructuer
🙏5👨💻1