Algorithms/Kahn

يمتلك الرسم البياني الموجّه رأسًا واحدًا على الأقل لتكون له درجة دخول (عدد الأضلع الداخلة إلى الرأس) تساوي 0 ودرجة خروج واحدة على الأقل تساوي 0.

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

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

يمكن تقسيم عمل خوارزمية كان Kahn للترتيب الطوبولوجي إلى الخطوات التالية:

1. حسب عدد الأضلاع الداخلة لكل رأس موجود في الرسم البياني الموجّهة وتهيئة تعداد العقد المزورة ليحمل القيمة 0.
2. اختيار جميع الرؤوس التي تمتلك درجة دخول تساوي الصفر وإضافتها إلى الرتل (عملية إدخال Enqueue).
3. حذف الرأس من الرتل (عملية إخراج Dequeue)، ثم تنفيذ ما يلي:
   1. زيادة تعداد العقد المزورة بمقدار 1.
   2. إنقاص عدد الأضلع الداخلة بمقدار 1 لكل العقد المجاورة.
   3. إن وصل عدد الأضلع الداخلة لعقدة مجاورة إلى المقدار 0، تُضاف تلك العقدة إلى الرتل.
4. تكرار الخطوة 3 إلى أن يخلو الرتل من العناصر.
5. إن كان تعداد العقد المزورة غير مساوٍ لعدد العقد في الرسم البياني فلا يمكن حينئذٍ إجراء الترتيب الطوبولوجي عليه.

إيجاد عدد الأضلع الداخلة لكل عقدة

هناك طريقتان لحساب عدد الأضلع الداخلية لكل رأس:

1- التنقل عبر عناصر مصفوفة الأضلاع وزيادة قيمة التعداد للعقدة الهدف بمقدار 1.

for each node in Nodes
    indegree[node] = 0;
for each edge(src,dest) in Edges
    indegree[dest]++

يبلغ التعقيد الزمني لهذه الطريقة المقدار O(V+E)‎.

2- التنقل عبر القائمة لكل عقدة ثم زيادة عدد الأضلاع الداخلة لجميع العقد المتّصلة بها بمقدار 1.

ستنّفذ حلقة for التكرارية الخارجية V مرة وستنّفذ الحلقة الداخلية E مرة؛ لذا يكون التعقيد الزمني لهذه الطريقة O(V+E)‎.

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

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

• C++‎:

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

// صنف لتمثيل الرسم البياني
class Graph 
{ 
	int V; // عدد الرؤوس

	// مؤشر إلى المصفوفة الحاوية على قائمة المجاورة
	list<int> *adj; 

public: 
	Graph(int V); // إنشاء الرسم البياني

	// تضيف الدالة ضلعًا إلى الرسم البياني 
	void addEdge(int u, int v); 

	// تطبع الدالة الترتيب الطوبولوجي للرسم البياني
	void topologicalSort(); 
}; 

Graph::Graph(int V) 
{ 
	this->V = V; 
	adj = new list<int>[V]; 
} 

void Graph::addEdge(int u, int v) 
{ 
	adj[u].push_back(v); 
} 

