توضح هذه المقالة طريقة تنفيذ خوارزمية اجتياز العرض الأول المستندة إلى Java للرسوم البيانية في شكل أمثلة، والطرق المحددة هي كما يلي:
استخدم مصفوفة الجوار لتخزين طريقة الرسم البياني:
1. حدد عدد رؤوس وحواف الرسم البياني
2. يتم تخزين معلومات قمة الإدخال في قمة الصفيف أحادية البعد
3. تهيئة مصفوفة الجوار؛
4. أدخل كل حافة على حدة وقم بتخزينها في قوس المصفوفة المجاورة.
أدخل الأرقام التسلسلية i وj للرأسين المتصلين بالحافة؛
اضبط قيمة العنصر للصف i والعمود j لمصفوفة الجوار على 1؛
اضبط قيمة العنصر للصف j والعمود i لمصفوفة الجوار على 1؛
تنفيذ اجتياز العرض الأول:
1. تهيئة قائمة الانتظار س
2. قم بزيارة vertex v; تمت إضافة vertex v إلى قائمة الانتظار Q;
3.بينما (قائمة الانتظار Q ليست فارغة)
v=تم وضع العنصر الرئيسي في قائمة الانتظار Q في قائمة الانتظار؛
w = النقطة المجاورة الأولى للقمة v
بينما (ث موجود)
إذا لم تتم زيارة w، قم بزيارة vertex w;
w=النقطة المجاورة التالية للقمة v
رمز التنفيذ هو كما يلي:
package com.teradata.lsw.sort;import java.util.ArrayList;import java.util.LinkedList;import java.util.List;import java.util.Queue;public class BFS {// معلومات عقدة التخزين كائن خاص[] القمم؛// مصفوفة معلومات حافة التخزين Private int[][] arcs;// عدد الحواف Private int vexnum;// سجل ما إذا كانت العقدة i قد تمت زيارتها تمت زيارة منطقية خاصة[]؛// قم بإنشاء قائمة مرتبطة مؤقتة لتخزين العقد التي تم اجتيازها public List<Object> temp = new ArrayList<Object>();/*** @param args* * @author TD_LSW*/public static void main(String[] args) {// TODO طريقة الإنشاء التلقائي stubBFS g = new BFS(8);Character[] vertices = { 'A'، 'B'، 'C'، 'D'، 'E'، 'F'، 'G'، 'H' };g.addVertex(vertices);g.addEdge(0, 1);g .addEdge(0, 2);g.addEdge(1, 3);g.addEdge(1, 4);g.addEdge(3, 5);g.addEdge(4, 5);g.addEdge(2, 6);g.addEdge(2, 7);System.out.println("اجتياز العرض الأول للرسم البياني:");g.bfs();}//العرض- تنفيذ الاجتياز الأول Private void bfs() {// TODO Auto-generated way stubfor (int i = 0; i < vexnum; i++) {visited[i] = false;}Queue<Integer> q = new LinkedList<Integer>();for (int i = 0; i < vexnum; i++) {if (!visited[i]) {visited[i] = true;visit(i) );q.add(i);while (!q.isEmpty()) {int j = (Integer) q.remove().intValue();// احكم أنه إذا اكتملت جميع عمليات الاجتياز، فلن تكون هناك حاجة للتكرار if (temp.size() == vexnum) {q.removeAll(q);return;}for ( int k = this .firstAdjVex(j); = 0 k = this.nextAdjVex(j, k)) {if (!visited[k]) {q.add(k);visited[k] = true;visit(k);}}}}}}// ابحث عن العقدة التالية public int firstAdjVex(int i) {for (int j = 0; j < vexnum ; j++) {if (arcs[i][j] > 0)return j;}return -1;}public int nextAdjVex(int i, int k) {for (int j = k + 1; j < vexnum; j++) {if (arcs[i][j] > 0)return j;}return -1;}// تهيئة حواف الرسم البياني public void addEdge(int i, int j) {// / TODO طريقة الإنشاء التلقائي stubif (i == j)return;arcs[i][j] = 1;arcs[j][i] = 1;}// تهيئة عقد الرسم البياني public void addVertex(Object[] object) {// TODO طريقة الإنشاء التلقائي stubthis.vertices = object;}// تهيئة الرسم البياني public BFS(int n) {// TODO المنشئ تلقائيًا stubvexnum = n ;vertices = new Object[n];arcs = new int[n][n];visited = new boolean[n];for (int i = 0; i < vexnum; i++) {for (int j = 0; j < vexnum; j++) {arcs[i][j] = 0;}}} زيارة باطلة خاصة (int i) {// TODO طريقة الإنشاء التلقائي stubtemp .add(vertices[i]);System.out.print(vertices[i] + " ");}}