একটি স্প্যানিং ট্রি হল একটি অনডিরেক্টেড গ্রাফের সাবসেট যাতে সব ভার্টেক্স ন্যূনতম সংখ্যক এজ দিয়ে কানেক্টেড থাকে।
যদি গ্রাফে সব ভার্টেক্স কানেক্টেড থাকে, তবে কমপক্ষে একটি স্প্যানিং ট্রি থাকবে। একটি গ্রাফে একাধিক স্প্যানিং ট্রি থাকতে পারে।
মিনিমাম স্প্যানিং ট্রি
একটি মিনিমাম স্প্যানিং ট্রি (MST) হল একটি কানেক্টেড ওয়েটেড অনডিরেক্টেড গ্রাফের এজের সাবসেট যা সব ভার্টেক্সকে একসাথে কানেক্ট করে ন্যূনতম পসিবল টোটাল এজ ওয়েটের সাথে। MST বের করতে প্রাইম বা ক্রুস্কাল অ্যালগরিদম ব্যবহার করা যায়। এই অধ্যায়ে আমরা প্রাইম অ্যালগরিদম আলোচনা করব।
আমরা আলোচনা করেছি, একটি গ্রাফে একাধিক স্প্যানিং ট্রি থাকতে পারে। যদি n সংখ্যক ভার্টেক্স থাকে, স্প্যানিং ট্রিতে n - 1 সংখ্যক এজ থাকবে। এই প্রসঙ্গে, যদি গ্রাফের প্রতিটি এজ একটি ওয়েটের সাথে জড়িত থাকে এবং একাধিক স্প্যানিং ট্রি থাকে, তবে আমাদের গ্রাফের মিনিমাম স্প্যানিং ট্রি বের করতে হবে।
অধিকন্তু, যদি কোনো ডুপ্লিকেট ওয়েটেড এজ থাকে, তবে গ্রাফে একাধিক মিনিমাম স্প্যানিং ট্রি থাকতে পারে।
উপরের গ্রাফে আমরা একটি স্প্যানিং ট্রি দেখিয়েছি যদিও সেটি মিনিমাম স্প্যানিং ট্রি নয়। এই স্প্যানিং ট্রির কস্ট হল (5 + 7 + 3 + 3 + 5 + 8 + 3 + 4) = 38।
