реализация графа со списком смежностей java - PullRequest
Новая
       63

реализация графа со списком смежностей java

0 голосов
/ 30 апреля 2020

У меня есть 2D координаты для многих точек, например, точка a = x, y

Я хочу сделать реализацию графа, используя список смежных списков, и соединить определенные точки однонаправленного графа наиболее эффективным способом ( не использует карты или ха sh таблица)

Я попытался создать класс для точек с именем point и сделал массив связанных списков

частных узлов List [] = new LinkedList [numPoints ]

проблема в том, что массив будет целым числом, и я не могу хранить x и y, мне нужно знать x и y

1 Ответ

0 голосов
/ 30 апреля 2020

Вы можете попробовать эту реализацию неориентированного графа 

public class Graph {

    private static final String NEW_LINE = System.lineSeparator();

    private final int vertices;
    private int edges;
    private List<Integer>[] adj;

    public Graph(int v) {
        if (v < 0)
            throw new IllegalArgumentException("Number of vertices must be non-negative");
        this.vertices = v;
        this.edges = 0;
        adj = (List<Integer>[]) new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adj[v] = new LinkedList<Integer>();
        }
    }

    public int getVertices() {
        return vertices;
    }

    public int getEdges() {
        return edges;
    }

    public void addEdge(int v, int w) {
        adj[v].add(w);
        adj[w].add(v);
        edges++;
    }

    public int degree(int v) {
        return adj[v].size();
    }

    public Iterable<Integer> adj(int v) {
        return adj[v];
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        for (int v = 0; v < vertices; v++) {
            builder.append(v + ": ");
            for (int w : adj[v]) {
                builder.append(w + " ");
            }
            builder.append(NEW_LINE);
        }
        return builder.toString();
    }
}
...