任务图实现

Question

如果有人能帮助我完成这项任务，我将不胜感激。

任务：实现 class 图（有向和加权），而不使用 java.

的标准图-classes

使用 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();

    }

}

问题：

如何将边添加到 hashMap 中的 LinkedList？

我的方法 addEdges 有什么问题？

如何打印边缘？

Answer 1

How Can I add Edges to the LinkedList inside the 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 ?

How is it possible to print the Edges?

迭代地图，获取每个 LinkedList 并打印它：

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

将所有 Edge 简单地存储在 Set 中而不是 Map<Character, LinkedList<Edge>> 中是否可以更好地满足您的需求？

Answer 2

$1：添加边 - 请参阅下面的完整示例。

$2：您没有存储重量和创建的 'Edge'-object:

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() 有效 'fine' - 它正在打印 HashMap 中每个节点的值。输出是：

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

上面写着：

for 'A' the connected edges are: [B and C]

for 'B' the connected edges is : [D]

for 'C' the connected edges are: [D and E]

for 'D' the connected edges are: []

for 'E' the connected edges are: []

存储权重和显示边的示例：

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
            }
        }
    }
}

任务图实现

Task graph implement

java

graph

adjacency-list

adjacency-matrix