كيفية تنفيذ بنية بيانات الرسم البياني في Golang

غالبًا ما تأتي المشاكل المتعلقة بالرسم البياني في طريقك في صناعة البرمجيات. سواء في المقابلات الفنية أو عند إنشاء التطبيقات التي تستخدم الرسوم البيانية.

الرسوم البيانية هي هياكل بيانات أساسية تستخدم في تطبيقات مختلفة ، بدءًا من الشبكات الاجتماعية وأنظمة النقل إلى محركات التوصية وتحليل الشبكة.

ما هو الرسم البياني وكيف يمكنك تنفيذ الرسوم البيانية في Go؟

ما هو الرسم البياني؟

الرسم البياني هو بنية بيانات غير خطية تمثل مجموعة من العقد (أو الرؤوس) والوصلات بينها (الحواف). تُستخدم الرسوم البيانية على نطاق واسع في تطبيقات البرامج التي تتعامل بكثافة مع الاتصالات مثل شبكات الكمبيوتر والشبكات الاجتماعية وغير ذلك.

الرسم البياني هو واحد من هياكل البيانات التي يجب أن تعرفها كمبرمج. توفر الرسوم البيانية طريقة قوية ومرنة لنمذجة مختلف سيناريوهات العالم الحقيقي وتحليلها ، وهذا يجعلها بنية بيانات أساسية وجوهرية في علوم الكمبيوتر.

تعتمد مجموعة متنوعة من خوارزميات حل المشكلات المستخدمة في عالم البرمجيات على الرسوم البيانية. يمكنك التعمق أكثر في الرسوم البيانية في هذا دليل لهيكل بيانات الرسم البياني.

تنفيذ رسم بياني في جولانج

في معظم الأوقات لتنفيذ بنية البيانات بنفسك ، تحتاج إلى التنفيذ البرمجة الشيئية (OOP) المفاهيم ، ولكن تنفيذ OOP في Go يختلف تمامًا عما لديك في لغات أخرى مثل Java و C ++.

يستخدم Go الهياكل والأنواع والواجهات لتنفيذ مفاهيم OOP ، وهذا كل ما تحتاجه لتنفيذ بنية بيانات الرسم البياني وأساليبها.

يتكون الرسم البياني من عقد (أو رؤوس) وحواف. العقدة هي كيان أو عنصر في الرسم البياني. مثال على العقدة هو جهاز موجود على شبكة أو شخص على شبكة اجتماعية. بينما الحافة هي اتصال أو علاقة بين عقدتين.

لتنفيذ رسم بياني في Go ، تحتاج أولاً إلى تحديد بنية العقدة التي ستكون ملكيتها جيرانها. الجيران للعقدة هم العقد الأخرى المتصلة مباشرة بالعقدة.

في الرسوم البيانية الموجهة ، تحتوي الحواف على اتجاهات لذلك فقط العقد التي تشير إليها عقدة معينة تعتبر جيرانها. بينما في الرسوم البيانية غير الموجهة ، فإن جميع العقد التي تشترك في الحافة مع العقدة هي جيرانها.

يوضح الكود التالي كيف أن ملف العقدة تبدو بنية:

type Node struct {
 Neighbors []*Node
}

في هذه المقالة ، سيكون التركيز على رسم بياني غير موجه. ومع ذلك ، لتوفير وضوح أفضل ، إليك ما هو ملف العقدة قد يبدو هيكل الرسم البياني الموجه كما يلي:

type Node struct {
 OutNeighbors []*Node // outgoing edges
 InNeighbors []*Node // incoming edges
}

مع هذا التعريف ، فإن الجيران شريحة سوف تخزن العقد التي توجد لها حواف صادرة من العقدة الحالية ، و في الجيران شريحة سوف تخزن العقد التي توجد منها حواف واردة للعقدة الحالية.

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

يوضح الكود التالي ملف رسم بياني هيكل:

type Graph struct {
 nodes map[int]*Node
}

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

أنت بحاجة إلى وظيفة لتعمل كمُنشئ لتهيئة رسم بياني جديد. سيخصص هذا ذاكرة لقائمة التقارب ويسمح لك بإضافة عقد إلى الرسم البياني. الكود أدناه هو تعريف منشئ لـ رسم بياني فصل:

funcNewGraph() *Graph {
return &Graph{
 nodes: make(map[int]*Node),
 }
}

يمكنك الآن تحديد طرق لإجراء أنواع مختلفة من العمليات على الرسم البياني. هناك العديد من العمليات التي يمكنك إجراؤها على الرسم البياني ، من إضافة العقد إلى إنشاء الحواف بين العقد ، والبحث عن العقد ، والمزيد.

