Algorithms/Boruvka MST

خوارزمية بوروفكا Boruvka مشابهة لخوارزميتي برم Prim وكروسكال Kruskal في كونها خوارزمية جشعة.

تعدّ خوارزمية بوروفكا أقدم خوارزمية لإيجاد الشجرة الممتدة الصغرى وقد وضعها بوروفكا سنة 1926م، قبل اختراع الحواسيب بفترة طويلة، وقد نشرت هذه الخوارزمية كطريقة لبناء شبكة فعّالة من التمديدات الكهربائية.

تستخدم خوارزمية بوروفكا كإحدى خطوات خوارزمية عشوائية ذات سرعة أعلى وتعمل بتعقيد زمني قدره O(E)‎.

خطوات الخوارزمية

تعمل خوارزمية بوروفكا على الرسوم البيانية المتصلة connected الموزونة weighted الموجّهة directed، وتتبع في عملها الخطوات التالية:

1. تهيّئ الخوارزمية جميع الرؤوس في الرسم البياني كمكوّنات منفردة (أو مجموعات).
2. تهيّئ شجرة ممتدة صغرى Minimum Spanning Tree فارغة.
3. تنفّذ الخوارزمية الخطوات التالية على كل مكوّن ما دام هناك أكثر من مكوّن واحد:
   1. تبحث الخوارزمية عن أقرب ضلع موزون يربط هذه المكوّن بأيّ مكوّن آخر.
   2. تضيف الخوارزمية ذلك الضلع إلى الشجرة الممتدة الصغرى إن لم يكن قد أضيف فيها سابقًا.
4. تعيد الخوارزمية الشجرة الممتدة الصغرى.

تتبع هذه الخوارزمية نفس مبدأ العمل الذي تتبعه خوارزمية Prim، فالشجرة الممتدة تعني وجوب اتصال جميع الرؤوس بعضها ببعض؛ لذا فإنّ المجموعتين الفرعيتين المفككتين disjoint subsets من الرؤوس يجب أن تتصل ببعضها البعض لتكوّن شجرة ممتدة، ويجب أن ترتبط كذلك مع الضلع ذي الوزن الأقل ليقال عنها حينئذٍ بأنّها شجرة ممتدة صغرى.

يوضّح المثال التالي خطوات عمل الخوارزمية باستخدام الرسم البياني أدناه:

تكون الشجرة الممتدة الصغرى فارغة في البداية، إذ يمثّل كل رأس مكوّنًا واحدًا كما هو موضح في الرسم البياني التالي:

سنبحث لكل مكوّن عن الضلع الذي يمتلك أقلّ وزن والذي يربط ذلك المكوّن بمكون آخر.

الأضلاع ذات الأوزان الأقلّ معلّمة في الرسم البياني التالي باللون الأخضر، وبهذا تصبح الشجرة الممتدة الصغرى: {0-1, 2-8, 2-3, 3-4, 5-6, 6-7}.

أصبحت المكوّنات بعد الخطوة السابقة: ‎{{0,1}, {2,3,4,8}, {5,6,7}}‎، وهي محاطة باللون الأزرق في الرسم البياني التالي:

تعاد الخطوة السابقة على المكوّنات الجديدة، وتعثر الخوارزمية على الضلع الذي يمتلك أقل وزن ويربط ذلك المكوّن بمكون آخر.

الأضلاع ذات الأوزان الأقلّ معلّمة في الرسم البياني التالي باللون الأخضر، وبهذا تصبح الشجرة الممتدة ‎{0-1, 2-8, 2-3, 3-4, 5-6, 6-7, 1-2, 2-5}‎.

في هذه المرحلة هناك مكوّن واحد يتألف من الرؤوس التالية: {0, 1, 2, 3, 4, 5, 6, 7, 8}‎ والتي تضمّ جميع الأضلاع. ينتهي عمل الخوارزمية في هذه المرحلة لأن هناك مكوّنًا واحدًا فقط.

تنفيذ الخوارزمية

تعرض الأمثلة التالية طريقة تنفيذ الخوارزمية في عدد من لغات البرمجة.

يمثّل الرسم البياني في الأمثلة التالية باستخدام مجموعة من الأضلاع وبنية البيانات وحِّد-جِد union-find لمتابعة عدد المكوّنات.

• C++‎:

#include <stdio.h> 

// بنية لتمثيل ضلع موزون في الرسم البياني
struct Edge 
{ 
	int src, dest, weight; 
}; 

