Algorithms/graphs

الرسم البياني هو من بنى المعطيات غير الخطية والتي تتضمّن عقدًا nodes وأضلاع edges. تُسمّى العقد في بعض الأحيان بالرؤوس vertices والأضلاع بالخطوط lines أو الأقواس arcs التي تربط بين عقدتين في الرسم البياني.

ويمكن وصف الرسم البياني بصورة أدق بأنّه يحتوي على مجموعة محدّدة من العقد (أو الرؤوس) ومجموعة محدّدة من الأضلاع التي تربط بين عقدتين.

يتضمّن الرسم البياني أعلاه مجموعة الرؤوس V = {0,1,2,3,4}‎ ومجموعة الأضلاع E = {01, 12, 23, 34, 04, 14, 13}‎.

يجدر التنبيه إلى أن مجموعة الحواف مرتّبة وذلك لأنّ الزوج (u, v) يختلف عن الزوج (v, u) في حال استخدام الرسم البياني الموجّه directed graph (أو ما يعرف اختصارًا بـ di-graph). يشير الزوج (u, v) إلى أنّ هناك حافة من الرأس u إلى الرأس v، ويمكن للحافة أن تتضمّن الوزن/القيمة/الكلفة.

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

تمثيل الرسوم البيانية

هناك طريقتان شائعتان لتمثيل الرسوم البيانية:

1. مصفوفة المجاورة Adjacency Matrix.
2. قائمة المجاورة Adjacency List.

وهناك طرق أخرى لتمثيل الرسوم البيانية مثل مصفوفة الوقوع Incidence Matrix أو قائمة الوقوع Incidence List. يعتمد اختيار طريقة التمثيل على الحالة التي يجري التعامل معها، وعلى العمليات المراد إجراؤها وسهولة الاستخدام.

مصفوفة المجاورة

مصفوفة المجاورة هي مصفوفة ثنائية الأبعاد حجمها V x V وتمثل V عدد الرؤوس في الرسم البياني. ولو فرضنا أنّ المصفوفة ثنائية الأبعاد تحمل الاسم adj فإنّ الموقع adj[i][j] = 1 يشير إلى أنّ هناك ضلعًا يربط الرأس i بالرأس j. تكون مصفوفات المجاورة التي تمثّل رسومًا بيانية غير موجّهةٍ متناظرةً دائمًا. تستخدم مصفوفات المجاورة كذلك في تمثيل الرسوم البيانية الموزونة، فلو كان الموقع adj[i][j] = w فإنّ هذا يعني أن هناك ضلعًا يربط الرأس i بالرأس j ولهذا الضلع الوزن w.

مصفوفة المجاورة للمثال أعلاه هي:

مميزات هذه الطريقة:

1. سهولة التنفيذ والمتابعة.
2. يبلغ التعقيد الزمني لعملية حذف ضلع من الأضلاع O(1)‎.
3. يمكن لعمليات الاستعلام عن وجود ضلع يربط الرأس u بالرأس v أن تكون فعّالة وأن تنفّذ في O(1)‎ من الوقت.

عيوب هذه الطريقة:

1. تستهلك الكثير من المساحة O(V^2)‎، وحتى لو تضمّن الرسم البياني القليل من الرؤوس (أي أن عدد الأضلاع قليل) فإنّ هذه الطريقة تستهلك المساحة ذاتها.
2. يبلغ التعقيد الزمني لعملية إضافة رأس إلى الرسم البياني O(V^2)‎.

أمثلة

يعرض المثال التالي طريقة تنفيذ مصفوفة المجاورة في لغة بايثون:

class Graph:
    def __init__(self,numvertex):
        self.adjMatrix = [[-1]*numvertex for x in range(numvertex)]
        self.numvertex = numvertex
        self.vertices = {}
        self.verticeslist =[0]*numvertex

    def set_vertex(self,vtx,id):
        if 0<=vtx<=self.numvertex:
            self.vertices[id] = vtx
            self.verticeslist[vtx] = id

    def set_edge(self,frm,to,cost=0):
        frm = self.vertices[frm]
        to = self.vertices[to]
        self.adjMatrix[frm][to] = cost
        # لا تضف هذا السطر إن كنت تستخدم الرسوم البيانية الموجّهة
        self.adjMatrix[to][frm] = cost

    def get_vertex(self):
        return self.verticeslist

    def get_edges(self):
        edges=[]
        for i in range (self.numvertex):
            for j in range (self.numvertex):
                if (self.adjMatrix[i][j]!=-1):
                    edges.append((self.verticeslist[i],self.verticeslist[j],self.adjMatrix[i][j]))
        return edges
        
    def get_matrix(self):
        return self.adjMatrix

