Java 数据结构

使用JAVA语言以邻接表的方式实现了数据结构---图（Graph），用JAVA来表示图的顶点。从数据的表示方法来说，有二种表示图的方式：一种是邻接矩阵，其实是一个二维数组；一种是邻接表，其实是一个顶点表，每个顶点又拥有一个边列表。下图是图的邻接表表示。

从图中可以看出，图的实现需要能够表示顶点表，能够表示边表。邻接表指是的哪部分呢？每个顶点都有一个邻接表，一个指定顶点的邻接表中，起始顶点表示边的起点，其他顶点表示边的终点。这样，就可以用邻接表来实现边的表示了。如顶点V0的邻接表如下：

与V0关联的边有三条，因为V0的邻接表中有三个顶点(不考虑V0)。

具体分析

先来分析边表：在图中如何来表示一条边？很简单，就是：起始顶点指向结束顶点、就是顶点对

protected class Edge implements java.io.Serializable {
 private VertexInterface<T> vertex;// 终点
 private double weight;//权值

Edge类中只有两个属性，vertex 用来表示顶点，该顶点是边的终点。weight 表示边的权值。若不考虑带权的情况，就不需要weight属性，那么可以直接定义一个顶点列表 来存放 终点 就可以表示边了。这是因为：这些属性是定义在Vertex.java中，而Vertex本身就表示顶点，如果在Vertex内部定义一个List存放终点，那么该List再加上Vertex所表示的顶点本身，就可以表示与起点邻接的各个点了（称之为这个 起点的邻接表）。这样的边的特点是：边的所有的起始点都相同。

但是为了表示带权的边，因此，新增加weight属性，并用类Edge来封装，这样不管是带权的边还是不带权的边都可以用同一个Edge类来表示。不带权的边将weight赋值为0即可。

再分析顶点表：

定义接口VertexInterface，参考资料：http://www.cnblogs.com/hapjin/p/4760934.html

class Vertex<T> implements VertexInterface<T>, java.io.Serializable {