في هذه المقالة ، سوف تستكشف وظائف إضافة العقد والحواف إلى الرسوم البيانية ، وكذلك إزالتها. الرسوم التوضيحية التالية هي تطبيقات وظائف تنفيذ هذه العمليات.

إضافة عقدة إلى الرسم البياني

لإضافة عقدة جديدة إلى الرسم البياني ، تحتاج إلى وظيفة الإدراج التي تبدو كالتالي:

func(g *Graph)AddNode(nodeID int) {
if _, exists := g.nodes[nodeID]; !exists {
 newNode := &Node{
 Neighbors: []*Node{},
 }
 g.nodes[nodeID] = newNode
 fmt.Println("New node added to graph")
 } else {
 fmt.Println("Node already exists!")
 }
}

ال AddNode تضيف الوظيفة عقدة جديدة على الرسم البياني مع تمرير المعرّف إليها كمعامل. تتحقق الوظيفة مما إذا كانت العقدة بنفس المعرف موجودة بالفعل قبل إضافتها إلى الرسم البياني.

إضافة حافة إلى الرسم البياني

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

فيما يلي وظيفة إضافة حافة بين عقدتين على الرسم البياني:

func(g *Graph)AddEdge(nodeID1, nodeID2 int) {
 node1 := g.nodes[nodeID1]
 node2 := g.nodes[nodeID2]
 node1.Neighbors = append(node1.Neighbors, node2)
 node2.Neighbors = append(node2.Neighbors, node1)
}

بسيط جدا! إن إضافة الحواف في رسم بياني غير موجه هي ببساطة عملية جعل كلتا العقدتين متجاورتين لبعضهما البعض. تحصل الوظيفة على كلا العقدتين من خلال المعرفات التي تم تمريرها إليها وتقوم بإلحاق كل منهما بالعقد الأخرى الجيران شريحة.

إزالة حافة من الرسم البياني

لإزالة عقدة من الرسم البياني ، تحتاج إلى إزالتها من جميع قوائم جيرانها لضمان عدم وجود تناقضات في البيانات.

عملية إزالة العقدة من جميع جيرانها هي نفس عملية إزالة الحواف (أو كسر اتصالات) بين العقد ، ومن ثم عليك تحديد وظيفة إزالة الحواف أولاً قبل تحديد واحد إزالة العقد.

أدناه هو تنفيذ إزالة وظيفة:

func(g *Graph)removeEdge(node, neighbor *Node) {
 index := -1
for i, n := range node.Neighbors {
if n == neighbor {
 index = i
break
 }
 }
if index != -1 {
 node.Neighbors = 
append(node.Neighbors[:index], node.Neighbors[index+1:]...)
 }
}
func(g *Graph)RemoveEdge(node, neighbor *Node) {
 g.removeEdge(node, neighbor)
 g.removeEdge(neighbor, node)
 fmt.Println("Edge successfully removed")
}

ال إزالة تقبل الوظيفة عقدتين كمعلمات وتبحث عن فهرس العقدة (الجار) الثانية في قائمة جيران العقدة الرئيسية. ثم يمضي قدما لإزالة الجار من العقدة. الجيران باستخدام تقنية تسمى تقطيع الشريحة.

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

في هذه الحالة ، لديك رسم بياني غير موجه ، وبالتالي فإن حوافه ثنائية الاتجاه. لهذا السبب كان عليك الاتصال بـ إزالة مرتين في الاساس RemoveEdge وظيفة لإزالة الجار من قائمة العقدة والعكس صحيح.

إزالة عقدة من الرسم البياني

بمجرد أن تتمكن من إزالة الحواف ، يمكنك أيضًا إزالة العقد. فيما يلي وظيفة إزالة العقد من الرسم البياني:

func(g *Graph)RemoveNode(nodeID int) {
 node, exists := g.nodes[nodeID]
if !exists {
 fmt.Println("Node doesn't exist")
return
 }
for _, neighbor := range node.Neighbors {
 g.RemoveEdge(node, neighbor)
 }
delete(g.nodes, nodeID)
 fmt.Println("Node deleted successfully")
}

تقبل الوظيفة معرف العقدة التي تريد إزالتها. يتحقق مما إذا كانت العقدة موجودة قبل الاستمرار في إزالة جميع حوافها. ثم تحذف العقدة من الرسم البياني باستخدام Go يحمل في ثناياه عوامل يمسح وظيفة.

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

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

قم ببناء برنامج محسن باستخدام هياكل البيانات الصحيحة

يوفر Go بالفعل نظامًا أساسيًا رائعًا لتطوير تطبيقات برمجية فعالة ، ولكن عندما تهمل جيدًا ممارسات التطوير ، يمكن أن يتسبب ذلك في مشاكل مختلفة لبنية تطبيقك وأدائه.

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