الكشف عن وجود دورة في الرسم البياني غير الموجه

المجموعة المفككة disjoint-set هي إحدى بنى المعطيات التي تتابع مجموعة من العناصر المقسّمة إلى عدد من المجاميع الفرعية (غير المتداخلة) المفككة.

خوارزمية "وحّد-جد"

تجري خوارزمية وحّد-جِدْ union-find عمليتين مفيدتين على المجموعات المفككة، وهما:

• جد Find: تحدّد هذه العملية ما إذا كان عنصر معيّن موجودًا في المجموعة، ويمكن استخدام هذه العملية لمعرفة ما إذا كان عنصران موجودين في المجموعة الفرعية نفسها.
• وحّد: توّحد هذه العملية مجموعتين فرعيتين في مجموعة فرعية واحدة.

يمكن الاستفادة من المجموعات المفككة وخوارزمية وحّد-جِد في الكشف عن وجود دورة في الرسم البياني، وتفترض هذه الطريقة عدم وجود حلقات ذاتية في الرسم البياني.

يمكن متابعة المجموعات الفرعية باستخدام مصفوفة أحادية الأبعاد (ليكن اسمها parent[]‎.

لنأخذ الرسم البياني التالي كمثال:

تصنع الخوارزمية مجاميع فرعية لكلّ ضلع في الرسم البياني وذلك باستخدام رأسي الضلع، فإن عُثر على أنّ الرأسين موجودان في المجموعة الفرعية نفسها، فإن هذا يعني وجود دورة في الرسم البياني.

الخطوة الأولى هي تهيئة جميع المواقع في المصفوفة الأب لتحمل القيمة ‎-1 (وهذا يعني وجود عنصر واحد في كل مجموعة فرعية).

0   1   2
-1 -1  -1

والآن سنعالج الأضلاع واحدًا تلو الآخر.

الضلع ‎0-1: جد المجاميع الفرعية التي يوجد فيها الرأسان 0 و 1. لمّا كان الرأسان في مجموعتين فرعيتين مختلفتين، فسنأخذ المجموعة الناتجة من اتحاد المجموعتين، وإما أن نجعل العقدة 0 هي العقدة الأم للعقدة 1 أو بالعكس.

الضلع ‎‎1-2: الرأس 1 موجود في المجموعة الفرعية 1 و الرأس 2 موجود في المجموعة الفرعية 2؛ لذا سنوحّدهما.

الضلع ‎0-2: الرأس 0 موجود في المجموعة الفرعية 2 والرأس 2 موجود كذلك في المجموعة الفرعية 2. نستنتج من ذلك أنّ هذا الضلع يشكّل دورة.

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

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

• C++‎:

#include <bits/stdc++.h> 
using namespace std; 

// تمثيل ضلع في الرسم البياني
class Edge 
{ 
	public: 
	int src, dest; 
}; 

// تمثيل الرسم البياني
class Graph 
{ 
	public: 
	// V-> عدد الرؤوس
	// E-> عدد الأضلاع
	int V, E; 

	// يمثل الضلع بهيئة مصفوفة من الأضلاع
	Edge* edge; 
}; 

// تنشئ الدالة رسمًاً بيانيًا يتضمّن الرؤوس والأضلاع المعطاة
Graph* createGraph(int V, int E) 
{ 
	Graph* graph = new Graph(); 
	graph->V = V; 
	graph->E = E; 

	graph->edge = new Edge[graph->E * sizeof(Edge)]; 

	return graph; 
} 

// دالة مساعدة للعثور على المجموعة الفرعية التي ينتمي إليها العنصر المعطى
int find(int parent[], int i) 
{ 
	if (parent[i] == -1) 
		return i; 
	return find(parent, parent[i]); 
} 

// دالة مساعدة لتوحيد مجموعتين فرعيتين
void Union(int parent[], int x, int y) 
{ 
	int xset = find(parent, x); 
	int yset = find(parent, y); 
	if(xset != yset) 
	{ 
		parent[xset] = yset; 
	} 
} 

// الدالة الرئيسية التي تتحقّق ممّأ إذا كان الرسم البياني المعطى
// يحتوي على دورة أو لا
int isCycle( Graph* graph ) 
{ 
	// حجز موقع في الذاكرة لإنشاء مجموعات الرؤوس الفرعية
	int *parent = new int[graph->V * sizeof(int)]; 

	// تهيئة جميع المجموعات الفرعية لتكون مجموعات ذات عنصر واحد
	memset(parent, -1, sizeof(int) * graph->V); 

	// المرور على جميع الأضلع في الرسم البياني، والعثور على المجموعات الفرعية 
	// لكلا الرأسين المكونين لكل ضلع، وإذا عُثر على مجموعتين فرعيتين متشابهتين
	// فإن هذا يعني أن الرسم البياني يحتوي على دورة
	for(int i = 0; i < graph->E; ++i) 
	{ 
		int x = find(parent, graph->edge[i].src); 
		int y = find(parent, graph->edge[i].dest); 

		if (x == y) 
			return 1; 

		Union(parent, x, y); 
	} 
	return 0; 
} 

// اختبار الدوال السابقة
int main() 
{ 
	/* إنشاء الرسم البياني التالي
		0 
		| \ 
		| \ 
		1-----2 */
	int V = 3, E = 3; 
	Graph* graph = createGraph(V, E); 

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

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

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

	if (isCycle(graph)) 
		cout<<"graph contains cycle"; 
	else
		cout<<"graph doesn't contain cycle"; 

	return 0; 
}

• بايثون:

# هناك ضلع واحد لأي رأسين في الرسم البياني، بمعنى أنّ الرأسين 1 و 2 يشكّلان الضلع ‎1-2 أو ‎2-1 وليس كلاهما
from collections import defaultdict 

# يستخدم هذا الصنف لتمثيل الرسم البياني غير الموجّه باستخدام قائمة المجاورة
class Graph: 

	def __init__(self,vertices): 
		self.V= vertices # عدد الرؤوس
		self.graph = defaultdict(list) # القاموس الافتراضي الذي يستخدم لتخزين الرسم البياني


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

	# دالة مساعدة للعثور على المجموعة الفرعية التي ينتمي إليها العنصر المعطى
	def find_parent(self, parent,i): 
		if parent[i] == -1: 
			return i 
		if parent[i]!= -1: 
			return self.find_parent(parent,parent[i]) 

	# دالة مساعدة لتوحيد مجموعتين فرعيتين
	def union(self,parent,x,y): 
		x_set = self.find_parent(parent, x) 
		y_set = self.find_parent(parent, y) 
		parent[x_set] = y_set 



	# الدالة الرئيسية التي تتحقق ممّا إذا كان الرسم البياني المعطى
	# يحتوي على دورة أم لا
	def isCyclic(self): 
		
		# حجز موقع في الذاكرة لإنشاء مجموعة الرؤوس الفرعية
		# وتهيئة جميع المجموعات الفرعية لتكون مجموعات ذات عنصر واحد
		parent = [-1]*(self.V) 


		# المرور على جميع الأضلع في الرسم البياني، والعثور على المجموعات الفرعية 
		# لكلا الرأسين المكونين لكل ضلع، وإذا عُثر على مجموعتين فرعيتين متشابهتين
		# فإن هذا يعني أن الرسم البياني يحتوي على دورة
		for i in self.graph: 
			for j in self.graph[i]: 
				x = self.find_parent(parent, i) 
				y = self.find_parent(parent, j) 
				if x == y: 
					return True
				self.union(parent,x,y) 


# إنشاء الرسم البياني أعلاه
g = Graph(3) 
g.addEdge(0, 1) 
g.addEdge(1, 2) 
g.addEdge(2, 0) 

if g.isCyclic(): 
	print "Graph contains cycle"
else : 
	print "Graph does not contain cycle "

• جافا:

import java.util.*; 
import java.lang.*; 
import java.io.*; 

class Graph 
{ 
	// V-> عدد الرؤوس
	// E-> عدد الأضلاع
	int V, E; 
	Edge edge[]; // مجموعة الأضلاع

	class Edge 
	{ 
		int src, dest; 
	}; 

	// إنشاء رسم بياني يتكون من الرؤوس والأضلاع المعطاة
	Graph(int v,int e) 
	{ 
		V = v; 
		E = e; 
		edge = new Edge[E]; 
		for (int i=0; i<e; ++i) 
			edge[i] = new Edge(); 
	} 

	// دالة مساعدة للعثور على المجموعة الفرعية التي ينتمي إليها العنصر المعطى
	int find(int parent[], int i) 
	{ 
		if (parent[i] == -1) 
			return i; 
		return find(parent, parent[i]); 
	} 

	// دالة مساعدة لتوحيد مجموعتين فرعيتين
	void Union(int parent[], int x, int y) 
	{ 
		int xset = find(parent, x); 
		int yset = find(parent, y); 
		parent[xset] = yset; 
	} 


	// الدالة الرئيسية التي تتحقق من أنّ الرسم البياني المعطى
	// يحتوي على دورة أو لا
	int isCycle( Graph graph) 
	{ 
		// حجز موقع في الذاكرة لإنشاء مجموعة الرؤوس الفرعية
		int parent[] = new int[graph.V]; 

		// تهيئة جميع المجموعات الفرعية لتكون مجموعات ذات عنصر واحد
		for (int i=0; i<graph.V; ++i) 
			parent[i]=-1; 

		
		// المرور على جميع الأضلع في الرسم البياني، والعثور على المجموعات الفرعية 
		// لكلا الرأسين المكونين لكل ضلع، وإذا عُثر على مجموعتين فرعيتين متشابهتين
		// فإن هذا يعني أن الرسم البياني يحتوي على دورة
		for (int i = 0; i < graph.E; ++i) 
		{ 
			int x = graph.find(parent, graph.edge[i].src); 
			int y = graph.find(parent, graph.edge[i].dest); 

			if (x == y) 
				return 1; 

			graph.Union(parent, x, y); 
		} 
		return 0; 
	} 

	// اختبار الدوال السابقة
	public static void main (String[] args) 
	{ 
		/* إنشاء الرسم البياني التالي
		0 
		| \ 
		| \ 
		1-----2 */
		int V = 3, E = 3; 
		Graph graph = new Graph(V, E); 

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

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

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

		if (graph.isCycle(graph)==1) 
			System.out.println( "graph contains cycle" ); 
		else
			System.out.println( "graph doesn't contain cycle" ); 
	} 
}

مصادر

• صفحة Disjoint Set (Or Union-Find)‎ في توثيق الخوارزميات في موقع GeeksforGeeks.