图

画一个图

定义数据结构

这里使用的是邻接表

图

public class ListGraph<V, E> implements Graph<V, E> {

    // 存点  记录所有的点
    private Map<V, Vertex<V, E>> vertices = new HashMap<>();
    // 存边   记录所有的边
    private Set<Edge<V, E>> edges = new HashSet<>();

点

    private static class Vertex<V, E> {
        V value;
        // 入度边  记录每一个进入该点的边
        Set<Edge<V, E>> inEdges = new HashSet<>();
        // 出度边  记录每一个以该点出去的边
        Set<Edge<V, E>> outEdges = new HashSet<>();

        public Vertex(V value) {
            this.value = value;
        }

        @Override
        public boolean equals(Object obj) {
            return Objects.equals(value, ((Vertex<V, E>) obj).value);
        }

        @Override
        public int hashCode() {
            return value == null ? 0 : value.hashCode();
        }
    }

边

    private static class Edge<V, E> {

        public Edge(Vertex<V, E> from, Vertex<V, E> to) {
            this.from = from;
            this.to = to;
        }
        // 初始点 
        Vertex<V, E> from;
        // 终点
        Vertex<V, E> to;
        // 权重
        E weight;

        @Override
        public boolean equals(Object obj) {
            Edge<V, E> edge = (Edge<V, E>) obj;
            return Objects.equals(from, edge.from) && Objects.equals(to, edge.to);
        }

        @Override
        public int hashCode() {
            return from.hashCode() * 31 + to.hashCode();
        }
    }

图的类结构

定义方法

addVertex 添加点

    public void addVertex(V v) {
    // 如果点的集合中存在该点，就返回
        if (vertices.containsKey(v)) return;
        // 没有就添加
        vertices.put(v, new Vertex<V, E>(v));
    }

addEdge 添加边

    public void addEdge(V from, V to, E weight) {
        // 判断顶点是否存在
        Vertex<V, E> fromVertex = vertices.get(from);

        // 如果出点没有就在map中加入
        if (fromVertex == null) {
            fromVertex = new Vertex<V, E>(from);
            vertices.put(from, fromVertex);
        }
        // 如果入点没有就在map中加入
        Vertex<V, E> toVertex = vertices.get(to);
        if (toVertex == null) {
            toVertex = new Vertex<V, E>(to);
            vertices.put(from, toVertex);
        }

        if (weight != null) {
            Edge<V, E> edge = new Edge<>(fromVertex, toVertex);
            edge.weight = weight;
            // 更新weight的值  先删后创建
            if (fromVertex.outEdges.remove(edge)) {
                toVertex.inEdges.remove(edge);
                edges.remove(edge);
            }
            // 出点的set中加入边信息
            fromVertex.outEdges.add(edge);
            // 入点的set中加入边信息
            toVertex.inEdges.add(edge);
            edges.add(edge);
        }
    }

removeVertex 移除点

    public void removeVertex(V v) {
        // 删除点信息
        Vertex<V, E> vertex = vertices.remove(v);
        if (vertex == null) return;
        // 删除所以和点有关的边信息
        for (Iterator<Edge<V, E>> iterator = vertex.outEdges.iterator(); iterator.hasNext(); ) {
            Edge<V, E> edge = iterator.next();
            // 删除入点中该边信息
            edge.to.inEdges.remove(edge);
            // 删除本点中该边信息
            iterator.remove();
            // 在大集合中删除该点对应的边
            edges.remove(edge);
        }
        // 同上
        for (Iterator<Edge<V, E>> iterator = vertex.inEdges.iterator(); iterator.hasNext(); ) {
            Edge<V, E> edge = iterator.next();
            edge.from.outEdges.remove(edge);
            iterator.remove();
            edges.remove(edge);
        }
    }

移除边

    public void removeEdge(V from, V to) {
        Vertex<V, E> fromVertex = vertices.get(from);
        if (fromVertex == null) return;
        Vertex<V, E> toVertex = vertices.get(to);
        if (toVertex == null) return;
        Edge<V, E> edge = new Edge<V, E>(fromVertex, toVertex);
        if (fromVertex.outEdges.remove(edge)) {
            toVertex.inEdges.remove(edge);
            edges.remove(edge);
        }
    }

# 算法学习