Реализация графа задач

Question

Я был бы благодарен, если бы кто-то мог помочь мне с этой Задачей.

Задача: Реализует класс Graph (направленный и взвешенный), без использования стандартных Graph-классов java.

Не имеет значения, используя adjacencyList или adjMatrix

Мой код

import java.util.*;

public class Graph {

    static class Edge {

        char vA;
        char vB;
        double weight;

        Edge(char a, char b, double weight) {
            vA = a;
            vB = b;
            this.weight = weight;
        }

        void setWeight(double w) {
            weight = w;
        }

        double getWeight() {
            return weight;
        }
    }

    private Map<Character, LinkedList<Character>> edges = new HashMap<>();

    void addNode(char node) {
        if (!edges.containsKey(node)) {
            edges.put(node, new LinkedList<Character>());
        }
    }

    public void addEdge(char a, char b, double weight) {

        Edge e = new Edge(a, b, weight);
        a = e.vA;
        b = e.vB;
        e.setWeight(weight);

        edges.get(a).add(b);

    }

    void printNodes() {
        System.out.println(edges.keySet());

    }

    void printEdges() {
        System.out.println(edges.values());

    }

    void dfs() {
        //TODO
    }

    void dijkstra(char startNodeID){
    }


    public static void main(String... args) {
        Graph graph = new Graph();
        graph.addNode('A');
        graph.addNode('B');
        graph.addNode('C');
        graph.addNode('D');
        graph.addNode('E');
        graph.addEdge('A', 'B', 2);
        graph.addEdge('A', 'C', 3);
        graph.addEdge('B', 'D', 6);
        graph.addEdge('C', 'D', 8);
        graph.addEdge('C', 'E', 9);

        graph.printEdges();
        graph.printNodes();

    }

}

Вопросы:

Как добавить края в LinkedList внутри hashMap?

Что не так с моим методом addEdges?

Как можно распечатать края?

Answer 1

$ 1: чтобы добавить края - см. Полный пример ниже.

$ 2: вы не сохраняете вес и созданный Edge-объект:

public void addEdge(char a, char b, double weight) {
    Edge e = new Edge(a, b, weight); // 1. creating the Edge
    a = e.vA;            // 2. assigning the 'edge.vA'-value to 'a' ... why?
    b = e.vB;            // 3. same here with 'b'
    e.setWeight(weight); // 4. weight was already set when creating object on line 1
    edges.get(a).add(b); // 5. here you add the node 'b' to the list... what about the weight?
    // 6. now you exit the method without storing the created edge 'e'
}

$ 3: printEdges () работает «отлично» - это печать значений для каждого узла в HashMap. Выход:

[[B, C], [D], [D, E], [], []]

что гласит:

• для 'A' соединенные ребра: [B и C]
• для 'B' соединенные ребра: [D]
• для 'C' соединенные ребра: [D и E]
• для 'D' соединенные ребра: []
• для 'E' соединенные ребра: []

Пример для хранения весов и краев дисплея:

import java.util.*;

public class Graph {

    static class Edge {

        final char vA;
        final char vB;
        final double weight;

        Edge(char a, char b, double weight) {
            this.vA = a;
            this.vB = b;
            this.weight = weight;
        }

        @Override
        // compare if 2 edges are equal
        public boolean equals(Object obj) {
            if (obj instanceof Edge) {
                Edge other = (Edge) obj;
                return this.vA == other.vA && this.vB == other.vB;
            }
            return false;
        }

        @Override
        // string representation of edge
        public String toString() {
            return String.format("[%s -> %s] : %.2f", vA, vB, weight);
        }
    }

    // The edges could be stored directly in an ArrayList, but I assume
    // you'll need to lookup all edges for a give node.
    private Map<Character, ArrayList<Edge>> edges = new HashMap<>();

    void addNode(char node) {
        if (!edges.containsKey(node)) {
            edges.put(node, new ArrayList<Edge>());
        }
    }

    public void addEdge(char a, char b, double weight) {
        Edge edge = new Edge(a, b, weight);
        if (!edges.get(a).contains(edge)) {
            edges.get(a).add(edge);
        } else {
            System.out.printf("Edge [%s -> %s] already exists!%n", edge.vA, edge.vB);
        }
    }

    void printNodes() {
        System.out.printf("%nNODES:%n%s%n", edges.keySet());
    }

    void printEdges() {
        System.out.println("EDGES:");
        edges.forEach((node, edgeList) -> {
            /**
             * Take each pair <key,value> (here <Character, ArrayList<Edge>) from 
             * the HashMap 'edges' as variables (node,edgeList), where
             * node: represents the current node, e.g.: A
             * edgeList: contains all the edges starting from 'node', e.g. [[A,B,2],[A,C,3]]
             */
            System.out.printf("%s:%n", node); // print current node
            edgeList.forEach(edge -> {
                // take each Edge from the current ArrayList<Edge> edgeList as 'edge' and ...
                System.out.printf("  %s%n", edge); // print the edge value using Edge::toString()
            });
        });
    }


    void printEdgesFor() {
        // get all pairs of the HashMap as Entry:
        for (Map.Entry<Character, ArrayList<Edge>> entry : edges.entrySet()) {
            Character node = entry.getKey(); // Entry-key = node
            ArrayList<Edge> edgeList = entry.getValue(); // Entry-value = edgeList
            System.out.printf("%s:%n", node);
            for (Edge edge: edgeList) {
                System.out.printf("  %s%n", edge.toString());
            }
        }
    }

    void printEdgesFor2() {
        // get all keys:
        for (Character node: edges.keySet()) { // get all nodes (key from HashMap 'edges')
            ArrayList<Edge> edgeList = edges.get(node); // get edgeList from HashMap 'edges' using key
            System.out.printf("%s:%n", node);
            for (Edge edge: edgeList) { // with each edge of the current edgeList..
                System.out.printf("  %s%n", edge.toString()); // print
            }
        }
    }
}

Answer 2

Как я могу добавить края в LinkedList внутри hashMap

Если вы хотите, чтобы LinkedList содержал ребра, определите его как LinkedList<Edge> вместо LinkedList<Character>:

 private Map<Character, LinkedList<Edge>> edges = new HashMap<>();

и внесите необходимые изменения, в том числе в addEdge:

edges.get(a).add(e);  //need to add it to b as well ? 

Как можно печатать края?

Переберите карту, получите каждый LinkedList и распечатайте его:

void printNodes() {
    for(char node : edges.keySet()) {
        System.out.println(edges.get(node)); //requires implementing toString in Edge
    }
}

Не лучше ли вам просто хранить все края в наборе, а не Map<Character, LinkedList<Edge>>?