تعريف الرسم البياني
يتكون الرسم البياني من مجموعة محدودة من القمم ومجموعة من الحواف بين الرؤوس. عادة ما يتم تمثيله على النحو التالي: g (v ، e) ، حيث يمثل g رسمًا بيانيًا ، V هو مجموعة من الرؤوس في الرسم البياني G ، و E هي مجموعة الحواف في الرسم البياني G.
الرسم البياني الموجه
الحافة الموجهة: إذا كانت الحافة من Vertex VI إلى VJ لها اتجاه ، فإن هذه الحافة تسمى الحافة الموجهة ، والتي تصبح أيضًا قوسًا (قوسًا). ويمثله من قبل <vi ، vj>. السادس يسمى ذيل القوس ويسمى VJ رأس القوس.
مخطط مضطربة
حافة غير موجهة: إذا كانت الحافة بين الرؤوس VI إلى VJ ليس لها اتجاه ، فإن هذه الحافة تسمى حافة غير موجهة (EDGE) ، ويمثلها زوج غير مرتبة (VI ، VJ).
صورة بسيطة
الرسم البياني البسيط: في بنية الرسم البياني ، إذا لم يكن هناك قمة على حافةها الخاصة ولا تظهر نفس الحافة مرارًا وتكرارًا ، فهذه الصورة تسمى مخططًا بسيطًا.
فئة الصورة
يشير إلى قمة
تتمثل الخطوة الأولى في إنشاء فئة رسم بياني في إنشاء فئة قمة للحفظ رؤوسًا وحوافًا. تعمل هذه الفئة مثل فئة العقدة من القوائم المرتبطة وأشجار البحث الثنائية. تحتوي فئة Vertex على عضوين بيانات: أحدهما لتحديد قمة الرأس والآخر للإشارة إلى ما إذا كان قد تم الوصول إليه. تم تسمية العلامة وتم زيارتها على التوالي.
نسخة الكود كما يلي:
وظيفة Vertex (label) {
this.label = label ؛
}
نقوم بحفظ جميع القمم في صفيف ، وفي فئة الرسم البياني ، يمكننا الرجوع إليها من خلال موقفهم في الصفيف
يشير إلى الحافة
يتم تخزين المعلومات الفعلية للرسم البياني على "الحافة" لأنها تصف بنية الرسم البياني. يمكن أن تحتوي عقدة الأصل على شجرة ثنائية فقط على عقدان طفلان ، لكن بنية الرسم البياني أكثر مرونة. يمكن أن يكون للرأس حافة واحدة أو حواف متعددة متصلة به.
سوف نستخدم طريقة تمثيل حواف الرسم البياني لتصبح جدولًا مجاورًا أو صفيف جدول مجاور. سيتم تخزين مجموعة مكونة من قائمة من الرؤوس المجاورة من الرؤوس
بناء رسم بياني
حدد فئة الرسم البياني التالي:
نسخة الكود كما يلي:
وظيفة الرسم البياني (V) {
this.Vertices = V ؛ // رؤوس إلى النقطة العالية
this.edges = 0 ؛
this.adj = [] ؛
لـ (var i = 0 ؛ i <this.vertices ؛ ++ i) {
this.adj [i] = [] ؛
this.adj [i] .push ('') ؛
}
this.addedge = تمت إضافة ؛
this.toString = toString ؛
}
يسجل هذه الفئة عدد الحواف التي يمثلها الرسم البياني ويستخدم طولًا وعدد رؤوس الرسم البياني لتسجيل عدد القمم.
نسخة الكود كما يلي:
الوظيفة المضافة () {
this.adj [v] .push (w) ؛
this.adj [w] .push (v) ؛
this.edges ++ ؛
}
هنا نستخدم حلقة لإضافة جهاز فرعي لكل عنصر في الصفيف لتخزين جميع القمم المجاورة وتهيئة جميع العناصر إلى سلاسل فارغة.
اجتياز الصورة
عمق أولوية اجتياز
يشار إلى DepthFirstSearch ، والمعروف أيضًا باسم DepThfirstSearch ، باسم DFS لفترة قصيرة.
على سبيل المثال ، تبحث عن مفتاح في غرفة ، بغض النظر عن الغرفة التي تبدأ بها ، يمكنك البحث عن زوايا الغرفة ، والطاولات الجانبية ، وطاولات السرير ، والأسرة ، وخزائن ، وخزائن تلفزيونية ، وما إلى ذلك. بعد البحث في جميع الأدراج وخزانات التخزين ، ثم البحث عن الغرفة المجاورة.
البحث عن أولوية العمق:
يعني البحث الأول في العمق الوصول إلى قمة لم تتم زيارتها ، ووضع علامة على ذلك ، ثم الوصول إلى رؤوس أخرى لم تتم زيارتها في جدول القمة الأولي بشكل متكرر.
أضف صفيفًا إلى فئة الرسم البياني:
نسخة الكود كما يلي:
this.marked = [] ؛ // احفظ الرؤوس التي تمت زيارتها
لـ (var i = 0 ؛ i <this.vertices ؛ ++ i) {
this.marked [i] = false ؛ // تهيئة إلى خطأ
}
وظيفة البحث العمق الأول:
نسخة الكود كما يلي:
وظيفة dfs (v) {
this.marked [v] = true ؛
// إذا لم يكن البيان ضروريًا هنا
if (this.adj [v]! = غير محدد) {
print ("Vertex المزينة:" + V) ؛
لكل (var w في this.adj [v]) {
if (! this.marked [w]) {
this.dfs (w) ؛
}
}
}
}
بحث العرض الأول
يعد البحث الأول الواسع (BFS) طريقة بحث أعمى ، وغرض التوسع بشكل منهجي وفحص جميع العقد في الرسم البياني للعثور على النتائج. بمعنى آخر ، لا يأخذ في الاعتبار الموقع المحتمل للنتيجة ، ويبحث في الصورة بأكملها جيدًا حتى يتم العثور على النتيجة.
يبدأ البحث في العرض الأول بالبرامة الأولى ، وحاول الوصول إلى قمة الرأس أقرب ما يكون ممكنًا ، كما هو موضح في الشكل التالي:
مبدأ العمل هو:
1. ابحث أولاً عن رؤوس غير مقدمة مجاورة للقمة الحالية وأضفها إلى قائمة الرؤوس التي تمت زيارتها وقائمة الانتظار ؛
2. ثم أخرج قمة الرأس التالية من الرسم البياني وأضفها إلى قائمة Vertice التي تمت زيارتها
3. وأخيراً أضف جميع القمم غير المورقة المجاورة لـ V إلى قائمة الانتظار
ما يلي هو تعريف وظيفة البحث الأولى:
نسخة الكود كما يلي:
وظيفة bfs (s) {
Queue var = [] ؛
this.marked = true ؛
queue.push (s) ؛ // أضف إلى نهاية قائمة الانتظار
بينما (queue.length> 0) {
var v = queue.shift () ؛ // إزالة من قائد الفريق
if (v == undefined) {
print ("Vertex المزينة:" + V) ؛
}
لكل (var w في this.adj [v]) {
if (! this.marked [w]) {
this.edgeto [w] = v ؛
this.marked [w] = true ؛
queue.push (w) ؛
}
}
}
}
أقصر مسار
عند إجراء عملية بحث متسعة ، يتم العثور على أقصر مسار من قمة واحدة إلى قمة أخرى متصلة تلقائيًا
تحديد المسار
للعثور على أقصر مسار ، نحتاج إلى تعديل خوارزمية البحث في العرض الأول لتسجيل المسار من قمة إلى أخرى. نحتاج إلى صفيف لحفظ جميع حواف القمة التالية من قمة واحدة. نسمي هذه المصفوفة edgeto
نسخة الكود كما يلي:
this.edgeto = [] ؛ // أضف هذا السطر إلى فئة الرسم البياني
// وظيفة BFS
وظيفة bfs (s) {
Queue var = [] ؛
this.marked = true ؛
queue.push (s) ؛ // أضف إلى نهاية قائمة الانتظار
بينما (queue.length> 0) {
var v = queue.shift () ؛ // إزالة من قائد الفريق
if (v == undefined) {
print ("Vertex المزينة:" + V) ؛
}
لكل (var w في this.adj [v]) {
if (! this.marked [w]) {
this.edgeto [w] = v ؛
this.marked [w] = true ؛
queue.push (w) ؛
}
}
}
}
خوارزمية الفرز الطوبولوجي
فرز الطوبولوجي يقوم بفرز جميع رؤوس الرسم البياني الموجه ، بحيث توجه الحواف الموجهة من الرأس الأمامي إلى الرأس الخلفي.
خوارزمية الفرز الطوبولوجية تشبه BFS. الفرق هو أن خوارزمية الفرز الطوبولوجي لا تخرج الرؤوس التي تم الوصول إليها على الفور ، ولكنها بدلاً من ذلك تصل إلى جميع القمم المجاورة في الجدول المجاور للقرار الحالي. حتى يتم استنفاد هذه القائمة ، لن يتم دفع قمة الرأس الحالية إلى المكدس.
يتم تقسيم خوارزمية الفرز الطوبولوجي إلى وظيفتين. الوظيفة الأولى هي TopSort () ، والتي يتم استخدامها لتعيين عملية الفرز واستدعاء وظيفة المساعد TopSorthelper () ، ثم عرض قائمة الرأس المرتبة.
يتم العمل الرئيسي لخوارزمية فرز الطوبولوجيا في الوظيفة العودية TopSorthelper () ، والتي تمثل قمة القمة الحالية كما تم الوصول إليها ، ثم تصل بشكل متكرر كل قمة في جدول قمة الرأس المجاورة الحالي ، مما يمثل هذه القمم كما تم الوصول إليها. أخيرًا ، ادفع قمة الرأس الحالية إلى المكدس.
نسخة الكود كما يلي:
// topsort () وظيفة
وظيفة TopSort () {
var stack = [] ؛
var زار = [] ؛
لـ (var i = 0 ؛ i <this.vertices ؛ i ++) {
زار [i] = خطأ ؛
}
لـ (var i = 0 ؛ i <this.vertices ؛ i ++) {
إذا (تمت زيارته [i] == false) {
this.topsorthelper (i ، زار ، stack) ؛
}
}
لـ (var i = 0 ؛ i <stack.length ؛ i ++) {
if (stack [i]! = undefined && stack [i]! = false) {
print (this.vertexlist [stack [i]]) ؛
}
}
}
// Topsorthelper () وظيفة
وظيفة TopSorthelper (V ، زيارة ، مكدس) {
زار [v] = صحيح ؛
لكل (var w في this.adj [v]) {
if (! زار [w]) {
this.topsorthelper (زار [w] ، زار ، stack) ؛
}
}
stack.push (v) ؛
}