    private T label;//标识标点,可以用不同类型来标识顶点如String,Integer....
    private List<Edge> edgeList;//到该顶点邻接点的边,实际以java.util.LinkedList存储
    private boolean visited;//标识顶点是否已访问
    private VertexInterface<T> previousVertex;//该顶点的前驱顶点
    private double cost;//顶点的权值,与边的权值要区别开来

解释Vertex类中定义的各个属性：

label : 用来标识顶点，如图中的 V0,V1,V2,V3，在实际代码中，V0...V3 以字符串的形式表示，就可以用来标识不同的顶点了。因此，需要在Vertex类中添加获得顶点标识的方法---getLabel()

public T getLabel() {
 return label;
}

edgeList : 存放与该顶点关联的边。从上面Edge.java中可以看到，Edge的实质是“顶点”，因为，Edge类除去wight属性，就只剩表示顶点的vertex属性了。借助edgeList，当给定一个顶点时，就可以访问该顶点的所有邻接点。因此，Vertex.java中就需要实现根据edgeList中存放的边来遍历 某条边的终点(也即相应顶点的各个邻接点) 的迭代器了。

public Iterator<VertexInterface<T>> getNeighborInterator() {
    return new NeighborIterator();
}

迭代器的实现如下：

/**Task: 遍历该顶点邻接点的迭代器--为 getNeighborInterator()方法 提供迭代器
     * 由于顶点的邻接点以边的形式存储在java.util.List中,因此借助List的迭代器来实现
     * 由于顶点的邻接点由Edge类封装起来了--见Edge.java的定义的第一个属性
     * 因此，首先获得遍历Edge对象的迭代器,再根据获得的Edge对象解析出邻接点对象
     */
    private class NeighborIterator implements Iterator<VertexInterface<T>>{

Iterator<Edge> edgesIterator;
private NeighborIterator() {
    edgesIterator = edgeList.iterator();//获得遍历edgesList 的迭代器
}
@Override
public boolean hasNext() {
    return edgesIterator.hasNext();
}

@Override
public VertexInterface<T> next() {
    VertexInterface<T> nextNeighbor = null;
    if(edgesIterator.hasNext()){
Edge edgeToNextNeighbor = edgesIterator.next();//LinkedList中存储的是Edge
nextNeighbor = edgeToNextNeighbor.getEndVertex();//从Edge对象中取出顶点
    }
    else
throw new NoSuchElementException();
    return nextNeighbor;
}

@Override
public void remove() {
    throw new UnsupportedOperationException();
}
    }

visited : 之所以给每个顶点设置一个用来标记它是否被访问的属性，是因为：实现一个数据结构，是要用它去完成某些功能的，如遍历、查找…… 而在图的遍历过程中，就需要标记某个顶点是否被访问了，因此：设置该属性以便实现这些功能。那么，也就需要定义获取顶点是否被访问的isVisited()方法了。

public boolean isVisited() {
    return visited;
}

previousVertex 属性 ，在求图中某两个顶点之间的最短路径时，在从起始顶点遍历过程中，需要记录下遍历到某个顶点时的前驱顶点， previousVertex 属性就派上用场了。因此，需要有判断和获取顶点的前驱顶点的方法：

public boolean hasPredecessor() {//判断顶点是否有前驱顶点
    return this.previousVertex != null;
}

/**************************/

public VertexInterface<T> getPredecessor() {//获得前驱顶点
    return this.previousVertex;
}

cost 属性：用来表示顶点的权值。注意，顶点的权值与边的权值是不同的。比如求无权图（默认是边不带权值）的最短路径时，如何求出顶点A到顶点B的最短的路径？由定义，该最短路径其实就是A走到B经历的最少边数目。因此，就可以用 cost 属性来记录A到B之间的距离是多少了。比如说，A 先走到 C 再走到B；初始时，A的 cost = 0，由于 A 是 C 的前驱，A到B需要经历C，C 的 cost 就是 c.previousVertex.cost + 1，直至 B，就可以求出 A 到 B 的最短路径了。

因此，针对 cost 属性，Vertex.java需要实现的方法如下：

public void setCost(double newCost) {
    cost = newCost;
}
public double getCost() {
    return cost;
}

分析：

从上可以看出，设计一个数据结构时，该数据结构需要包含哪些属性不是随意的，而是先确定该数据结构需要完成哪些功能（如，图的DFS、BFS、拓扑排序、最短路径），这些功能的实现需要借助哪些属性(如，求最短路径需要记录每个顶点的前驱顶点，就需要 previousVertex)。然后，去定义这些属性以及关于该属性的基本操作。设计一个合适的数据结构，当借助该数据结构来实现算法时，可以有效地降低算法的实现难度和复杂度！

Vertex.java类完整代码如下：

package graph;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;

class Vertex<T> implements VertexInterface<T>, java.io.Serializable {

    private T label;//标识标点,可以用不同类型来标识顶点如String,Integer....
    private List<Edge> edgeList;//到该顶点邻接点的边,实际以java.util.LinkedList存储
    private boolean visited;//标识顶点是否已访问
    private VertexInterface<T> previousVertex;//该顶点的前驱顶点
    private double cost;//顶点的权值,与边的权值要区别开来
    
    public Vertex(T vertexLabel){
label = vertexLabel;
edgeList = new LinkedList<Edge>();//是Vertex的属性,说明每个顶点都有一个edgeList用来存储所有与该顶点关系的边
visited = false;
previousVertex = null;
cost = 0;
    }
    
    /**
     *Task: 这里用了一个单独的类来表示边,主要是考虑到带权值的边
     *可以看出,Edge类封装了一个顶点和一个double类型变量 
     *若不需要考虑权值,可以不需要单独创建一个Edge类来表示边,只需要一个保存顶点的列表即可
     * @author hapjin
     */
    protected class Edge implements java.io.Serializable {
private VertexInterface<T> vertex;// 终点
private double weight;//权值

//Vertex 类本身就代表顶点对象,因此在这里只需提供 endVertex，就可以表示一条边了
protected Edge(VertexInterface<T> endVertex, double edgeWeight){
    vertex = endVertex;
    weight = edgeWeight;
}

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

