Algorithms/src/main/java/algorithms/graph/Graph.java - develop - javapractice/JavaPractice

Algorithms/src/main/java/algorithms/graph/Graph.java
116 строк4 KB
Zexa91x0
Algorithms - Graph
07 май 2021, 23:14
07 май 2021, 23:145d81911
package algorithms.graph;

import java.util.LinkedList;

public class Graph {

    private int vertexCount;
    private int edgeCount = 0;
    private LinkedList<Integer>[] adjList;

    /**
     *
     * Конструктор
     * @param vertexCount количество вершин графа
     */
    public Graph(int vertexCount) {
        if (vertexCount <= 0) throw new IllegalArgumentException("Количество вершин не может быть меньше одной");

        this.vertexCount = vertexCount;

        adjList = new LinkedList[vertexCount];
        for (int i = 0; i < adjList.length; i++) {
            adjList[i] = new LinkedList<>();
        }
    }

    /**
     * Получить общее количество вершин графа
     */
    public int getVertexCount() {
        return vertexCount;
    }

    /**
     * Получить общее количество ребер графа
     */
    public int getEdgeCount() {
        return edgeCount;
    }

    /**
     * Получить клон ребра для вершины (не ссылку)
     * Нужен именно клон, потому что если вернуть ссылку то можно будет внести снаружи изменения в объект // todo - проверить можно ли вносить изменения снаружи
     * @param vertex - вершина
     * @return клон ребра
     */
    public LinkedList<Integer> getEdgesForVertex(int vertex) {

        return (LinkedList<Integer>) adjList[vertex].clone();
    }

    /**
     * Создать ребро.
     * Ребро - это новое отношение между двумя вершинами.
     */
    public void addEdge(int v1, int v2) {
        if (v1 < 0 || v2 < 0 || v1 >= vertexCount || v2 >= vertexCount) {
            throw new IllegalArgumentException("указана несуществующая вершина");
        }
        this.edgeCount++;
        adjList[v1].add(v2);
        adjList[v2].add(v1);

    }


    public static void main(String[] args) {
        Graph graph = new Graph(10);

        graph.addEdge(1, 2);
        graph.addEdge(0, 4);
        graph.addEdge(2, 0);
        graph.addEdge(1, 4);
        graph.addEdge(3, 4);
        graph.addEdge(7, 8);
        graph.addEdge(3, 5);
        graph.addEdge(5, 6);
        graph.addEdge(6, 9);
        graph.addEdge(0, 7);
        graph.addEdge(7, 9);

        System.out.println("Vertex (вершин): " + graph.getVertexCount());
        System.out.println("Edge (ребер) : " + graph.getEdgeCount());

/*        DepthFirstPath depthFirstPath = new DepthFirstPath(graph, 1);
        System.out.println("Start 1, path to 3 : " + depthFirstPath.pathTo(3));
        System.out.println("Start 1, path to 0 : " + depthFirstPath.pathTo(0));
        System.out.println("Start 1, path to 2 : " + depthFirstPath.pathTo(2));
        System.out.println("Start 1, path to 8 : " + depthFirstPath.pathTo(8));

        System.out.println("____________________________");*/


        BreadthFirstPath breadthFirstPath = new BreadthFirstPath(graph, 0);

        for (int i = 0; i < graph.getVertexCount(); i++) {
            System.out.println("Start 0, End " + i + ": " + breadthFirstPath.pathTo(i));
        }
    }

/*        public boolean breadthSearch (graph, start, end){
        int [] queue;

        quere.push(start);
        while (quere.length > 0) {
            const current = queue.shift ();
            if (graph[current].includes(end)){
                return true;
            } else{
                queue = [... quere, ... graph[current]]
            }
        }

        return false;
    }*/
}