// الدالة المسؤولة عن إجراء الترتيب الطوبولوجي
void Graph::topologicalSort() 
{ 
	// إنشاء متجه لتخزين عدد الأضلاع الداخلة لجميع الرؤوس.
	// تهيئة قيمة الأضلاع الداخلة لتكون 0
	vector<int> in_degree(V, 0); 

	// التنقل عبر قوائم المجاورة لتعبئة قيم عدد الأضلاع الداخلة لجميع الرؤوس
	// O(V+E) التعقيد الزمني لهذه الخطوة هو
	for (int u=0; u<V; u++) 
	{ 
		list<int>::iterator itr; 
		for (itr = adj[u].begin(); itr != adj[u].end(); itr++) 
			in_degree[*itr]++; 
	} 

	// إنشاء رتل وإدراج الرؤوس فيه مع تعيين القيمة 0 لعدد الأضلاع الداخلة
	queue<int> q; 
	for (int i = 0; i < V; i++) 
		if (in_degree[i] == 0) 
			q.push(i); 

	// تهيئة عدد الرؤوس المزورة
	int cnt = 0; 

	// إنشاء متجه لتخزين النتائج (الترتيب الطوبولوجي للرؤوس)
	vector <int> top_order; 

	// إخراج الرؤوس من الرتل واحدًا تلو الآخر
	// وإضافة الرؤوس المجاورة إن كان عدد الأضلاع الداخلة للعقد المجاورة هو 0
	while (!q.empty()) 
	{ 
		// استخراج مقدمة الرتل (أو إزالة العنصر من الرتل) 
		// وإضافته إلى الترتيب الطوبولوجي
		int u = q.front(); 
		q.pop(); 
		top_order.push_back(u); 

		// المرور على جميع العقد المجاورة للعقد المزالة
		// وإنقاص قيمة الأضلاع الداخلة لها بمقدار 1
		list<int>::iterator itr; 
		for (itr = adj[u].begin(); itr != adj[u].end(); itr++) 

			// نضيف العقدة إلى الرتل إن أصبحت قيمة الأضلاع الداخلة صفرًا
			if (--in_degree[*itr] == 0) 
				q.push(*itr); 

		cnt++; 
	} 

	// التحقق من وجود دورة في الرسم البياني
	if (cnt != V) 
	{ 
		cout << "There exists a cycle in the graph\n"; 
		return; 
	} 

	// طباعة نتيجة الترتيب الطوبولوجي
	for (int i=0; i<top_order.size(); i++) 
		cout << top_order[i] << " "; 
	cout << endl; 
} 

// اختبار الدوال السابقة
int main() 
{ 
	// إنشاء الرسم البياني أعلاه 
	Graph g(6); 
	g.addEdge(5, 2); 
	g.addEdge(5, 0); 
	g.addEdge(4, 0); 
	g.addEdge(4, 1); 
	g.addEdge(2, 3); 
	g.addEdge(3, 1); 

	cout << "Following is a Topological Sort of\n"; 
	g.topologicalSort(); 

	return 0; 
}

• بايثون:

from collections import defaultdict 

# صنف لتمثيل الرسم البياني 
class Graph: 
	def __init__(self,vertices): 
		self.graph = defaultdict(list) # قاموس يحتوي على قائمة المجاورة
		self.V = vertices # عدد الرؤوس

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


	# الدالة المسؤولة عن إجراء الترتيب الطوبولوجي 
	def topologicalSort(self): 
		
		# إنشاء متجه لتخزين عدد الأضلاع الداخلة لجميع الرؤوس.
		# تهيئة قيمة الأضلاع الداخلة لتكون 0 
		in_degree = [0]*(self.V) 
		
		# المرور على قوائم المجاورة لتعبئة قيم الأضلع الداخلة للرؤوس.
		# O(V+E) يبلغ التعقيد الزمني لهذه العملية المقدار
		for i in self.graph: 
			for j in self.graph[i]: 
				in_degree[j] += 1

		# إنشاء رتل وإضافة جميع الرؤوس التي يكون عدد الأضلع الداخل إليها صفرًا
		queue = [] 
		for i in range(self.V): 
			if in_degree[i] == 0: 
				queue.append(i) 

		# تهيئة تعداد الرؤوس المزورة
		cnt = 0

		# إنشاء متّجه لتخزين النتائج (نتائج الترتيب الطوبولوجي)
		top_order = [] 

		# إزالة الرؤوس من الرتل واحدًا تلو الآخر
		# ثم إضافة الرؤوس المتجاورة إن كان عدد الأضلع الداخلة للرؤوس المجاورة صفرًا
		while queue: 

			# استخراج مقدّمة الرتل (أو إزالة العنصر) وإضافته إلى الترتيب الطوبولوجي
			u = queue.pop(0) 
			top_order.append(u) 

			
			# المرور على جميع العقد المجاورة للعقدة المزالة
			# وإنقاص عدد الأضلع الداخلة إليها بمقدار 1
			
			for i in self.graph[u]: 
				in_degree[i] -= 1
				# إن أصبح عدد الأضلع الداخلة صفرًا، تضاف العقدة إلى الرتل
				if in_degree[i] == 0: 
					queue.append(i) 

			cnt += 1

		# التحقق من وجود دورة في الرسم البياني
		if cnt != self.V: 
			print "There exists a cycle in the graph"
		else : 
			# طباعة الترتيب الطوبولوجي
			print top_order 


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

