প্রিম'স অ্যালগরিদম (Prim’s Algorithm)

স্প্যানিং ট্রি এবং MST (Spanning Tree and Minimum Spanning Tree) - গ্রাফ থিওরি (Graph Theory) - Computer Science

289

প্রিম'স অ্যালগরিদম (Prim’s Algorithm)

প্রিম'স অ্যালগরিদম হল একটি জনপ্রিয় গ্রাফ অ্যালগরিদম যা একটি ওজনযুক্ত গ্রাফের জন্য মিনিমাম স্প্যানিং ট্রি (MST) তৈরি করতে ব্যবহৃত হয়। এটি একটি গ্রাফের সমস্ত ভেরটেক্সকে অন্তর্ভুক্ত করে এবং মোট এজের ওজনকে সর্বনিম্ন রাখে।

অ্যালগরিদমের কাজ করার পদ্ধতি

শুরুতে একটি ভেরটেক্স নির্বাচন:
- প্রাথমিকভাবে গ্রাফের যেকোন একটি ভেরটেক্স নির্বাচন করুন এবং এটিকে MST-তে যুক্ত করুন।
সার্ভিসেবল এজ নির্বাচন:
- নির্বাচিত ভেরটেক্সের প্রতিবেশী ভেরটেক্সগুলির মধ্যে সর্বনিম্ন ওজনের এজ নির্বাচন করুন এবং সেই ভেরটেক্সটিকে MST-তে যুক্ত করুন।
মাল্টিপল পুনরাবৃত্তি:
- প্রক্রিয়াটি পুনরাবৃত্তি করুন যতক্ষণ না সমস্ত ভেরটেক্স MST-তে যুক্ত হয়।
শেষ:
- সমস্ত ভেরটেক্স যুক্ত হলে অ্যালগরিদম শেষ হবে এবং MST তৈরি হবে।

pseudocode for Prim’s Algorithm

Prim(Graph G, Vertex start):
  Create a priority queue Q
  Create a set MST to keep track of vertices in the minimum spanning tree
  Create a distance array dist[] and initialize it to ∞
  
  dist[start] = 0
  Q.push(start)

  while Q is not empty:
    current = Q.pop() // Get the vertex with the smallest distance
    MST.add(current)

    for each neighbor in G.neighbors(current):
      if neighbor is not in MST and weight(current, neighbor) < dist[neighbor]:
        dist[neighbor] = weight(current, neighbor)
        Q.push(neighbor) // Update the priority queue

  return MST

উদাহরণ

ধরি, আমাদের একটি গ্রাফ আছে:

    (2)
 A ------- B
  |         |
(1)       (3)
  |         |
 C ------- D
     (4)

ভেরটেক্স: A, B, C, D
এজ: A-B (2), A-C (1), B-D (3), C-D (4)

প্রিম'স অ্যালগরিদমের প্রক্রিয়া:

শুরু করি A থেকে:
- MST: {A}
- প্রতিবেশী: B (2), C (1)
সর্বনিম্ন ওজনের এজ C (1) নিয়ে আসি:
- MST: {A, C}
- প্রতিবেশী: A (1), D (4)
B (2) যুক্ত করি:
- MST: {A, C, B}
- প্রতিবেশী: D (3)
D (3) যুক্ত করি:
- MST: {A, B, C, D}

সুবিধা

সরলতা: অ্যালগরিদমটি সরল এবং বুঝতে সহজ।
দ্রুত: বিশেষ করে ঘন গ্রাফের জন্য কার্যকরী।

অসুবিধা

প্রাথমিক ভেরটেক্স নির্ভরতা: শুরু ভেরটেক্সের উপর ফলাফল নির্ভরশীল।
অন্য অ্যালগরিদমের তুলনায় ধীর: কিছু পরিস্থিতিতে ক্রুসক্যালের চেয়ে ধীর হতে পারে।

সারসংক্ষেপ

প্রিম'স অ্যালগরিদম একটি কার্যকরী পদ্ধতি যা একটি ওজনযুক্ত গ্রাফের জন্য মিনিমাম স্প্যানিং ট্রি তৈরি করতে ব্যবহৃত হয়। এটি সরল, কার্যকরী, এবং বাস্তব জীবনের নেটওয়ার্ক ডিজাইন ও অপ্টিমাইজেশনের জন্য প্রায়ই ব্যবহৃত হয়।

Content added By

Md. Shakil khan

স্প্যানিং ট্রি এবং এর গুরুত্ব ক্রাসকাল'স অ্যালগরিদম (Kruskal’s Algorithm) MST এর প্রয়োগ এবং সমস্যাসমূহ

প্রিম'স অ্যালগরিদম (Prim’s Algorithm)

প্রিম'স অ্যালগরিদম (Prim’s Algorithm)

অ্যালগরিদমের কাজ করার পদ্ধতি

pseudocode for Prim’s Algorithm

উদাহরণ

সুবিধা

অসুবিধা

সারসংক্ষেপ

Promotion

Satt AI

Hi, আমি SATT AI!

প্রিম'স অ্যালগরিদম (Prim’s Algorithm)

প্রিম'স অ্যালগরিদম (Prim’s Algorithm)

অ্যালগরিদমের কাজ করার পদ্ধতি

pseudocode for Prim’s Algorithm

উদাহরণ

সুবিধা

অসুবিধা

সারসংক্ষেপ

All Notifications

Promotion

Satt AI

Hi, আমি SATT AI!