4月 24 2020
0

有10天的时间没写博客了, 这两天也没闲着, 内审来检查的时候提出了一些新的要求, 然后根据这些要求, 短短三天一天一个小版本号,把合同台账给升级了. 目前公司新买了一台VPS,然后我把台账系统挂到了上边. 然后做了个二级域名解析: http://cms.conyli.cc, 没有采用部署的方式, 直接用Django跑着, 反正应用场景比较小.

好了,不管再艰难, 生活还得继续, 还残留了图算法没有搞完. 当然还有之前的红黑树, 某一天还是要回来看掉的.

  1. 图的表示方法 – 邻接矩阵
  2. 图的表示方法 – 邻接表
  3. 设计顶点和边的类
  4. 顶点类的实现 – 框架
  5. 顶点类的实现 – 两个connect方法
  6. 顶点类的实现 – 迭代器
  7. 顶点类的实现 – 其他方法

图的表示方法 – 邻接矩阵

这里就不再赘述图的基本理念了, 核心就是点, 边, 有向/无向, 有权这些概念, 在这个基础上发展出来一系列算法. 虽然书上是先说图概念, 然后算法, 接口, 图的实现. 不过我考虑了一下,还是得反过来.

先弄懂底层如何表示图, 再去看算法, 然后落实到具体操作上. 开始吧.

数组法是一种非常直观的方法, 假如一个图一共有N个顶点, 那么就可以使用一个N*N的邻接矩阵来表示图. 这个邻接矩阵, 实际上就是一个二维数组, 可以用type[N][N]来表示.

这其中的type表示每个数组元素的类型, 如果采用无权图, 则可以简单的用一个布尔值表示有没有边, 如果采用有权图, 则可以在其中放入权值.

同时还可以表示有向关系. 这个数组的每一行中的每一个元素, 代表一个某个编号的顶点与其他顶点之间的关系. 一般规定, type[m][n]为true或者其他表示有连接的数据的时候, 表示m号顶点有一条通向n号顶点的边.

如果规定这个关系是有向的, 那么type[m][n]为true就是一个有向的边, type[n][m]则未必为true. 由此可见, 如果将数组画成正方形格子, 对于有向图, 图形不会以[1,1],[2,2]这条线对称, 而无向图, 是会以这条线为中心对称的.

采用这个方式, 可以简单的想一下获取图的一些复杂度:

  1. 想知道一个顶点A有没有到另外一个顶点B的边, 直接查询 array[A][B] 的值即可, 因此这是一个O(1)操作
  2. 想知道一个顶点A的所有相连的顶点, 无论有向和无向, 都需要扫描array[A]这一行, 因此时间就是O(n).
  3. 想知道有几个点连到某个顶点A. 如果是无向图, 则依然可以扫描array[A], 因为无向图都相连. 如果是有向图, 则需要挨个扫描array[0-N][A], 因此也是O(n)的操作

另外还一个可以想到的问题是, 如果图的连接比较稀疏, 比如一个6个点的图, 可能只有10条边, 但是要占据6*6的内存空间, 空余了26个格子.

图的表示方法 – 邻接表

邻接表其实有点像简化一点的邻接矩阵. 用一个线性表的位置索引表示对应的顶点, 每个元素是一个当前顶点连接到的点的集合.

其实就是不保留空白区域的邻接矩阵, 好处是所用的空间大大减少. 所以一般稀疏图都用邻接表, 而稠密图用邻接矩阵.

可以来想象一下下列操作的复杂度:

  1. 想知道一个顶点A有没有到另外一个顶点B的边, 先要找到邻接表中对应顶点A的集合, 然后遍历这个集合查找是否存在B, 查找B的效率取决于使用的集合的效率, 不过最快的二分也就是logN的水平, 而查找A是常数, 因此这个方法一定不会快于在邻接矩阵中的查找. 不过因为是稀疏图, 所以没慢多少.
  2. 想知道一个顶点A的所有相连的顶点, 这个类似, 无论有向和无向, 都只需要遍历A对应的集合, 因此这个操作是O(n).
  3. 想知道一个有向图中几个点连到A, 这个就比较麻烦了, 因为没有固定的存储位置, 因此需要遍历除了A之外的所有的点, 然后在每个点上查询是否存在A. 如果运气不好的话, 理论性能是O(n^2), 但因为是稀疏图, 整体上不会太慢.