    /**Task: 遍历该顶点邻接点的迭代器--为 getNeighborInterator()方法 提供迭代器
     * 由于顶点的邻接点以边的形式存储在java.util.List中,因此借助List的迭代器来实现
     * 由于顶点的邻接点由Edge类封装起来了--见Edge.java的定义的第一个属性
     * 因此，首先获得遍历Edge对象的迭代器,再根据获得的Edge对象解析出邻接点对象
     */
    private class NeighborIterator implements Iterator<VertexInterface<T>>{

Iterator<Edge> edgesIterator;
private NeighborIterator() {
    edgesIterator = edgeList.iterator();//获得遍历edgesList 的迭代器
}
@Override
public boolean hasNext() {
    return edgesIterator.hasNext();
}

@Override
public VertexInterface<T> next() {
    VertexInterface<T> nextNeighbor = null;
    if(edgesIterator.hasNext()){
Edge edgeToNextNeighbor = edgesIterator.next();//LinkedList中存储的是Edge
nextNeighbor = edgeToNextNeighbor.getEndVertex();//从Edge对象中取出顶点
    }
    else
throw new NoSuchElementException();
    return nextNeighbor;
}

@Override
public void remove() {
    throw new UnsupportedOperationException();
}
    }
    
    /**Task: 生成一个遍历该顶点所有邻接边的权值的迭代器
     * 权值是Edge类的属性,因此先获得一个遍历Edge对象的迭代器,取得Edge对象,再获得权值
     * @author hapjin
     *
     * @param <Double> 权值的类型
     */
    private class WeightIterator implements Iterator{//这里不知道为什么,用泛型报编译错误???

private Iterator<Edge> edgesIterator;
private WeightIterator(){
    edgesIterator = edgeList.iterator();
}
@Override
public boolean hasNext() {
    return edgesIterator.hasNext();
}
@Override
public Object next() {
    Double result;
    if(edgesIterator.hasNext()){
Edge edge = edgesIterator.next();
result = edge.getWeight();
    }
    else throw new NoSuchElementException();
    return (Object)result;//从迭代器中取得结果时,需要强制转换成Double
}
@Override
public void remove() {
    throw new UnsupportedOperationException();
}

    }
    
    @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 connect(VertexInterface<T> endVertex, double edgeWeight) {
// 将"边"(边的实质是顶点)插入顶点的邻接表
boolean result = false;
if(!this.equals(endVertex)){//顶点互不相同
    Iterator<VertexInterface<T>> neighbors = this.getNeighborInterator();
    boolean duplicateEdge = false;
    while(!duplicateEdge && neighbors.hasNext()){//保证不添加重复的边
VertexInterface<T> nextNeighbor = neighbors.next();
if(endVertex.equals(nextNeighbor)){
    duplicateEdge = true;
    break;
}
    }//end while
    if(!duplicateEdge){
edgeList.add(new Edge(endVertex, edgeWeight));//添加一条新边
result = true;
    }//end if
}//end if
return result;
    }

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

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

    @Override
    public Iterator getWeightIterator() {
return new WeightIterator();
    }

    @Override
    public boolean hasNeighbor() {
return !(edgeList.isEmpty());//邻接点实质是存储是List中
    }

    @Override
    public VertexInterface<T> getUnvisitedNeighbor() {
VertexInterface<T> result = null;
Iterator<VertexInterface<T>> neighbors = getNeighborInterator();
while(neighbors.hasNext() && result == null){//获得该顶点的第一个未被访问的邻接点
    VertexInterface<T> nextNeighbor = neighbors.next();
    if(!nextNeighbor.isVisited())
result = nextNeighbor;
}
return result;
    }

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

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

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

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

    @Override
    public double getCost() {
return cost;
    }
    
