• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

开发技术 开发技术 5小时前 2次浏览
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Graph {

    private Map<Node, Map<Node, Edge>> edgeMap = new HashMap<>();

    private Map<Integer, Node> nodes = new HashMap<>();

    private List<Edge> edges = new ArrayList<>();

    public List<Edge> getEdges() {
        return edges;
    }

    public Map<Integer, Node> getNodes() {
        return nodes;
    }

    /**
     * 如果边不存在,则创建边,同时保留最优边
     *
     * @param from
     * @param to
     * @param weight
     * @return
     */
    private Edge buildEdge(Node from, Node to, int weight) {
        Map<Node, Edge> fromMap = edgeMap.computeIfAbsent(from, k -> new HashMap<>());
        Edge edge = fromMap.get(to);
        // 新边
        if (edge == null) {
            edge = new Edge(from, to, weight);
            fromMap.put(to, edge);
            from.edges.add(edge);
            edges.add(edge);
            from.out++;
            to.in++;
        } else {
            // 留下最优边
            if (edge.weight > weight) {
                edge.weight = weight;
            }
        }
        return edge;
    }

    /**
     * 如果不存在,则创建节点
     *
     * @param index
     * @return
     */
    private Node buildNode(int index) {
        Node node = nodes.get(index);
        if (node == null) {
            node = new Node(index);
            nodes.put(index, node);
        }
        return node;
    }

    /**
     * 添加边
     *
     * @param fromIndex
     * @param toIndex
     * @param weight
     */
    public void addEdge(int fromIndex, int toIndex, int weight) {
        buildEdge(buildNode(fromIndex), buildNode(toIndex), weight);
    }
}

class Edge {
    Node from;
    Node to;
    int weight;

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

class Node {
    int value;
    int in;
    int out;
    List<Edge> edges;

    public Node(int value) {
        this.value = value;
        this.in = 0;
        this.out = 0;
        this.edges = new ArrayList<>();
    }
}

程序员灯塔
转载请注明原文链接:
喜欢 (0)