这两种表示方式, 都暗含了一个基础的方式, 就是边是由顶点和图的性质来决定的. 无论是数组还是线性表, 因为有了天然的序号, 所以就可以对应到点, 那么边就可以表示成数组的指定位置, 或者线性表指定序号位置上的集合中是否存在某个数字来表示边.

这样就利用仅仅只记录点的序号的方式, 设计出了图的表示方法.

图的表示方法 – 邻接表

如果遇到一些简单的问题, 那么使用上述两种方法是可以的. 不过实际上经常会遇到一些问题, 尤其是要给顶点或者边加上一些额外的标记, 比如记录是否被访问, 从某个点出发到这个点的距离等等, 在各种图算法中有用. 因此这个时候我们就不能仅仅满足于在线性表或者数组中存储一个简单的基本类型.

考虑到我们实际上存储的是代表顶点的数据, 所以可以设置一个顶点类, 用这个顶点类来放入到图的数据结构中. 此外使用这个顶点, 马上就可以想到, 顶点类中可以包含一个存放了所有指向其相连的顶点的邻接表集合, 这样就可以非常快速的继续定位到其他的顶点.

话说这个类, 让我自己想, 还真的一时难以想出来, 所以还是老样子, 看接口学习一下, 顺便还学习了顶点的英文叫做vertex:

import java.util.Iterator;

public interface VertexInterface<T> {

    //返回这个顶点的label, 这个根据具体的数据, 可以是一个标识符, 也可以是这个顶点存放的数据.
    T getLabel();

    //标识该订单已经被访问过
    void visit();

    //取消该顶点的访问标记
    void unvisit();

    //很显然, 搭配前两个方法, 可以实现一些路径相关的查找, 内部需要有一个布尔值存放访问状态
    boolean isVisited();

    //尝试将当前顶点连接到另外一个顶点endVertex, 这条边的权重为edgeWeight
    //如果endVertex是当前顶点, 或者两个顶点之间已经有边, 则返回false.
    //如果能够连接, 则返回true
    //注意, 如果是无向图, 这个连接应该是相互的, 即连接之后, endVertex也连接到当前点.
    //如果是有向图, 则这个方法仅仅表示当前顶点有一条连接到endVertex的边, endVertex可不一定会连接到当前顶点
    boolean connect(VertexInterface<T> endVertex, double edgeWeight);

    //这是上一个版本的无权图重载
    boolean connect(VertexInterface<T> endVertex);

    //获取当前点所有的邻接点组成的迭代器, 所以很显然, 我们得有一个内部数据结构用来存放邻接点
    Iterator<VertexInterface<T>> getNeighborIterator();

    //获取由权重组成的迭代器, 用于有权图计算
    Iterator<Double> getWeightIterator();

    //有至少邻接点吗?
    boolean hasNeighbor();

    //返回一个未访问的邻接点, 如果全部邻接点都访问过了, 返回null.
    //很显然这个方法也是为了寻路等操作
    VertexInterface<T> getUnvisitedNeighbor();

    //设置当前节点的前驱节点, 很显然也是用于寻路. 在有向图中寻路, 可以通过这个找到路径中指向当前顶点的点
    void setPredecessor(VertexInterface<T> predecessor);

    //获取前驱节点, 没有就返回null
    VertexInterface<T> getPredecessor();

    //是否含有前驱节点, 这三个方法配合起来使用, 很显然, 内部又得有一个数据结构存放前驱顶点
    boolean hasPredecessor();

    //设置顶点的cost, 这个对于一些算法有用
    void setCost(double Newcost);

    //获取顶点的cost
    double getCost();

}

有了接口还没完, 我们想想还需要放什么, 很显然, 无权图可以在邻接表中直接存放另外一个顶点, 因为无权重. 但是有权图需要同时保存权重. 因此可以考虑弄一个类, 把权重和顶点封装起来, 所以可以创建一个边类.

这个边类, 内部只需要维护两个域, 一个指向这个边的末尾顶点, 一个域用来存放权重. 如果是无权图, 就将权重设置为0即可. 这样每个Vertex内部维护一个Edge类的集合表示邻接的点和该边的权重即可.

