Pytanie Java - Jaka jest najlepsza struktura implementacji Graph?


Wykres jest bardzo duży, ale nieukierunkowany. Krawędzie są nieważone.

W mojej implementacji muszę znaleźć wierzchołek z maksymalnym stopniem i wykonać usuwanie na obu wierzchołkach i krawędziach.

Połączona lista? ArrayList? Mapa?

Który z nich jest lepszy dla mojej implementacji?


11
2017-12-22 09:09


pochodzenie




Odpowiedzi:


Moją sugestią byłoby przechowywanie wierzchołków w kolejce priorytetowej. W ten sposób możesz uzyskać bardzo szybki dostęp do wierzchołka z najwyższym stopniem. Jeśli chodzi o sposób implementowania wierzchołków, przechowałbym każdy sąsiedni wierzchołek w jakiejś ustawionej strukturze danych, takiej jak HashSet lub TreeSet, aby móc efektywnie usuwać elementy. Nie reprezentowałbym wyraźnie krawędzi, nie jest potrzebny.

Kod, coś w rodzaju:

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());
  }

  ...

}

Mam nadzieję że to pomoże.


6
2017-12-22 09:36



Dzięki za kod. Nigdy wcześniej nie używał PriorityQueue, czy łatwo jest usunąć? - user236691
Tak, to naprawdę proste. Jeśli chcesz usunąć element o najwyższym priorytecie w tym samym czasie podczas pobierania, po prostu użyj metody odpytywania. Usuwanie elementów ogólnie odbywa się za pomocą metody usuwania. Po prostu google "priorytet kolejki java" dla dokumentacji. - svenningsson
Mam to, dzieki! Jeszcze jedno pytanie, jaki jest cel wprowadzenia porównania metod w klasie wierzchołków? - user236691
Och, to chyba trochę hack, ale ułatwia implementację metody porównania. Chciałem zasilić kolejkę priorytetową moim własnym niestandardowym komparatorem. Aby ją wdrożyć, potrzebowałem dostępu do liczby sąsiadów wierzchołka. Ponieważ nie chciałem zaśmiecać fragmentu kodu takimi rzeczami, po prostu umieściłem metodę compare w klasie Vertex. Ale lepiej byłoby, gdyby implementacja była gdzie indziej, być może jako anonimowa klasa tworzona podczas tworzenia PriorityQueue. Mam nadzieję że to pomoże. Powodzenia! - svenningsson
Wierzchołek powinien zaimplementować Porównywalny zamiast Komparatora, aby zdefiniować porządek naturalny. W ten sposób nie trzeba określać komparatora. - Christoffer Hammarström


Dwie podstawowe struktury danych do reprezentowania wykresów to

  • adjacency list 

  • the adjacency matrix

widzieć http://en.wikipedia.org/wiki/Adjacency_list i http://en.wikipedia.org/wiki/Adjacency_matrix.
Artykuły omawiają także zalety i wady tych dwóch struktur.


14
2017-12-22 09:22



Wow, proszę. - G-Wiz
Moja książka o strukturach danych sugeruje mapę przylegania, która jest listą sąsiedztwa z zastąpieniem listy drugorzędnej mapą. Zmniejsza to spodziewany czas działania niektórych z jego metod. (Struktury danych i algorytmy w Javie - Goodrich, Tamassia i Goldwasser) - Fr4nc3sc0NL


Z powyższej sugestii odpowiedź byłaby

Mapa z LinkedList ...

Twoja struktura danych może być podobna (zależnie od wymagań) ...

Map<?, List<?>>
<Node-name, List-of-nodes-connected-to-it>

Zasadniczo najlepiej zaimplementować wykresy za pomocą funkcji HASHING, a powyższa struktura danych bardzo pomaga.


3
2017-12-22 09:16



To nie jest prawda, mieszanie nie zawsze jest najlepsze, czasami najlepsza jest Macierz Przyległości. To zależy od algorytmu. - Nick Fortescue
Ponadto, nie wszystkie mapy używają Hashowania, na przykład TreeMap nie. - Nick Fortescue
dziękuje za komentarz :-) - Rites
Co rozumiesz przez "zależy od algorytmu"? Czy możesz podać dowolny przykład? - user236691
Dowolny algorytm, który znajduje się na etapie krytycznym, jeśli sąsiadują ze sobą dwa wierzchołki. Jest to O (1) w macierzy i O (min (A, B)) na liście, gdzie A i B są stopniem wierzchołka - Nick Fortescue


