Мы знаем, что для представления узлов мы можем представлять их с одномерным массивом. Однако для отношений между узлами мы не можем просто представлять их с одномерным массивом. Мы можем представлять их с двумерным массивом, то есть методом представления матрицы.
Мы предполагаем, что A-это двумерный массив, затем элемент AIJ не только отражает взаимосвязь между узлом VI и узлом VJ, но и значение AIJ может представлять размер веса.
Смежный матричный модельный класс
Название класса класса модели смежности матрицы - Amwgraph.java. Он может построить график, представленную матрицей смежности через этот класс, и обеспечивать вставку узлов, вставить ребра и получить первый узел смежности и следующий соседний узел определенного узла.
импортировать java.util.arraylist;
импортировать java.util.linkedlist;
открытый класс amwgraph {
Private Arraylist Vertexlist;
// Ссылка таблицы точек хранения точек
частный int [] [] края;
// адресная матрица, используемая для хранения краев
частные int numofedges;
// количество краев
public amwgraph (int n) {
// Инициализировать матрицу, одномерный массив и количество краев
ряд = new int [n] [n];
vertexlist = new ArrayList (n);
numofedges = 0;
}
// Получить количество узлов
public int getnumofvertex () {
return vertexlist.size ();
}
// Получить количество краев
public int getNumOfedges () {
вернуть числа;
}
// возвращать данные узла I
открытый объект getValueByindex (int i) {
вернуть vertexlist.get (i);
}
// вернуть вес v1 и v2
public int getweay (int v1, int v2) {
вернуть края [v1] [v2];
}
// вставить узел
public void insertvertex (Object Vertex) {
vertexlist.add (vertexlist.size (), vertex);
}
// вставить узел
public void вставка (int v1, int v2, int вес) {
края [v1] [v2] = вес;
numofedges ++;
}
// Удалить узел
public void deleteedge (int v1, int v2) {
края [v1] [v2] = 0;
NumOfedges--;
}
// Получить подписку первого соседнего узла
public int getfirstneighbor (int index) {
for (int j = 0; j <vertexlist.size (); j ++) {
if (edges [index] [j]> 0) {
вернуть J;
}
}
возврат -1;
}
// Получить следующий соседний узел на основе подписки предыдущего соседнего узла
public int getnextneighbor (int v1, int v2) {
for (int j = v2+1; j <vertexlist.size (); j ++) {
if (edges [v1] [j]> 0) {
вернуть J;
}
}
возврат -1;
}
}Давайте посмотрим на код, который реализует матрицу смежности, чтобы представлять плотные графики:
пакет com.datastructure.graph;
////// Dense Graph - использовать матрицу смежности для представления
// открытый класс DenseGraph {
//
// частный int n; // количество узлов
// частный int m; // номер края
// Частный логический режиссер; // это направленный график
// Частный логический [] [] g; // конкретные данные изображения
//
// // конструктор
// public densegraph (int n, boolean направлен) {
// утверждать n> = 0;
// this.n = n;
// this.m = 0; // инициализация не имеет краев
// this.directed = режиссер;
// // g инициализируется в логическую матрицу n*n. Каждый g [i] [j] является ложным, что указывает на то, что нет никаких и краев.
// // false - значение по умолчанию переменной логического типа
// g = new Boolean [n] [n];
//}
//
// public int v () {
// return n;
//} // возвращать количество узлов
//
// public int e () {
// return m;
//} // возвращать количество краев
//
// // Добавить край к графику
// public void addedge (int v, int w) {
//
// утверждение v> = 0 && v <n;
// утверждать w> = 0 && w <n;
//
// if (hasedge (v, w))
// возвращаться;
//
// // Подключение V и W
// g [v] [w] = true;
// if (! направленный)
// g [w] [v] = true;
//
// // количество краев ++
// m ++;
//}
//
// // Проверьте, есть ли ребра от V до W на графике
// boolean hasedge (int v, int w) {
// утверждение v> = 0 && v <n;
// утверждать w> = 0 && w <n;
// вернуть g [v] [w];
//}
//
// // возвращать все соседи вершины на графике
// // Поскольку Java использует справочный механизм, возвращение вектора не принесет никаких дополнительных накладных расходов.
// publicatable <Integer> прил. (int v) {
// утверждение v> = 0 && v <n;
// vector <Integer> adjv = new Vector <Integer> ();
// for (int i = 0; i <n; i ++)
// if (g [v] [i])
// adjv.add (i);
// вернуть прил.;
//}
//}
импортировать java.util.arraylist;
импортировать java.util.list;
// Использовать матрицу смежности для представления плотных графиков
открытый класс DenseGraph {
частный int n;
// количество узлов на рисунке
частный int m;
// количество краев на картинке
Частный логический [] [] g;
// смежная матрица G
Частный логический режиссер;
// это направленный график
Public DenseGraph (int n, Boolean Recrected) {
this.n = n;
// количество узлов на графике инициализации
this.m = 0;
// количество краев на рисунке инициализируется до 0
this.Directed = режиссер;
g = новый логический [n] [n];
// Матрица смежности G инициализируется в двумерную матрицу n*n
// Индекс представляет узел на графике, а значение, хранящееся в G, - это ли узел есть ребра
}
// возвращать количество краев на графике
public int e () {
возврат М;
}
// возвращать количество узлов на графике
public int v () {
возврат n;
}
// Добавить края между двумя узлами, указанными на рисунке
public void addedge (int v, int w) {
if (! hasedge (v, w)) {
// подключить [v] [w]
g [v] [w] = true;
// Неправный график
if (! направленный)
g [w] [v] = true;
// количество сторон на картинке +1
M ++;
}
}
// Определите, есть ли края между двумя узлами
Частный логический хаседж (int v, int w) {
вернуть g [v] [w];
}
// возвращает соседние узлы всех узлов V
публичный итерабильный
// Прилегающий используется для хранения соседнего узла V
Список <integer> radecentl = new ArrayList <> ();
// Найти все узлы, прилегающие к V и добавить их в прилегающий
для (int i = 0; i <n; i ++) {
if (g [v] [i])
radessentl.add (i);
}
вернуть прилегающего;
}
}
Суммировать
Выше приведено все содержание этой статьи о программировании Java для реализации примера кода плотного графика матрицы смежности, и я надеюсь, что это будет полезно для всех. Заинтересованные друзья могут продолжать ссылаться на этот сайт:
Анализ основных понятий и примеров кода дерева структуры данных Java
Java Common Data Strufture Ofters Questions (с ответами)
Принцип алгоритма MultiMode String Principle и код реализации Java
Если есть какие -либо недостатки, пожалуйста, оставьте сообщение, чтобы указать это. Спасибо, друзья, за вашу поддержку на этом сайте!