同时我们考虑Edge类可以作为内部类, 因为只有顶点才使用这个类, 对外暴露的接口应该是统一的顶点类的接口. 当然, 如果愿意的话也可以作为包权限的类, 只要注意任何时候不要暴露内部的Edge引用即可. 不过为了泛型方便, 还是使用内部类即可.

注意接口中的内部类不能为public权限以外的权限, 所以这个内部类不能写在接口中, 要写在稍后实际实现的Vertex类中. 这里只是先把代码写出来:

private class Edge{
    private VertexInterface<T> vertex;
    private double weight;

    public Edge(VertexInterface<T> vertex, double weight) {
        this.vertex = vertex;
        this.weight = weight;
    }

    protected VertexInterface<T> getEndVertex() {
        return vertex;
    }

    protected double getWeight() {
        return weight;
    }
}

有了这个Edge类的辅助, 在实现Vertex的时候, 通过上边的接口分析, 内部的数据至少包含如下内容:

  1. 存放T类型数据的域
  2. 一个布尔值表示访问与否
  3. 存放相邻顶点及权重的集合, 即一个Edge类的集合
  4. 一个存放前驱节点的引用
  5. 一个存放cost值的域

好, 剩下就来实现Vertex类了. 写到这里的时候是4月23号晚上, 话说2020年开年真的是刺激, 疫情到现在没结束不说, 金三胖竟然也挂了. 今晚早点休息, 明天再来继续一鼓作气干完图算法.

顶点类的实现 – 框架

只要实现出了顶点类, 然后配置好每个顶点类的边, 那么图就可以表示成为顶点类对象的集合.

根据上一节的分析, 先来搭出框架.

import java.util.Collection;
import java.util.Iterator;

class Vertex<T> implements VertexInterface<T> {

    //存放T类型数据的域
    private T label;

    //布尔值
    private boolean visited;

    //存放相连的顶点(边)的集合, 使用了之前自行编写的带迭代器的链表
    private MyLinkedList<Edge> edgeList;

    //前驱顶点
    private VertexInterface<T> previousVertex;

    //cost
    private double cost;

    //Edge内部类, 仅仅使用构造器创建对象, 是一个不可变对象
    private class Edge{
        private VertexInterface<T> vertex;
        private double weight;

        protected Edge(VertexInterface<T> vertex, double weight) {
            this.vertex = vertex;
            this.weight = weight;
        }

        protected VertexInterface<T> getEndVertex() {
            return vertex;
        }

        protected double getWeight() {
            return weight;
        }
    }

    //创建一个新顶点的构造器
    public Vertex(T vertexLabel) {
        this.label = vertexLabel;
        this.edgeList = new MyLinkedList<>();
        this.visited = false;
        this.previousVertex = null;
        this.cost = 0;
    }
}

基础设施好了, 现在开始一个一个看方法的实现.

顶点类的实现 – 两个connect方法

connect方法是非常核心的一个方法. 按照我们的设想, 如果要创建一个图, 只需要先创建所有的顶点, 然后使用connect方法描述顶点之间的关系, 最后返回顶点的集合, 就得到一幅图.

由于我们定义了两个connect方法用于有权图和无权图的连接, 所以先编写有权图的连接, 无权其实就是权重为0的连接.

思考一下connect方法的逻辑, 其实很简单, 首先不能自己连接到自己, 然后不能重复, 因此在每次操作的时候, 都需要判断这两种情况, 如果成功通过判断, 就创建Edge对象然后添加到链表中.

@Override
public boolean connect(VertexInterface<T> endVertex, double edgeWeight) {
    boolean result = false;

    //判断要连接的顶点不是自己
    if (!this.equals(endVertex)) {

        //再通过遍历邻接的顶点对象判断顶点是否已经连接

        boolean connected = false;

        for (Edge edge : this.edgeList) {
            if (edge.vertex.equals(endVertex)) {
                connected = true;
                break;
            }
        }

        //没有连接过, 创建新Edge对象加入邻接表, 同时设置结果为true
        if (!connected) {
            this.edgeList.add(new Edge(endVertex, edgeWeight));
            result = true;
        }
    }

    return result;
}

另外一个connect方法就可以简单的套用了:

