Java - Какая лучшая структура реализации для Graph?
Чтобы исключить фон и границу кнопки, просто сделайте кнопку меньшей, чем растровое изображение.
6 ответов
Мое предложение - хранить вершины в приоритетной очереди. Таким образом, вы сможете иметь очень быстрый доступ к вершине с наивысшей степенью. Что касается того, как реализовать эти вершины, я бы хранил каждую соседнюю вершину в какой-нибудь структуре данных, такой как HashSet или TreeSet, чтобы иметь возможность эффективно удалять вещи. Я бы не представлял ребра явно, это не нужно.
Код, что-то вроде:
class Graph {
PriorityQueue<Vertex> vertexes;
public Graph() {
vertexes = new PriorityQueue<Vertex>(10,new Vertex());
}
public Vertex maxDegreeVertex() {
return vertexes.peek();
}
...
}
class Vertex implements Comparator<Vertex> {
HashSet<Vertex> edges;
public Vertex() {
edges = new HashSet<Vertex>();
}
public compare(Vertex v1, Vertex v2) {
v2.edges.size().compareTo(v1.edges.size());
}
...
}
Надеюсь, это поможет.
.Вы также можете посмотреть на специально разработанные библиотеки, такие как JUNG
Если ваш алгоритм требует просмотра на максимальном уровне, то вам нужна структура данных, упорядоченная по степени, что-то вроде PriorityQueue было бы неплохо.
Тогда вам нужно хранить сам график. Для быстрого удаления я бы порекомендовал что-то вроде структуры Sparse Array. Если вам нужно использовать структуры данных java.util, то HashMap от вершин к списку подключенных вершин предлагает удаление O(1).
Если вы можете использовать сторонние библиотеки, то здесь список ответов, из которых JGraph и JUNG кажутся наиболее популярными.
.Две фундаментальные структуры данных для представления графиков -
adjacency listthe adjacency matrix
см. http://en.wikipedia.org/wiki/Adjacency_list и http://en.wikipedia.org/wiki/Adjacency_matrix.
.
В статьях также обсуждаются "за" и "против" этих двух структур
Исходя из вышеизложенного, ответом будет
Карта со связным списком...
Ваша структура данных может быть такой (варьируется в зависимости от ваших требований)...
Map<?, List<?>>
<Node-name, List-of-nodes-connected-to-it>
В принципе, графики лучше всего реализовывать с помощью HASHING, и вышеприведенная структура данных в этом очень помогает...
Зависит от того, какие еще требования у вас есть. Наивным, простым подходом может быть
class Node
{
List<Node> edges;
int id;
}
-
class Node
{
List<Node> edges;
int id;
}
-
-
-[121212], где у вас будет список всех вершин на графике. Проблема в том, что это может стать непоследовательным; например, вершина A может находиться в списке рёбер вершины B, а вершина B может не находиться в списке вершины A. Чтобы обойти это, можно смоделировать его следующим образом:
class Edge
{
Node incidentA;
Node incidentB;
}
class Node
{
int id;
}
Опять же, у вас будут List и List всех рёбер и узлов в системе. Конечно, анализ этой структуры данных был бы сделан совсем иначе, чем при другом подходе
.