G =Graph(6)
G.set_vertex(0,'a')
G.set_vertex(1,'b')
G.set_vertex(2,'c')
G.set_vertex(3,'d')
G.set_vertex(4,'e')
G.set_vertex(5,'f')
G.set_edge('a','e',10)
G.set_edge('a','c',20)
G.set_edge('c','b',30)
G.set_edge('b','e',40)
G.set_edge('e','d',50)
G.set_edge('f','e',60)
print("Vertices of Graph")
print(G.get_vertex())
print("Edges of Graph")
print(G.get_edges())
print("Adjacency Matrix of Graph")
print(G.get_matrix())

قائمة المجاورة

تستخدم هذه الطريقة مصفوفة من القوائم، ويكون حجم المصفوفة مساويًا لعدد الرؤوس في الرسم البياني. ولو فرضنا أنّ المصفوفة تحمل الاسم array[]‎ فإنّ العنصر array[i]‎ يمثّل قائمة الرؤوس المجاورة للرأس i. يمكن استخدام طريقة التمثيل هذه مع الرسوم البيانية الموزونة، إذ يمكن تمثيل أوزان الأضلاع بواسطة قوائم من الأزواج.

يعرض الشكل التالي طريقة تمثيل الرسم البياني أعلاه باستخدام قائمة المجاورة:

أمثلة

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

يجدر التنبيه إلى أنّ طرق التنفيذ أدناه تستخدم المصفوفات الديناميكية (المتجهات vector في C++‎ و ArrayList في جافا) عوضًا عن القوائم المترابطة لتمثيل قوائم المجاورة.

• C++‎:

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

// دالة مساعدة لإضافة ضلع إلى رسم بياني غير موجّه
void addEdge(vector<int> adj[], int u, int v) 
{ 
	adj[u].push_back(v); 
	adj[v].push_back(u); 
} 

// دالة مساعدة لطباعة قائمة المجاورة التي تمثّل الرسم البياني
void printGraph(vector<int> adj[], int V) 
{ 
	for (int v = 0; v < V; ++v) 
	{ 
		cout << "\n Adjacency list of vertex "
			<< v << "\n head "; 
		for (auto x : adj[v]) 
		cout << "-> " << x; 
		printf("\n"); 
	} 
} 

// اختبار الدوال السابقة
int main() 
{ 
	int V = 5; 
	vector<int> adj[V]; 
	addEdge(adj, 0, 1); 
	addEdge(adj, 0, 4); 
	addEdge(adj, 1, 2); 
	addEdge(adj, 1, 3); 
	addEdge(adj, 1, 4); 
	addEdge(adj, 2, 3); 
	addEdge(adj, 3, 4); 
	printGraph(adj, V); 
	return 0; 
}

• بايثون:

# يستخدم هذا الصنف لتمثيل قائمة المجاورة الخاصّة بعقدة معينة
class AdjNode: 
	def __init__(self, data): 
		self.vertex = data 
		self.next = None


# يمثل هذا الصنف رسمًا بيانياً. 
# الرسم البياني هو قائمة تتضمن قوائم المجاورة.
# عدد الرؤوس سيكون هو حجم المصفوفة.

class Graph: 
	def __init__(self, vertices): 
		self.V = vertices 
		self.graph = [None] * self.V 

	# دالة لإضافة ضلع إلى الرسم البياني غير الموجّه
	def add_edge(self, src, dest): 
		# إضافة العقدة إلى العقدة المصدرية
		node = AdjNode(dest) 
		node.next = self.graph[src] 
		self.graph[src] = node 

		# إضافة العقدة المصدرية إلى الهدف الذي هو رسم بياني غير موجّه
		node = AdjNode(src) 
		node.next = self.graph[dest] 
		self.graph[dest] = node 

	# دالة لطباعة الرسم البياني
	def print_graph(self): 
		for i in range(self.V): 
			print("Adjacency list of vertex {}\n head".format(i), end="") 
			temp = self.graph[i] 
			while temp: 
				print(" -> {}".format(temp.vertex), end="") 
				temp = temp.next
			print(" \n") 


