数据结构与算法之图的基本实现

图

• 图由顶点(vertex)和边(edge)组成，通常表示为G=(V,E)

图的分类

有向图
有明确方向的图

image.png

• 有向无环图(DAG)
  如果一个有向图，从任意顶点出发无法经过若干条边回到该顶点，那么它就是一个有向无环图

image.png

• 出度、入度
  1、出度、入度适用于有向图
  2、 度：某个顶点的度就是依附于该顶点的个数
  3、 出度：表示该顶点为起点的边数量(其实看箭头就可以了，箭头出去就是出度)
  4、入度：表示该顶点为终点的边的数量(箭头进来的)

  
  image.png
  

  比如上图：7的入度是3，出度是2

无向图

• 无向图的边是无向的

  
  image.png
  

  其实无向图类似与下面的有向图

  
  image.png

混合图
可能是有向，也可能是无向

image.png

简单图和多重图

• 平行边：
  1、无向图中，关联一对顶点的无向边如果多于1条，则称为平行边(如下图的三条线)

  
  image.png
  

  2、有向图中，关联一对顶点的有向边如果多于一条，并且它们的方向相同，则称为平行边

  
  image.png

• 简单图
  没有平行边也没有自环的图

  
  image.png

• 多重图
  有平行边或者有自环的图

• 无向完全图
  性质1、任意两个顶点之间都存在边
  性质2、n个顶点的无向完全图有n(n-1)/2个边

性质2推导:比如4个顶点

image.png

首先6连边的结果:一共3条边

image.png
然后8连边的结果：一共2条，最后3连边一共1条结果
image.png

所以边数一共是：3+2+1=4*3/2=n(n-1)/2

• 有向完全图
  任意两个顶点之间都存在方向相反的两条边

  
  image.png

• 有权图
  有权图的边可以有权值

  
  image.png

图的实现方案

图有两种常见的实现方案
1、领接矩阵
2、领接表

邻接矩阵的存储方式
一维数组存放顶点信息
二维数组存放边信息

image.png

v1->v0有边所以写1，v0->v1没有边，所有写0

弊端：我们会发现画的红色斜线，上下对称，所以领接矩阵比较浪费内存

• 领接矩阵有权图

  
  image.png

领接表

• 无向图的领接表

  
  image.png

• 有向图的领接表

  
  image.png

图的基础接口定义

public interface Graph<V, E> {
    /**
     * 边得大小
     */
    int edgesSize();

    /**
     * 顶点的大小
     */
    int verticesSize();

    /**
     * 添加顶点
     * @param v 顶点
     */
    void addVertext(V v);

    /**
     * 添加边
     * @param from 入度顶点
     * @param to 出度顶点
     */
    void addEdge(V from, V to);
    /**
     * 添加边
     * @param from 入度顶点
     * @param to 出度顶点
     * @param weight 权重
     */
    void addEdge(V from, V to, E weight);

    /**
     * 移除顶点
     * @param v 顶点
     */
    void removeVertex(V v);

    /**
     * 移除边
     * @param from 入度顶点
     * @param to 出度顶点
     */
    void removeEdge(V from, V to);
}

图的基础实现

image.png

顶点的定义

• 每个顶点有三个元素：1、值value、2、该顶点出度的集合、3、该顶点的入度的集合
• 因为我们在添加顶点的时候，需要判断当前顶点是否已经被添加了，那么判断两个顶点是否相等，我们需要重新实现equals和hashCode
• 根据value来判断是否是同一个顶点

    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 v) {
            this.value = v;
        }
        @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();
        }
        @Override
        public String toString() {
            return value == null ? "" : value.toString();
        }
    }

边的定义

• 边是两个顶点连接而成的，那么顶点肯定需要两个(from 和to)，从哪个顶点到哪个顶点
• 边可能有权重
• 添加边的时候需要判断边是否相等，判断依旧需要重写hashCode和equals
• hashCode等于from顶点和to顶点的hash相加
• equals需要判断两个边的from是否一样，以及两个边的to是否一样

    private static class Edge<V, E> {
        Vertex<V, E> from;
        Vertex<V, E> to;
        E weight;

        public Edge(Vertex<V, E> fromVertex, Vertex<V, E> toVertex) {
            this.from = fromVertex;
            this.to = toVertex;
        }

        @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 31 * from.hashCode() + to.hashCode();
        }

        @Override
        public String toString() {
            return "Edge{" +
                    "from=" + from +
                    ", to=" + to +
                    ", weight=" + weight +
                    '}';
        }
    }

添加顶点

• 首先需要有个Map集合，key是值，value是边
• 判断map是否有该值的边，有就直接返回，没有需要将值添加到map中

   private Map<V, Vertex<V, E>> vertices = new HashMap<>();
    @Override
    public int verticesSize() {
        return vertices.size();
    }
    /**
     * 添加顶点
     */
    @Override
    public void addVertext(V v) {
        if (vertices.containsKey(v)) return;
        vertices.put(v, new Vertex<>(v));
    }

添加边

• 需要一个set集合存放所有的边
• map中判断from是否有边，没有就创建，并添加到map中
• map中判断to是否有边，没有就创建，并添加到map中