// بنية لتمثيل رسم بياني متصل وغير موجه وموزون
// كمجموعة من الأضلاع
struct Graph 
{ 
	// V-> عدد الرؤوس
	// E-> عدد الأضلاع
	int V, E; 
    
    // يمثَّل الرسم البياني بمصفوفة من الأضلاع
    // ولما كان الرسم البياني غير موجه
    // فإنّ الضلع نفسه يمتد بين الوجهة والهدف
    // وبين الهدف والوجهة، أي أنّ الضلعين
    // يعدان ضلعًا واحدًا
	Edge* edge; 
}; 

// بنية لتمثيل مجموعة فرعية لاستخدام union-find
struct subset 
{ 
	int parent; 
	int rank; 
}; 

// تعريف مبدئي لبنية البيانات union-find
// boruvkaMST() يجري تعريف هذه الدوال بعد الدالة

int find(struct subset subsets[], int i); 
void Union(struct subset subsets[], int x, int y); 

// الدالة الرئيسية المسؤولة عن بناء الشجرة الممتدة الصغرى باستخدام خوارزمية بوروفكا
void boruvkaMST(struct Graph* graph) 
{ 
	// الحصول على البيانات الخاصة بالرسم البياني المعطى
	int V = graph->V, E = graph->E; 
	Edge *edge = graph->edge; 

	// حجز موقع في الذاكرة لإنشاء مجاميع الأضلاع الفرعية
	struct subset *subsets = new subset[V]; 

	// تخزّن هذه المصفوفة موقع الضلع ذي الوزن الأقل في المجموعة الفرعية
	// edges[] الموقع المخزّن لفهرسة المصفوفة
	int *cheapest = new int[V]; 

	// إنشاء المجاميع الفرعية مع عناصر مفردة
	for (int v = 0; v < V; ++v) 
	{ 
		subsets[v].parent = v; 
		subsets[v].rank = 0; 
		cheapest[v] = -1; 
	} 

	// في البداية هناك V شجرة مختلفة
	// وفي النهاية ستكون هناك شجرة واحدة وهي ستكون الشجرة الممتدة الصغرى
	int numTrees = V; 
	int MSTweight = 0; 

    // الاستمرار في دمج المكوّنات (أو المجاميع الفرعية)
    // إلى أن تُدمج جميع المكوّنات بعضها ببعض في شجرة ممتدة صغرى مفردة
	while (numTrees > 1) 
	{ 
		// تهيئة المصفوفة التي تحتوي على الأضلاع ذات الأوزان الأقل في كل مرة
		for (int v = 0; v < V; ++v) 
		{ 
			cheapest[v] = -1; 
		} 

		// التنقل عبر جميع الأضلاع واختيار
		// الضلع ذي الوزن الأقل في كل مكوّن
		for (int i=0; i<E; i++) 
		{ 
			// إيجاد المكوّنات (أو المجاميع الفرعية) لزاويتين
			// من الضلع الحالي
			int set1 = find(subsets, edge[i].src); 
			int set2 = find(subsets, edge[i].dest); 

            // إن كان الركنان التابعان للضلع الحالي
            // ينتميان للمجموعة نفسها، سيجري تجاهل الضلع الحالي            
			if (set1 == set2) 
				continue; 

			// وإلا سيجري التحقق من أنّ الضلع الحالي أقرب
			// من الأضلاع ذات الأوزان الأقل في المجموعتين الأولى والثانية
			else
			{ 
			if (cheapest[set1] == -1 || 
				edge[cheapest[set1]].weight > edge[i].weight) 
				cheapest[set1] = i; 

			if (cheapest[set2] == -1 || 
				edge[cheapest[set2]].weight > edge[i].weight) 
				cheapest[set2] = i; 
			} 
		} 

		// إضافة الأضلاع ذات الأوزان الأقل المختارة في أعلاه
		// وإضافتها إلى الشجرة الممتدة الصغرى
		for (int i=0; i<V; i++) 
		{ 
			// التحقق من وجود الضلع ذي الوزن الأقل في المجموعة الحالية
			if (cheapest[i] != -1) 
			{ 
				int set1 = find(subsets, edge[cheapest[i]].src); 
				int set2 = find(subsets, edge[cheapest[i]].dest); 

				if (set1 == set2) 
					continue; 
				MSTweight += edge[cheapest[i]].weight; 
				printf("Edge %d-%d included in MST\n", 
					edge[cheapest[i]].src, edge[cheapest[i]].dest); 

				// دمج المجموعتين الأولى والثانية وتخفيض عدد الأشجار
				Union(subsets, set1, set2); 
				numTrees--; 
			} 
		} 
	} 

	printf("Weight of MST is %d\n", MSTweight); 
	return; 
} 