@Override
public boolean connect(VertexInterface<T> endVertex) {
    return connect(endVertex, 0);
}

写完了这两个方法之后, 来看一下复杂度. 很显然, 添加一个顶点需要扫描所有的邻接点, 一个图最多的邻接点也就是n-1个, 外加还需要判断一次是不是自己, 所以判断是不是邻接就是O(n)复杂度.

还需要考虑插入的性能, 我们这里使用的是链表, 即在头部插入, 操作是O(1), 否则还会更慢. 不过一般是稀疏图, 所以实际性能还可以.

顶点类的实现 – 迭代器

迭代器有两个, 一个是所有相邻顶点的迭代器, 一个是所有cost的迭代器. 由于存放相邻顶点的数据结构是实现了迭代器接口的MyLinkedList, 因此获取Edge类的迭代器很方便, 在上边包装两个类就可以了..

先来创建的迭代器的两个内部类:

//迭代器要使用的两个内部类完成
private class NeighborIterator implements Iterator<VertexInterface<T>> {
    private Iterator<Edge> edges;

    //构造器在内部使用edgeList的迭代器
    NeighborIterator() {
        this.edges = edgeList.iterator();
    }

    //这两个方法都是包装, 实际上还是从edges这个迭代器中取结果
    @Override
    public boolean hasNext() {
        return edges.hasNext();
    }

    @Override
    public VertexInterface<T> next() {

        if (edges.hasNext()) {
            return edges.next().vertex;
        } else {
            throw new NoSuchElementException();
        }
    }
}

//这个类和上边一样
private class CostIterator implements Iterator<Double> {
    private Iterator<Edge> edges;

    CostIterator() {
        this.edges = edgeList.iterator();
    }

    @Override
    public boolean hasNext() {
        return edges.hasNext();
    }

    @Override
    public Double next() {
        if (edges.hasNext()) {
            return edges.next().vertex.getCost();
        } else {
            throw new NoSuchElementException();
        }
    }
}

然后是两个方法, 返回新创建的迭代器即可:

@Override
public Iterator<VertexInterface<T>> getNeighborIterator() {
    return new NeighborIterator();
}

@Override
public Iterator<Double> getWeightIterator() {
    return new CostIterator();
}

有了迭代器之后, 还有一个方法与迭代器相关, 就是返回下一个没有访问的顶点, 这个需要在内部使用迭代器来操作, 因此一起写上了:

@Override
public VertexInterface<T> getUnvisitedNeighbor() {
    VertexInterface<T> result = null;

    //获取相邻顶点迭代器
    Iterator<VertexInterface<T>> neighbors = getNeighborIterator();

    //逐项检查如果没有被访问过, 就中止循环然后返回这个点.
    while (neighbors.hasNext()) {
        if (!neighbors.next().isVisited()) {
            result = neighbors.next();
            break;
        }
    }

    return result;
}

顶点类的实现 – 其他方法

剩下基本都是一些getter和setter, 没什么太复杂的, 要先把hash和equals写了才行:

//其他方法 hash and equals
@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(label, vertex.label);

}

@Override
public int hashCode() {
    return Objects.hash(label, visited, edgeList, previousVertex, cost);
}

然后就是一堆简单方法的批发:

@Override
public T getLabel() {
    return label;
}

@Override
public void visit() {
    this.visited = true;
}

@Override
public void unvisit() {
    this.visited = false;
}

@Override
public boolean isVisited() {
    return visited;
}

//是否有邻居, 只要检查链表是不是为空, 为空就是没有邻居
@Override
public boolean hasNeighbor() {
    return !edgeList.isEmpty();
}

@Override
public void setPredecessor(VertexInterface<T> predecessor) {
    this.previousVertex = predecessor;
}

@Override
public VertexInterface<T> getPredecessor() {
    return previousVertex;
}

@Override
public boolean hasPredecessor() {
    return this.previousVertex != null;
}

@Override
public void setCost(double newCost) {
    this.cost = newCost;
}

@Override
public double getCost() {
    return cost;
}

这样就写好了一个顶点类, 内部包含一个Edge类和两个迭代器类. 有了这个类就可以来创建图和实现算法了.

发表于数据结构与算法

发表评论

邮箱地址不会被公开。 必填项已用*标注