• 根据from和to创建一个新的边edge

  
  image.png
  

  如上图的v1和v2,假设现在的from是v1,to是v2,

• 删除v1中的出度的边，如果成功，继续删除v2的入度，并将边的set集合也已要移除该边
• 然后我们再设置v1的出度等于新创建的边edge，v2的入度等于新创建的边edge

    private Set<Edge<V, E>> edges = new HashSet<>();
    @Override
    public int edgesSize() {
        return edges.size();
    }
    /**
     * 添加边
     * @param from 入度顶点
     * @param to 出度顶点
     */
    @Override
    public void addEdge(V from, V to) {
        addEdge(from, to, null);
    }

    /**
     * 添加边
     * @param from 入度顶点
     * @param to 出度顶点
     * @param weight 权重
     */
    @Override
    public void addEdge(V from, V to, E weight) {
        Vertex<V, E> fromVertex = vertices.get(from);
        if (fromVertex == null) {
            fromVertex = new Vertex<>(from);
            vertices.put(from, fromVertex);
        }
        Vertex<V, E> toVertex = vertices.get(to);
        if (toVertex == null) {
            toVertex = new Vertex<>(to);
            vertices.put(to, toVertex);
        }
        Edge<V, E> edge = new Edge<>(fromVertex, toVertex);
        edge.weight = weight;

        if (fromVertex.outEdges.remove(edge)) {
            toVertex.inEdges.remove(edge);
            edges.remove(edge);
        }
        fromVertex.outEdges.add(edge);
        toVertex.inEdges.add(edge);
        edges.add(edge);
    }

删除某边

image.png

• 比如我们要删除v2->v0这条边，from是v2,to是v0
• 从map中根据from和to获取边，如果没有直接返回
• 根据from和to创建新边，v2的出度也就是from的出度要移除
• v0的入度删除
• 整个边的集合删除

    @Override
    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<>(fromVertex, toVertex);
        if (fromVertex.outEdges.remove(edge)) {
            toVertex.inEdges.remove(edge);
            edges.remove(edge);
        }
    }

删除某个顶点

image.png

• 比如删除v2这个顶点，需要删除所有的入度和出度
• 根据顶点获取边，如果没有则直接返回
• 遍历该边的所有出度，删除该边的to的入度，当前遍历的边删除，边的集合也删除该边。如上图，v2的出度有v0和v3，那该边的to边是v0和v3，删除v0和v3的入度，再删除遍历到边
• 该边的入度以上步相似

    @Override
    public void removeVertex(V v) {
        Vertex<V, E> vertex = vertices.remove(v);
        if (vertex == null) return;
        //出度 1->2->3 移除2
        Iterator<Edge<V, E>> outIterator = vertex.outEdges.iterator();
        while (outIterator.hasNext()) {
            Edge<V, E> edge = outIterator.next();
            edge.to.inEdges.remove(edge);
            //当前遍历的边删除
            outIterator.remove();
            edges.remove(edge);
        }
        Iterator<Edge<V, E>> inIterator = vertex.inEdges.iterator();
        while (inIterator.hasNext()) {
            Edge<V, E> edge = inIterator.next();
            edge.from.outEdges.remove(edge);
            // 当前遍历的边删除
            inIterator.remove();
            edges.remove(edge);
        }
    }

测试

打印工具类封装

  public void print() {
        vertices.forEach((V v, Vertex<V, E> vertex) -> {
            System.out.print("\t\t\t|-----");
            System.out.print("入度:");
            System.out.print(vertex.inEdges);
            System.out.println("\t\t\t|");
            System.out.print("\t\t\t|");
            System.out.print("\n[顶点]:");
            System.out.println(v +"--->");
            System.out.println("\t\t\t|");
            System.out.println("\t\t\t|");
            System.out.print("\t\t\t|-----");
            System.out.print("出度:");
            System.out.println(vertex.outEdges);

            System.out.println("\n\n");
        });

        System.out.println("-----------[边]-----------");
        edges.forEach((Edge<V, E> edge) -> {
            System.out.println(edge);
        });
    }

main函数中有向图

        ListGraph<String, Integer> graph = new ListGraph<>();
        graph.addEdge("V1", "V0", 9);
        graph.addEdge("V1", "V2", 3);
        graph.addEdge("V2", "V0", 2);
        graph.addEdge("V2", "V3", 5);
        graph.addEdge("V3", "V4", 1);
        graph.addEdge("V0", "V4", 6);
               graph.addEdge("V1", "V0", 12);
        graph.print();

部分截图.png

移除v2->v0这条边

graph.removeEdge("V2","V0");

image.png

移除顶点

        graph.removeVertex("V2");

image.png image.png

无向图

        ListGraph<String, Integer> graph = new ListGraph<>();
        graph.addEdge("V0", "V1");
        graph.addEdge("V1", "V0");

        graph.addEdge("V0", "V2");
        graph.addEdge("V2", "V0");

        graph.addEdge("V0", "V3");
        graph.addEdge("V3", "V0");

        graph.addEdge("V1", "V2");
        graph.addEdge("V2", "V1");

        graph.addEdge("V2", "V3");
        graph.addEdge("V3", "V2");

        graph.print();