print "Following is a Topological Sort of the given graph"
g.topologicalSort()

• جافا:

import java.util.*; 

// صنف لتمثيل الرسم البياني
class Graph 
{ 
	int V;//  عدد الرؤوس 
	
	// مؤشر إلى المصفوفة الحاوية على قائمة المجاورة 
	List <Integer> adj[]; 
	public Graph(int V)// إنشاء الرسم البياني 
	{ 
		this.V = V; 
		adj = new ArrayList[V]; 
		for(int i = 0; i < V; i++) 
			adj[i]=new ArrayList<Integer>(); 
	} 
	
	// تضيف الدالة ضلعًا إلى الرسم البياني
	public void addEdge(int u,int v) 
	{ 
		adj[u].add(v); 
	} 
	// تطبع الدالة الترتيب الطوبولوجي للرسم البياني	 
	public void topologicalSort() 
	{ 
		// إنشاء مصفوفة لتخزين عدد الأضلاع الداخلة لجميع الرؤوس. 
		// تهيئة قيمة الأضلاع الداخلة لتكون 0 
		int indegree[] = new int[V]; 
		
		// التنقل عبر قوائم المجاورة لتعبئة قيم عدد الأضلاع الداخلة لجميع الرؤوس 
		// O(V+E) التعقيد الزمني لهذه الخطوة هو		 
		for(int i = 0; i < V; i++) 
		{ 
			ArrayList<Integer> temp = (ArrayList<Integer>) adj[i]; 
			for(int node : temp) 
			{ 
				indegree[node]++; 
			} 
		} 
		
		// إنشاء رتل وإدراج الرؤوس فيه مع تعيين القيمة 0 لعدد الأضلاع الداخلة 
		Queue<Integer> q = new LinkedList<Integer>(); 
		for(int i = 0;i < V; i++) 
		{ 
			if(indegree[i]==0) 
				q.add(i); 
		} 
		
		// تهيئة عدد الرؤوس المزورة
		int cnt = 0; 
		
		// إنشاء متجه لتخزين النتائج (الترتيب الطوبولوجي للرؤوس) 
		Vector <Integer> topOrder=new Vector<Integer>(); 
		while(!q.isEmpty()) 
		{ 
			// استخراج مقدمة الرتل (أو إزالة العنصر من الرتل) 
			// وإضافته إلى الترتيب الطوبولوجي 
			int u=q.poll(); 
			topOrder.add(u); 
			
			// المرور على جميع العقد المجاورة للعقد المزالة 
			// وإنقاص قيمة الأضلاع الداخلة لها بمقدار 1 
			for(int node : adj[u]) 
			{ 
				// نضيف العقدة إلى الرتل إن أصبحت قيمة الأضلاع الداخلة صفرًا 
				if(--indegree[node] == 0) 
					q.add(node); 
			} 
			cnt++; 
		} 
		
		// التحقق من وجود دورة في الرسم البياني		 
		if(cnt != V) 
		{ 
			System.out.println("There exists a cycle in the graph"); 
			return ; 
		} 
		
		// طباعة الترتيب الطوبولجي			 
		for(int i : topOrder) 
		{ 
			System.out.print(i+" "); 
		} 
	} 
} 
// اختبار الدوال السابقة 
class Main 
{ 
	public static void main(String args[]) 
	{ 
		// إنشاء الرسم أعلاه 
		Graph g=new Graph(6); 
		g.addEdge(5, 2); 
		g.addEdge(5, 0); 
		g.addEdge(4, 0); 
		g.addEdge(4, 1); 
		g.addEdge(2, 3); 
		g.addEdge(3, 1); 
		System.out.println("Following is a Topological Sort"); 
		g.topologicalSort(); 

	} 
}

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

يبلغ التعقيد الزمني الكلي لهذه الخوارزمية المقدار O(V+E)‎.

مصادر

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