// إنشاء رسم بياني يمتلك العدد المعطى من الرؤوس والأضلاع
struct Graph* createGraph(int V, int E) 
{ 
	Graph* graph = new Graph; 
	graph->V = V; 
	graph->E = E; 
	graph->edge = new Edge[E]; 
	return graph; 
} 

// i دالة مساعدة لإيجاد مجموعة العنصر
// (تستخدم الدالة طريقة ضغط المسار)
int find(struct subset subsets[], int i) 
{ 
	// i إيجاد الجذر وجعل الجذر عقدة أبوية للعنصر
	// (ضغط المسار)
	if (subsets[i].parent != i) 
	subsets[i].parent = 
			find(subsets, subsets[i].parent); 

	return subsets[i].parent; 
} 

// تدمج الدالة بين المجموعتين المعطاتين
// (تستخدم الدالة طريقة التوحيد بالمرتبة)
void Union(struct subset subsets[], int x, int y) 
{ 
	int xroot = find(subsets, x); 
	int yroot = find(subsets, y); 

	// ربط الشجرة ذات المرتبة المشابهة بجذر شجرة ذات مرتبة أعلى (التوحيد بالمرتبة)
	if (subsets[xroot].rank < subsets[yroot].rank) 
		subsets[xroot].parent = yroot; 
	else if (subsets[xroot].rank > subsets[yroot].rank) 
		subsets[yroot].parent = xroot; 

	// إن كانت المراتب متشابهة، تحوّل إحدى الشجرتين إلى جذر
	// وتُزاد مرتبتها بمقدار واحد
	else
	{ 
		subsets[yroot].parent = xroot; 
		subsets[xroot].rank++; 
	} 
} 

// اختبار الدوال السابقة
int main() 
{ 
	/* الرسم البياني الموزون الذي ستعمل عليه الشيفرة
			10 
		0--------1 
		| \	 | 
	6| 5\ |15 
		|	 \ | 
		2--------3 
			4	 */
	int V = 4; // عدد الرؤوس في الرسم البياني
	int E = 5; // عدد الأضلاع في الرسم البياني
	struct Graph* graph = createGraph(V, E); 


	// إضافة الضلع ‎0-1 
	graph->edge[0].src = 0; 
	graph->edge[0].dest = 1; 
	graph->edge[0].weight = 10; 

	// إضافة الضلع ‎0-2 
	graph->edge[1].src = 0; 
	graph->edge[1].dest = 2; 
	graph->edge[1].weight = 6; 

	// إضافة الضلع ‎0-3 
	graph->edge[2].src = 0; 
	graph->edge[2].dest = 3; 
	graph->edge[2].weight = 5; 

	// إضافة الضلع ‎1-3 
	graph->edge[3].src = 1; 
	graph->edge[3].dest = 3; 
	graph->edge[3].weight = 15; 

	// إضافة الضلع ‎2-3 
	graph->edge[4].src = 2; 
	graph->edge[4].dest = 3; 
	graph->edge[4].weight = 4; 

	boruvkaMST(graph); 

	return 0; 
}

• بايثون:

from collections import defaultdict 

