В этой статье описывается метод реализации основанного на Java алгоритма обхода в ширину для графов в виде примеров. Конкретные методы следующие:
Используйте матрицу смежности для хранения метода графа:
1. Определить количество вершин и ребер графа
2. Входная информация о вершинах сохраняется в одномерном массиве вершин.
3. Инициализировать матрицу смежности;
4. Введите каждое ребро по очереди и сохраните его в дуге матрицы смежности.
Введите порядковые номера i и j двух вершин, прикрепленных к ребру;
Установить значение элемента i-й строки и j-го столбца матрицы смежности равным 1;
Установить значение элемента j-й строки и i-го столбца матрицы смежности равным 1;
Реализация обхода в ширину:
1. Инициализировать очередь Q
2. Посещение вершины v; вершина посещения v добавлена в очередь Q;
3.пока (очередь Q не пуста)
v=Головной элемент очереди Q исключен из очереди;
w = первая смежная точка вершины v
пока (w существует)
Если вершина w не была посещена, вершина посещения w помещается в очередь Q;
w=следующая соседняя точка вершины v
Код реализации следующий:
пакет com.teradata.lsw.sort;импорт java.util.ArrayList;импорт java.util.LinkedList;импорт java.util.List;импорт java.util.Queue;публичный класс BFS {//Информация об узле хранения частный объект[] vertices;//Хранение массива информации о ребрах Private int[][] arcs;//Количество ребер Private int vexnum;// Запишите, был ли посещен i-й узел. Private boolean[] visit;//Создаем временный связанный список для хранения пройденных узлов. Private 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();}//Breadth- первая реализация обхода Private void bfs() {// TODO Автоматически сгенерированная заглушка метода (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 = (Целое число) q.remove().intValue(); //Считаем, что если все обходы завершены, нет необходимости выполнять цикл if (temp.size() == vexnum) {q.removeAll(q);return;}for ( int k = this .firstAdjVex(j); k >= 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;}//Инициализируем ребра графа Private void addEdge(int i, int j) {/ / TODO Автоматически сгенерированный метод stubif (i == j)return;arcs[i][j] = 1;arcs[j][i] = 1;}// Инициализировать узлы графа Private 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;}}}private void visit(int i) {// TODO Автоматически созданный метод stubtemp .add(vertices[i]);System.out.print(vertices[i] + " ");}}