    //判断两个顶点是否相同
    public boolean equals(Object other){
boolean result;
if((other == null) || (getClass() != other.getClass()))
    result = false;
else
{
    Vertex<T> otherVertex = (Vertex<T>)other;
    result = label.equals(otherVertex.label);//节点是否相同最终还是由标识 节点类型的类的equals() 决定
}
return result;
    }
}

实现图的邻接表

图的实现与邻接表的实现最大的不同就是，图的实现需要定义一个数据结构来存储所有的顶点以及能够对图进行什么操作，而邻接表的实现重点关注的图中顶点的实现，即怎么定义JAVA类来表示顶点，以及能够对顶点进行什么操作。参考资料：http://www.cnblogs.com/hapjin/p/4766823.html

为了存储图中所有的顶点，定义了一个Map，value当然就是表示顶点的类了，因为我们需要存储的是顶点。即value 为 VertexInterface

此外，还定义了一个整型变量 edgeCount 用来保存图中边的数目，这也是必要的。讨论一个图，当然要有图的顶点，由Map保存，顶点数目可以通过 Map.size() 方法获得；也要有边，而边已经隐含在Vertex.java中了(具体参考上一篇文章），因此这里只定义一个保存图中边的总数的变量即可。图的定义部分代码如下：

public class DirectedGraph<T> implements GraphInterface<T>,java.io.Serializable{

    private static final long serialVersionUID = 1L;

    private Map<T, VertexInterface<T>> vertices;//map 对象用来保存图中的所有顶点.T 是顶点标识,VertexInterface为顶点对象
    private int edgeCount;//记录图中 边的总数
    
    public DirectedGraph() {
vertices = new LinkedHashMap<>();//按顶点的插入顺序保存顶点
}

图的基本操作

这里的基本操作不是对图进行DFS、BFS、拓扑排序、求最短路径……而是一系列的如何构造图的方法，这些方法是实现图的遍历、求最短路径、拓扑排序的基础。

那么如何把顶点对象添加到Map中呢？

public void addVertex(T vertexLabel) {
//若顶点相同时,新插入的顶点将覆盖原顶点,这是由LinkedHashMap的put方法决定的
//每添加一个顶点,会创建一个LinkedList列表,它存储该顶点对应的邻接点,或者说是与该顶点相关联的边
vertices.put(vertexLabel, new Vertex(vertexLabel));//new Vertex 对象,会创建一个LinkedList,该LinkedList用来表示该顶点的邻接表
}

如何表示图中两个顶点之间的边呢？

public boolean addEdge(T begin, T end, double edgeWeight) {
boolean result = false;
VertexInterface<T> beginVertex = vertices.get(begin);//获得表示边的起始顶点
VertexInterface<T> endVertex = vertices.get(end);//获得表示 边的终点

if(beginVertex != null && endVertex != null)
    result = beginVertex.connect(endVertex, edgeWeight);//起始点与终点连接,即成一条边
if(result)
    edgeCount++;
return result;//当添加重复边时会返回 false
}

图的相关算法的JAVA实现及分析

算法的实现依赖于采用了何种数据结构，依赖于数据结构--图的具体实现。由于这里的数据结构--图的实现与《算法导论》中描述的图的数据结构有一点差别，如：没有定义表示图的访问状态的"白色顶点、灰色顶点、黑色顶点"，因此算法的实现也与《算法导论》中算法的实现有轻微的差别。

对于不带权的图而言(边上没有权值) 广度优先遍历算法与最短路径算法很相似，对广度优先遍历算法稍加修改，就可以变成最短路径算法了。可参考：无向图的最短路径算法JAVA实现 和 带权图的最短路径算法(Dijkstra)实现

理解：

深度优先遍历算法与拓扑算法也很相似，拓扑排序算法的实现可以借助深度优先遍历算法。具体参考《算法导论》

广度优先遍历算法

若顶点A先于顶点B被访问，则顶点A的邻接点也先于顶点B的邻接点被访问。特点：先把起始顶点附近的顶点访问完，再访问远处的顶点。在广度优先遍历算法的具体实现中，需要两个队列。一个辅助遍历，保存遍历过程中遇到的顶点，当访问完成了某个顶点A后，将A出队列，紧接着将A的所有邻接点都入队列，并访问。

另一个队列用来保存访问的顺序，另一个队列的顶点入队顺序就是图的广度遍历顺序，因此，该队列保持 与 前一个队列的顶点入队操作 一致。由于前一个队列是辅助遍历的，它有出队的操作，它就不能记录整个顶点的访问序列了，因此才需要一个保存访问顺序的队列。当整个过程遍历完成后，将 保存访问顺序的队列 进行出队操作，即可得到整个图的广度优先遍历的顺序了。具体算法如下：

public Queue<T> getBreadthFirstTraversal(T origin) {//origin 标识遍历的初始顶点
    resetVertices();//将顶点的必要数据域初始化,复杂度为O(V)
    Queue<VertexInterface<T>> vertexQueue = new LinkedList<>();//保存遍历过程中遇到的顶点,它是辅助遍历的,有出队列操作
    Queue<T> traversalOrder = new LinkedList<>();//保存遍历过程中遇到的 顶点标识--整个图的遍历顺序就保存在其中,无出队操作
    VertexInterface<T> originVertex = vertices.get(origin);//根据顶点标识获得初始遍历顶点
    originVertex.visit();//访问该顶点
    traversalOrder.offer(originVertex.getLabel());
    vertexQueue.offer(originVertex);

    while(!vertexQueue.isEmpty()){
VertexInterface<T> frontVertex = vertexQueue.poll();//出队列,poll()在队列为空时返回null
Iterator<VertexInterface<T>> neighbors = frontVertex.getNeighborInterator();
while(neighbors.hasNext())//对于 每个顶点都遍历了它的邻接表,即遍历了所有的边,复杂度为O(E)
{
    VertexInterface<T> nextNeighbor = neighbors.next();
    if(!nextNeighbor.isVisited()){
    nextNeighbor.visit();//广度优先遍历未访问的顶点
traversalOrder.offer(nextNeighbor.getLabel());
vertexQueue.offer(nextNeighbor);//将该顶点的邻接点入队列
    }
}//end inner while
    }//end outer while
    return traversalOrder;
}

从中可以看出，该算法的时间复杂度为--遍历之前，给每个顶点进行初始化时需要遍历所有顶点V，在遍历过程中需要判断顶点的邻接点是否被遍历，也即遍历该顶点的邻接表，邻接表代表的实质是边，边总数为E，故总的时间复杂度为O(V+E)，空间复杂度为O(V)--辅助队列的长度为顶点的长度

最短路径算法

在边不带权值的图中求顶点A到顶点B的最短路径--其实就是顶点A到顶点B之间的最少边的条数

调用最短路径算法之前，首先要确定一个初始顶点，图中其他顶点的路径长度都是相对于初始顶点而言的。求两个顶点间最短路径，其实并不是找出两个顶点间所有的路径长度，然后取最小值。而是借助于广度优先遍历算法，将每个顶点相对于初始顶点的最短路径长度保存在 cost 属性中，广度优先算法的性质保证了顶点间的路径是最短的。在最短路径的计算中，设初始点为 i，顶点A相对于初始点的最短路径长度为 length,则 顶点A的邻接点 相对于初始顶点 i 的最短长度为 length+1.

因此，执行最短路径算法后，实际上求得了图中所有顶点相对于初始顶点的最短路径。

初始顶点的路径长度为0（每个顶点有一个 cost 属性---见上一文章分析，由 cost 来记录每个顶点相对于初始顶点的路径长度)。因此，获得某顶点的最短路径只需要调用它的getCost方法即可。

 最短路径算法的代码如下，可以看出它和广度优先算法的代码非常的相似，其实就是广度优先算法的应用而已。

public int getShortestPath(T begin, T end, Stack<T> path) {
	resetVertices();//图中顶点的初始化
	boolean done = false;//标记整个遍历过程是否完成
	Queue<VertexInterface<T>> vertexQueue = new LinkedList<>();//辅助队列,保存遍历过程中遇到的顶点
	VertexInterface<T> beginVertex = vertices.get(begin);//获得起始顶点
	VertexInterface<T> endVertex = vertices.get(end);//获得终点,求起始顶点到终点的最短路径
	
	beginVertex.visit();
	vertexQueue.offer(beginVertex);//起始顶点入队列
	//Assertion: resetVertices() 已经对 beginVertex 执行了 setCost(0)
	
	while(!done && !vertexQueue.isEmpty()){//while循环完成后,实际上求得了图中所有顶点相对于初始点的 cost 属性值
		VertexInterface<T> frontVertex = vertexQueue.poll();
		Iterator<VertexInterface<T>> neighbors = frontVertex.getNeighborInterator();
		while(!done && neighbors.hasNext()){//计算 frontVertex的所有邻接顶点的 路径长度
			VertexInterface<T> nextNeighbor = neighbors.next();
			if(!nextNeighbor.isVisited()){
				nextNeighbor.visit();
				nextNeighbor.setPredecessor(frontVertex);//设置frontVertex 的前驱顶点
				nextNeighbor.setCost(frontVertex.getCost() + 1);//该顶点的路径长度是 它的前驱顶点的路径长度+1
				vertexQueue.offer(nextNeighbor);
			}//end if
			
			if(nextNeighbor.equals(endVertex))
				done = true;
		}//end inner while
	}//end outer while. and traverse over
	
	int pathLength = (int)endVertex.getCost();//初始顶点的 cost为 0,每个顶点的 cost 属性记录了它相对于初始顶点的最短长度
	path.push(endVertex.getLabel());
	
	VertexInterface<T> vertex = endVertex;
	while(vertex.hasPredecessor()){
		vertex = vertex.getPredecessor();
		path.push(vertex.getLabel());
	}
	return pathLength;
}

 深度优先遍历算法

在深度优先遍历中，需要两个栈，这里可以看出深度优先遍历带有递归的性质。一个栈用来辅助遍历，即用来保存遍历过程中里面的顶点，另一个栈用来保存遍历的顺序。之所以另外需要一个栈来保存遍历的顺序的原因 与 广度优先遍历 中需要用另一个队列来保存 遍历顺序 的原因相同。当深度优先遍历到某个顶点时，若该顶点的所有邻接点均已经被访问，则发生回溯，即返回去遍历 该顶点 的 前驱顶点 的 未被访问的某个邻接点。

深度优先遍历的代码与广度优先遍历的代码很大的一个不同就是，在while 循环里面，当取出栈顶/队头 顶点时，深度优先是用一个 if 语句 来执行逻辑，而广度优先 则是用一个 while 循环来执行逻辑。

这是因为：对于深度优先而言，访问了 顶点A 时，紧接着只需要找到 顶点A 的一个未被访问的邻接点，再访问该邻接点即可。而对于广度优先，访问了 顶点A 时，就是要寻找 顶点A的 所有未被访问的邻接点，再访问 所有的这些邻接点。

代码对比如下：

while(!vertexStack.isEmpty()){
	VertexInterface<T> topVertex = vertexStack.peek();
	//找到该顶点的一个未被访问的邻接点,从该邻接点出发又去遍历邻接点的邻接点
	VertexInterface<T> nextNeighbor = topVertex.getUnvisitedNeighbor();
	if(nextNeighbor != null){
		nextNeighbor.visit();
		//由于用的是if,在这里push邻接点后,下一次while循环pop的是该邻接点,然后又获得它的邻接点,---DFS
		vertexStack.push(nextNeighbor);
		traversalOrder.offer(nextNeighbor.getLabel());
	}
	else
		vertexStack.pop();//当某顶点的所有邻接点都被访问了时,直接将该顶点pop,这样下一次while pop 时就回溯到前一个顶点
		
/***************************************************/    

while(!vertexQueue.isEmpty()){
	VertexInterface<T> frontVertex = vertexQueue.poll();//出队列,poll()在队列为空时返回null
	Iterator<VertexInterface<T>> neighbors = frontVertex.getNeighborInterator();
	while(neighbors.hasNext())//对于 每个顶点都遍历了它的邻接表,即遍历了所有的边,复杂度为O(E)
	{
		VertexInterface<T> nextNeighbor = neighbors.next();
		if(!nextNeighbor.isVisited()){
			nextNeighbor.visit();//广度优先遍历未访问的顶点
			traversalOrder.offer(nextNeighbor.getLabel());
			vertexQueue.offer(nextNeighbor);//将该顶点的邻接点入队列
		}
	}//end inner while
}//end outer while

整个深度优先遍历算法代码如下：

public Queue<T> getDepthFirstTraversal(T origin) {
resetVertices();//先将所有的顶点初始化--时间复杂度为O(V)
LinkedList<VertexInterface<T>> vertexStack = new LinkedList<>();//辅助DFS递归遍历
Queue<T> traversalOrder = new LinkedList<>();//保存DFS遍历顺序

VertexInterface<T> originVertex = vertices.get(origin);//根据起始顶点的标识获得起始顶点
originVertex.visit();//访问起始顶点,起始顶点的出度不能为0(只考虑多于一个顶点的连通图),若为0,它就没有邻接点了
vertexStack.push(originVertex);//各个顶点的入栈顺序就是DFS的遍历顺序
traversalOrder.offer(originVertex.getLabel());//每当一个顶点入栈时,就将它入队列,从而队列保存了整个遍历顺序

while(!vertexStack.isEmpty()){
    VertexInterface<T> topVertex = vertexStack.peek();
    //找到该顶点的一个未被访问的邻接点,从该邻接点出发又去遍历邻接点的邻接点
    VertexInterface<T> nextNeighbor = topVertex.getUnvisitedNeighbor();//判断所有未被访问的邻接点，也即遍历了所有的边--复杂度O(E)
    if(nextNeighbor != null){
nextNeighbor.visit();
//由于用的是if,在这里push邻接点后,下一次while循环pop的是该邻接点,然后又获得它的邻接点,---DFS
vertexStack.push(nextNeighbor);
traversalOrder.offer(nextNeighbor.getLabel());
    }
    else
vertexStack.pop();//当某顶点的所有邻接点都被访问了时,直接将该顶点pop,这样下一次while pop 时就回溯到前一个顶点
}//end while
return traversalOrder;
    }

深度优先遍历的算法的时间复杂度：O(V+E)--遍历之前，给每个顶点进行初始化时需要遍历所有顶点V，在遍历过程中需要判断顶点的邻接点是否被遍历，也即遍历该顶点的邻接表，邻接表代表的实质是边，边总数为 E，故总的时间复杂度为O(V+E)；空间复杂度：O(V)--用了两个辅助栈

拓扑排序算法

求图的拓扑序列的思路就是：先找到图中一个出度为0的顶点，访问该顶点并将之入栈。访问了该顶点之后，相当于指向该顶点的所有的边都已经被删除了。然后，继续在图中寻找下一个出度为0且未被访问的顶点，直至图中所有的顶点都已被访问。寻找这样的顶点的方法实现如下：

private VertexInterface<T> getNextTopologyOrder(){//最坏情况下复杂度为O(V+E)
	VertexInterface<T> nextVertex = null;
	Iterator<VertexInterface<T>> iterator = vertices.values().iterator();//获得图的顶点的迭代器
	boolean found = false;
	while(!found && iterator.hasNext()){
		nextVertex = iterator.next();
		//寻找出度为0且未被访问的顶点
		if(nextVertex.isVisited() == false && nextVertex.getUnvisitedNeighbor() == null)
			found = true;
	}
	return nextVertex;
}

图的拓扑排序实现代码如下：

public Stack<T> getTopologicalSort() {
	/**
	 *相比于《算法导论》中的拓扑排序借助了DFS复杂度为O(V+E),该算法的时间复杂度较大
	 *因为算法导论中介绍的图的数据结构与此处实现的图的数据结构不同
	 *此算法的最坏时间复杂度为O(V*(V+E))==V * max{V,E}
	*/
	resetVertices();//先将所有的顶点初始化
	
	Stack<T> vertexStack = new Stack<>();//存放已访问的顶点的栈,该栈就是一个拓扑序列
	int numberOfVertices = vertices.size();//获得图中顶点的个数
	
	for(int counter = 1; counter <= numberOfVertices; counter++){
		VertexInterface<T> nextVertex = getNextTopologyOrder();//获得一个未被访问的且出度为0的顶点
		if(nextVertex != null){
			nextVertex.visit();
			vertexStack.push(nextVertex.getLabel());//遍历完成后,出栈就可以获得图的一个拓扑序列
		}
	}
	return vertexStack;
}

此拓扑排序算法实现的最坏情况下时间复杂度为：O(V*max(V,E))；空间复杂度为：O(V)--定义一个辅助栈来保存遍历顺序

分析：

本文实现了有向无环图及四个常用的图的遍历算法，在客户程序中只需要 new 一个图对象，然后就可以调用这些算法了。数据结构与算法是紧密相关的，算法实现的难易程序及好坏依赖于你所设计的数据结构。