# تمثيل الرسم البياني بواسة صنف
class Graph: 

	def __init__(self,vertices): 
		self.V= vertices #No. of vertices 
		self.graph = [] # default dictionary to store graph 
		

	# تضيف الدالة ضلعًا إلى الرسم البياني
	def addEdge(self,u,v,w): 
		self.graph.append([u,v,w]) 

	# i دالة مساعدة لإيجاد مجموعة العنصر
	# (تستخدم الدالة تقنية ضغط المسار)
	def find(self, parent, i): 
		if parent[i] == i: 
			return i 
		return self.find(parent, parent[i]) 

	# تدمج الدالة بين المجموعتين المعطاتين
	# (تستخدم الدمج بالمرتبة) 
	def union(self, parent, rank, x, y): 
		xroot = self.find(parent, x) 
		yroot = self.find(parent, y) 

		# ربط الشجرة ذات المرتبة الأدنى بجذر الشجرة ذات المرتبة الأعلى
		# (الدمج بالمرتبة)
		if rank[xroot] < rank[yroot]: 
			parent[xroot] = yroot 
		elif rank[xroot] > rank[yroot]: 
			parent[yroot] = xroot 
		# إن كان المراتب متساوية، تحوّل إحدى الشجرتين إلى جذر
		# وتُزاد مرتبتها بمقدار واحد
		else : 
			parent[yroot] = xroot 
			rank[xroot] += 1

	# الدالة الرئيسية المسؤولة عن بناء الشجرة الممتدة الصغرى
	# باستخدام خوارزمية بوروفكا
	def boruvkaMST(self): 
		parent = []; rank = []; 

		# تخزن المصفوفة موقع الضلع ذي الوزن الأقل من المجموعة الفرعية
        # [u,v,w] تخزن المصفوفة لكل مكوّن 
		cheapest =[] 

		# في البداية هناك V من الأشجار المختلفة
		# وفي النهاية ستكون هناك شجرة واحدة وهي ستكون الشجرة الممتدة الصغرى 
		numTrees = self.V 
		MSTweight = 0

		# إنشاء V مجموعة فرعية تمتلك عنصرًا واحدًا
		for node in range(self.V): 
			parent.append(node) 
			rank.append(0) 
			cheapest =[-1] * self.V 
	
		# الاستمرار في دمج المكوّنات (أو المجموعات)
		# إلى أن تُدمج جميع المكوّنات في شجرة ممتدة صغرى واحدة

		while numTrees > 1: 

			# التنقل عبر جميع الأضلاع واختيار
            # الضلع ذي الوزن الأقل في كل مكوّن 
			for i in range(len(self.graph)): 

				# إيجاد المكوّنات (أو المجموعات)
				# لزاويتين من الضلع الحالي
				u,v,w = self.graph[i] 
				set1 = self.find(parent, u) 
				set2 = self.find(parent ,v) 

				# إن كان الركنان التابعان للضلع الحالي
				# ينتميان للمجموعة نفسها، سيجري تجاهل الضلع الحالي
				
				
				# وإلا سيجري التحقق من أنّ الضلع الحالي أقرب
			    # من الأضلاع ذات الأوزان الأقل في المجموعتين الأولى والثانية
				if set1 != set2:	 
					
					if cheapest[set1] == -1 or cheapest[set1][2] > w : 
						cheapest[set1] = [u,v,w] 

					if cheapest[set2] == -1 or cheapest[set2][2] > w : 
						cheapest[set2] = [u,v,w] 

					# إضافة الأضلاع ذات الأوزان الأقل المختارة في أعلاه
                    # وإضافتها إلى الشجرة الممتدة الصغرى
			for node in range(self.V): 

				# التحقق من وجود الضلع ذي الوزن الأقل في المجموعة الحالية
				if cheapest[node] != -1: 
					u,v,w = cheapest[node] 
					set1 = self.find(parent, u) 
					set2 = self.find(parent ,v) 

					if set1 != set2 : 
						MSTweight += w 
						self.union(parent, rank, set1, set2) 
						print ("Edge %d-%d with weight %d included in MST" % (u,v,w)) 
						numTrees = numTrees - 1
			
			# إعادة تعيين المصفوفة
			cheapest =[-1] * self.V 

			
		print ("Weight of MST is %d" % MSTweight) 
							

	
g = Graph(4) 
g.addEdge(0, 1, 10) 
g.addEdge(0, 2, 6) 
g.addEdge(0, 3, 5) 
g.addEdge(1, 3, 15) 
g.addEdge(2, 3, 4) 

g.boruvkaMST()

التعقيد الزمني

يبلغ التعقيد الزمني لخوارزمية بوروفكا المقدار O(E log V)‎ وهو نفس التعقيد الزمني لخوارزميتي كروسكال Kruskal وبرم Prim.

انظر أيضًا

• خوارزمية برم: تبدأ هذه الخوارزمية بشجرة ممتدة فارغة، وتعتمد في عملها مجموعتين من الرؤوس. تحتوي المجموعة الأولى على الرؤوس المضافة فعلًا إلى الشجرة الممتدة الصغرى، أما المجموعة الأخرى فتضمّ الرؤوس غير المضافة بعد. وفي كل خطوة، تنظر الخوارزمية في جميع الأضلاع التي تربط المجموعتين، وتختار الضلع ذا الوزن الأقل من بين الأضلاع. وبعد ذلك تحرّك نقطة النهاية الأخرى لهذا الضلع إلى المجموعة التي تحتوي على الشجرة الممتدة الصغرى.
• خوارزمية كروسكال: تعثر خوارزمية كروسكال Kruskal على الشجرة الممتدة الصغرى في الرسم البياني المعطى، بترتيب الأضلاع تصاعديًا ثم اختيار الضلع الأصغر.

مصادر

• صفحة Boruvka’s algorithm في توثيق الخوارزميات في موقع GeeksforGeeks.