# اختبار الشيفرة السابقة
if __name__ == "__main__": 
	V = 5
	graph = Graph(V) 
	graph.add_edge(0, 1) 
	graph.add_edge(0, 4) 
	graph.add_edge(1, 2) 
	graph.add_edge(1, 3) 
	graph.add_edge(1, 4) 
	graph.add_edge(2, 3) 
	graph.add_edge(3, 4) 

	graph.print_graph()

• جافا

import java.util.LinkedList; 

public class GFG 
{ 
	// صنف معرّف من قبل المستخدم لتمثيل الرسم البياني
    // الرسم البياني هو مصفوفة تتضمن قوائم المجاورة
    // عدد الرؤوس في الرسم البياني سيكون هو حجم المصفوفة
	static class Graph 
	{ 
		int V; 
		LinkedList<Integer> adjListArray[]; 
		
		// دالة بانية
		Graph(int V) 
		{ 
			this.V = V; 
			
			// تعريف حجم المصفوفة ليكون مساويًا عدد الرؤوس
			adjListArray = new LinkedList[V]; 
			
            // إنشاء قائمة جديدة لكل رأس
            // وذلك ليكون بالإمكان تخزين العقد المتجاورة
			for(int i = 0; i < V ; i++){ 
				adjListArray[i] = new LinkedList<>(); 
			} 
		} 
	} 
	
	// تضيف الدالة ضلعًا إلى الرسم البياني غير الموجّه
	static void addEdge(Graph graph, int src, int dest) 
	{ 
		// إضافة الضلع من المصدر إلى الهدف
		graph.adjListArray[src].add(dest); 
		
		// لما كان الرسم البياني غير موجّه، نضيف ضلعًا من الهدف إلى المصدر أيضًا
		graph.adjListArray[dest].add(src); 
	} 
	
	// دالة مساعدة لطباعة قائمة المجاورة التي تمثل الرسم البياني
	static void printGraph(Graph graph) 
	{	 
		for(int v = 0; v < graph.V; v++) 
		{ 
			System.out.println("Adjacency list of vertex "+ v); 
			System.out.print("head"); 
			for(Integer pCrawl: graph.adjListArray[v]){ 
				System.out.print(" -> "+pCrawl); 
			} 
			System.out.println("\n"); 
		} 
	} 
	
	// اختبار الدوال السابقة
	public static void main(String args[]) 
	{ 
		// إنشاء الرسم البياني في الشكل أعلاه
		int V = 5; 
		Graph graph = new Graph(V); 
		addEdge(graph, 0, 1); 
		addEdge(graph, 0, 4); 
		addEdge(graph, 1, 2); 
		addEdge(graph, 1, 3); 
		addEdge(graph, 1, 4); 
		addEdge(graph, 2, 3); 
		addEdge(graph, 3, 4); 
	
		// طباعة قائمة المجاورة التي تمثل الرسم البياني أعلاه
		printGraph(graph); 
	} 
}

مميزات هذه الطريقة:

1. تمتاز طريقة التمثيل هذه بتوفير المساحة O(|V|+|E|)‎. وفي أسوأ الاحتمالات يمكن أن يكون هناك C(V, 2)‎ من الأضلاع في الرسم البياني وبهذا تكون المساحة المستهلكة O(V^2)‎.
2. إضافة الرؤوس إلى الرسم البياني أكثر سهولة.

عيوب هذه الطريقة:

عمليات الاستعلام عن وجود ضلع يربط الرأس u بالرأس v غير فعّالة وتنفّذ في O(V)‎ من الوقت.

مصادر

• صفحة Graph Data Structure and Algorithms في توثيق بنى المعطيات في موقع GeeksforGeeks.
• صفحة Graph and its representations في توثيق بنى المعطيات في موقع GeeksforGeeks.