Jeśli twój algorytm wymaga sprawdzenia na maksymalnym stopniu, to potrzebujesz struktury danych uporządkowanej według stopnia, coś takiego jak PriorityQueue byłoby dobre.

Następnie musisz przechowywać sam wykres. Do szybkiego usunięcia polecam coś w rodzaju struktury Sparse Array. Jeśli musisz użyć struktur danych java.util, a HashMap od wierzchołków do listy połączonych wierzchołków oferuje usuwanie O (1).

Jeśli możesz korzystać z bibliotek zewnętrznych, to są lista odpowiedzi tutaj z których JGraph i JUNG wydają się najbardziej popularne.


1
2017-12-22 09:22





Implementacja wykresu zależy od tego, co zamierzasz z nim zrobić. Jednak w większości przypadków pomocna jest implementacja listy zależnej.

W Javie możesz to zrobić za pomocą mapy <>. Oto ogólna lista dotycząca dopasowania Graph.Java wdrożenie na moim blogu.


1
2017-10-09 07:22





Możesz również rzucić okiem na specjalnie zaprojektowane biblioteki, takie jak JUNG


0
2017-12-22 09:21





Zależy od twoich innych wymagań. Może być naiwne, proste podejście

class Node
{
  List<Node> edges;
  int id;
}

gdzie masz listę wszystkich węzłów na wykresie. Problem polega na tym, że może to być niespójne; na przykład węzeł A może znajdować się na liście krawędzi węzła B, ale węzeł B może nie znajdować się na liście węzła A. Aby obejść ten problem, można go modelować jako taki:

class Edge
{
  Node incidentA;
  Node incidentB;
}

class Node
{
  int id;
}

Ponownie, będziesz miał listę i listę wszystkich krawędzi i węzłów w systemie. Oczywiście analiza tej struktury danych odbywałaby się w zupełnie inny sposób niż w innym podejściu.


0
2017-12-22 09:24





    public class Graph {
    private Set<Vertex>vertices;
    private Set<Edge>edges;
    private Map<Vertex,List<Edge>>adj;
    // Getter setter



    public Graph(Set<Vertex> vertices, Set<Edge> edges, Map<Vertex, List<Edge>> adj) {
        super();
        this.vertices = vertices;
        this.edges = edges;
        this.adj = adj;
    }
}

// Vertex class
public class Vertex {
    private String name;

    public Vertex(String name) {
        super();
        this.name = name;
    }


}

// Edge class 

public class Edge {
    private Vertex from;
    private Vertex to;
    private int weight;

    public Edge(Vertex from, Vertex to,int weight) {
        super();
        this.from = from;
        this.to = to;
        this.weight = weight;
    }


}

// Driver class 

import java.util.HashSet;
import java.util.Set;

public class Test {
    public static void  main(String[]args) {
        Graph gr = new Graph();
        Vertex a = new Vertex("a");
        Vertex b = new Vertex("b");
        Vertex c = new Vertex("c");
        Vertex d = new Vertex("d");
        Vertex e = new Vertex("e");
        Vertex f = new Vertex("f");
        Vertex g = new Vertex("g");


        Set<Vertex>vertices = gr.getVertices();
        if(vertices == null){
            vertices  = new HashSet<>();
            vertices.add(a);
            vertices.add(b);
            vertices.add(c);
            vertices.add(d);
            vertices.add(e);
            vertices.add(f);
            vertices.add(g);
        }

        Edge ae = new Edge(a, e, 3);        
        Edge ac = new Edge(a, c, 1);
        Edge cf = new Edge(c, f, 9);
        Edge cd = new Edge(c, d, 4);
        Edge eb = new Edge(e, b, 2);
        Edge bd = new Edge(b, d, 5);
        Edge df = new Edge(d, f, 7);

    Set<Edge>edges = gr.getEdges();
    if(edges == null){
        edges = new HashSet<Edge>();
        edges.add(ae);
        edges.add(ac);
        edges.add(cf);
        edges.add(cd);
        edges.add(eb);
        edges.add(bd);
        edges.add(bd);
    }
        gr.setVertices(vertices);
        gr.setEdges(edges);

    }

}

0
2018-05-01 19:12