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

图的表示方法 - 邻接矩阵

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

图的表示方法 - 邻接表

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

图的表示方法 - 邻接表

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();

}

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;
    }
}

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

顶点类的实现 - 框架

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方法

@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;
}

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

顶点类的实现 - 迭代器

//迭代器要使用的两个内部类完成
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;
}

顶点类的实现 - 其他方法

//其他方法 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;
}