图的深度和广度.doc

图的深度优先遍历和广度优先遍历 Java实现 收藏 一 图的基本概念及存储结构图G是由顶点的有穷集合，以及顶点之间的关系组成，顶点的集合记为V，顶点之间的关系构成边的集合EG=(V,E).说一条边从v1,连接到v2,那么有v1Ev2(E是V上的一个关系）=E.图有有向图，无向图之分，无向图的一条边相当于有向图的中两条边，即如果无向图的顶点v1和v2之间有一条边，那么既有从v1连接到v2的边，也有从v2连接到v1的边，E 并且E，而有向图是严格区分方向的。一般图的存储有两种方式1）相邻矩阵，用一个矩阵来保持边的情况，E则Matrixv1v2=Weight.2）邻接表，需要保存一个顺序存储的顶点表和每个顶点上的边的链接表。这里的实现采用第二种方案，另外图又复杂图，简单图之分，复杂图可能在两点之间同一个方向有多条边，我们考虑的都是无环简单图，无环简单图是指顶点没有自己指向自己的边的简单图，即任取vi属于V = 不属于E并且没有重复边。我们先给出图的ADT:package algorithms.graph;/* * The Graph ADT * author yovn * */public interface Graph /mark public static interface Edge public int getWeight(); int vertexesNum(); int edgeNum(); boolean isEdge(Edge edge); void setEdge(int from,int to, int weight); Edge firstEdge(int vertex); Edge nextEdge(Edge edge); int toVertex(Edge edge); int fromVertex(Edge edge); String getVertexLabel(int vertex); void assignLabels(String labels); void deepFirstTravel(GraphVisitor visitor); void breathFirstTravel(GraphVisitor visitor); 其中的方法大多数比较一目了然，其中1）Edge firstEdge(int vertex)返回指定节点的边的链表里存的第一条边2）Edge nextEdge(Edge edge)，顺着边链表返回下一条边3）fromVertex,toVertex很简单返回该边的起始顶点和终结顶点4）getVertexLabel返回该定点对应的标号,assignLabels给所有顶点标上号GraphVisitor是一个很简单的接口：package algorithms.graph;/* * author yovn *- */public interface GraphVisitor void visit(Graph g,int vertex);OK，下面是该部分实现：package algorithms.graph;import java.util.Arrays;/* * author yovn * */public class DefaultGraph implements Graph private static class _Edge implements Edge private static final _Edge NullEdge=new _Edge(); int from; int to; int weight; _Edge nextEdge; private _Edge() weight=Integer.MAX_VALUE; _Edge(int from, int to, int weight) this.from=from; this.to=to; this.weight=weight; public int getWeight() return weight; private static class _EdgeStaticQueue _Edge first; _Edge last; private int numVertexes; private String labels; private int numEdges; private _EdgeStaticQueue edgeQueues; /tag the specified vertex be visited or not private boolean visitTags; /* * */ public DefaultGraph(int numVertexes) if(numVertexes1) throw new IllegalArgumentException(); this.numVertexes=numVertexes; this.visitTags=new booleannumVertexes; this.labels=new StringnumVertexes; for(int i=0;inumVertexes;i+) labelsi=i+; this.edgeQueues=new _EdgeStaticQueuenumVertexes; for(int i=0;i=numVertexes) throw new IllegalArgumentException(); return edgeQueuesvertex.first; /* (non-Javadoc) * see algorithms.graph.Graph#isEdge(algorithms.graph.Graph.Edge) */ Override public boolean isEdge(Edge edge) return (edge!=_Edge.NullEdge); /* (non-Javadoc) * see algorithms.graph.Graph#nextEdge(algorithms.graph.Graph.Edge) */ Override public Edge nextEdge(Edge edge) return (_Edge)edge).nextEdge; /* (non-Javadoc) * see algorithms.graph.Graph#vertexesNum() */ Override public int vertexesNum() return numVertexes; Override public int fromVertex(Edge edge) return (_Edge)edge).from; Override public void setEdge(int from, int to, int weight) /we dont allow ring exist if(from=numVertexes|to=numVertexes|weight0|from=to)throw new IllegalArgumentException(); _Edge edge=new _Edge(from,to,weight); edge.nextEdge=_Edge.NullEdge; if(edgeQueuesfrom.first=_Edge.NullEdge) edgeQueuesfrom.first=edge; else edgeQueuesfrom.last.nextEdge=edge; edgeQueuesfrom.last=edge; Override public int toVertex(Edge edge) return (_Edge)edge).to; Override public String getVertexLabel(int vertex) return labelsvertex; Override public void assignLabels(String labels) System.arraycopy(labels, 0, this.labels, 0, labels.length); /to be continue二 深度优先周游即从从某一点开始能继续往前就往前不能则回退到某一个还有边没访问的顶点，沿这条边看该边指向的点是否已访问，如果没有访问，那么从该指向的点继续操作。那么什么时候结束呢，这里我们在图的ADT实现里加上一个标志数组。该数组记录某一顶点是否已访问，如果找不到不到能继续往前访问的未访问点，则结束。你可能会问，如果指定图不是连通图（既有2个以上的连通分量）呢?OK,解决这个问题，我们可以让每一个顶点都有机会从它开始周游。下面看deepFirstTravel的实现： /* (non-Javadoc) * see algorithms.graph.Graph#deepFirstTravel(algorithms.graph.GraphVisitor) */ Override public void deepFirstTravel(GraphVisitor visitor) Arrays.fill(visitTags, false);/reset all visit tags for(int i=0;inumVertexes;i+) if(!visitTagsi)do_DFS(i,visitor); private final void do_DFS(int v, GraphVisitor visitor) /first visit this vertex visitor.visit(this, v); visitTagsv=true; /for each edge from this vertex, we do one time /and this for loop is very classical in all graph algorithms for(Edge e=firstEdge(v);isEdge(e);e=nextEdge(e) if(!visitTagstoVertex(e) do_DFS(toVertex(e),visitor); 三 广度优先周游广度优先周游从每个指定顶点开始，自顶向下一层一层的访问。上一层所有顶点访问完了才继续下一层的访问。可以把二叉树的广度优先周游看成图的广度优先周游的特例。（二叉树是连通的无回路的有向图，也是一棵根树）同样，广度优先也要借助与一个队列来存储待访问顶点下面是breathFirstTravel的实现，为了减小Java库的影响，我自己实现一个很简单的队列。（你也可以使用ArrayList,但是记住队列的定义，只能在头删除，在尾插入）：private static class _IntQueue private static class _IntQueueNode _IntQueueNode next; int value; _IntQueueNode first; _IntQueueNode last; /queue can only insert to the tail void add(int i) _IntQueueNode node=new _IntQueueNode(); node.value=i; node.next=null; if(first=null)first=node; else last.next=node; last=node; boolean isEmpty() return first=null; /queue can only remove from the head int remove() int val=first.value; if(first=last) first=last=null; else first=first.next; return val; /* (non-Javadoc) * see algorithms.graph.Graph#breathFirstTravel(algorithms.graph.GraphVisitor) */ Override public void breathFirstTravel(GraphVisitor visitor) Arrays.fill(visitTags, false);/reset all visit tags for(int i=0;inumVertexes;i+) if(!visitTagsi) do_BFS(i,visitor); private void do_BFS(int v, GraphVisitor visitor) /and BFS will use an queue to keep the unvisited vertexes / we can also just use java.util.ArrayList _IntQueue queue=new _IntQueue(); queue.add(v); while(!queue.isEmpty() int fromV=queue.remove(); visitor.visit(this, fromV); visitTagsfromV=true; for(Edge e=firstEdge(fromV);isEdge(e);e=nextEdge(e) if(!visitTagstoVertex(e) queue.add(toVertex(e); OK，最后我们测试一下：/* * param args */ public static void main(String args) /* * For example, we have a graph: * 012 * * 3 4 5 * * 678 * * here ,all weight is 0, its a DAG(Dire