java使用邻接表实现图

ゞ浴缸里的玫瑰 2023-02-21 04:50 37阅读 0赞

# 邻接表实现图 #

图的表示方式有两种：

*  邻接矩阵（Adjacency Matrix）
 *  邻接表（Adjacency List）

本文采用类似邻接表的方式实现图。

## 图的基础接口 ##

public interface Graph<V, E> { 
    
        int verticesSize(); // 顶点数量
    
        int edgesSize(); // 边的数量
    
        void addVertex(V v); // 添加顶点
    
        void addEdge(V from, V to); // 添加边
    
        void addEdge(V from, V to, E weight); // 添加带权值的边
    
        void removeVertex(V v); // 删除顶点
    
        void removeEdge(V from, V to); // 删除边
    }

## 顶点的定义 ##

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 o) { 
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Vertex<?, ?> vertex = (Vertex<?, ?>) o;
            return Objects.equals(value, vertex.value);
        }
    
        @Override
        public int hashCode() { 
            return Objects.hash(value);
        }
    }

## 边的定义 ##

private static class Edge<V, E> { 
        Vertex<V, E> fromVertex; // 起始顶点
        Vertex<V, E> toVertex; // 结束顶点
        E weight; // 权重
    
        public Edge(Vertex<V, E> fromVertex, Vertex<V, E> toVertex, E weight) { 
            this.fromVertex = fromVertex;
            this.toVertex = toVertex;
            this.weight = weight;
        }
    
        @Override
        public boolean equals(Object o) { 
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Edge<?, ?> edge = (Edge<?, ?>) o;
            return Objects.equals(fromVertex, edge.fromVertex) && Objects.equals(toVertex, edge.toVertex);
        }
    
        @Override
        public int hashCode() { 
            return Objects.hash(fromVertex, toVertex);
        }
    }

## 邻接表的结构 ##

public class ListGraph<V, E> implements Graph<V, E> { 
    
        Map<V, Vertex<V, E>> vertices = new HashMap<>(); // 存放所有的顶点
        Set<Edge<V, E>> edges = new HashSet<>(); // 存放所有的边
    
        public int verticesSize() { 
            return vertices.size();
        }
    
        public int edgesSize() { 
            return edges.size();
        }

## 添加顶点 ##

public void addVertex(V v) { 
        vertices.putIfAbsent(v, new Vertex<>(v));
    }

## 添加边 ##

public void addEdge(V from, V to) { 
        addEdge(from, to, null);
    }
    
    public void addEdge(V from, V to, E weight) { 
    
        // 先判断顶点是否存在，不存在则添加
        addVertex(from);
        addVertex(to);
    
        // 根据值获取顶点
        Vertex<V, E> fromVertex = vertices.get(from);
        Vertex<V, E> toVertex = vertices.get(to);
    
        Edge<V, E> edge = new Edge(fromVertex, toVertex, weight);
    
        // 存放边的结构是set，直接添加会导致如果边存在就会被替换，不存在则添加
        fromVertex.outEdges.add(edge);
        toVertex.inEdges.add(edge);
    
        edges.add(edge);
    }

## 删除边 ##

public void removeEdge(V from, V to) { 
        // 根据值获取顶点
        Vertex<V, E> fromVertex = vertices.get(from);
        Vertex<V, E> toVertex = vertices.get(to);
    
        // 顶点不存在直接返回
        if(null == fromVertex || null == toVertex) { 
            return;
        }
    
        Edge<V, E> edge = new Edge<>(fromVertex, toVertex, null);
        if (fromVertex.outEdges.remove(edge)) {  // 删除起点出去集合中的边
            toVertex.inEdges.remove(edge); // 删除终点进入集合中的边
            edges.remove(edge);
        }
    }

## 删除顶点 ##

public void removeVertex(V v) { 
        // 根据值获取顶点
        Vertex<V, E> vertex = vertices.get(v);
    
        // 顶点不存在直接返回
        if(null == vertex) { 
            return;
        }
    
        // 删除以v为起点的终点中的进入集合中的边
        vertex.outEdges.forEach(edge -> { 
            edge.toVertex.inEdges.remove(new Edge(vertex, edge.toVertex, null));
            edges.remove(edge);
        });
    
        // 删除以v为终点的起点中的出去集合中的边
        vertex.inEdges.forEach(edge -> { 
            edge.fromVertex.outEdges.remove(new Edge(edge.fromVertex, vertex, null));
            edges.remove(edge);
        });
    
        vertices.remove(v);
    }

更多精彩内容关注本人公众号：架构师升级之路  
![在这里插入图片描述][20200627175030665.jpg]

[20200627175030665.jpg]: https://img-blog.csdnimg.cn/20200627175030665.jpg