《图的深度和广度》由会员分享，可在线阅读，更多相关《图的深度和广度（10页珍藏版）》请在金锄头文库上搜索。
1、图的深度优先遍历和广度优先遍历 Java 实现 收藏 一 图的基本概念及存储结构图 G 是由顶点的有穷集合，以及顶点之间的关系组成，顶点的集合记为 V，顶点之间的关系构成边的集合 EG=(V,E).说一条边从 v1,连接到 v2,那么有 v1Ev2(E 是 V 上的一个关系） =E.图有有向图，无向图之分，无向图的一条边相当于有向图的中两条边，即如果无向图的顶点 v1 和 v2 之间有一条边，那么既有从 v1 连接到 v2 的边，也有从 v2 连接到 v1 的边，E 并且E，而有向图是严格区分方向的。一般图的存储有两种方式1）相邻矩阵，用一个矩阵来保持边的情况，E 则 Matrixv1v2=W
2、eight.2）邻接表，需要保存一个顺序存储的顶点表和每个顶点上的边的链接表。这里的实现采用第二种方案，另外图又复杂图，简单图之分，复杂图可能在两点之间同一个方向有多条边，我们考虑的都是无环简单图，无环简单图是指顶点没有自己指向自己的边的简单图，即任取 vi 属于 V = 不属于 E 并且没有重复边。我们先给出图的 ADT:package algorithms.graph;/* The Graph ADT* author yovn*/public interface Graph /markpublic static interface Edgepublic int getWeight();in
3、t 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(GraphVisito
4、r 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;/* auth
5、or 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;i
6、nt 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 n
7、umEdges;private _EdgeStaticQueue edgeQueues;/tag the specified vertex be visited or not private boolean visitTags;/* */public DefaultGraph(int numVertexes) if(numVertexes=numVertexes) throw new IllegalArgumentException();return edgeQueuesvertex.first;/* (non-Javadoc)* see algorithms.graph.Graph#isEd
8、ge(algorithms.graph.Graph.Edge)*/Overridepublic boolean isEdge(Edge edge) return (edge!=_Edge.NullEdge);/* (non-Javadoc)* see algorithms.graph.Graph#nextEdge(algorithms.graph.Graph.Edge)*/Overridepublic Edge nextEdge(Edge edge) return (_Edge)edge).nextEdge;/* (non-Javadoc)* see algorithms.graph.Grap
9、h#vertexesNum()*/Overridepublic int vertexesNum() return numVertexes;Overridepublic int fromVertex(Edge edge) return (_Edge)edge).from;Overridepublic void setEdge(int from, int to, int weight) /we dont allow ring exist if(from=numVertexes|to=numVertexes|weight0|from=to)throw new IllegalArgumentExcep
10、tion();_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;Overridepublic int toVertex(Edge edge) return (_Edge)edge).to;Overridepublic String getVertexLabel
11、(int vertex) return labelsvertex;Overridepublic void assignLabels(String labels) System.arraycopy(labels, 0, this.labels, 0, labels.length);/to be continue二 深度优先周游即从从某一点开始能继续往前就往前不能则回退到某一个还有边没访问的顶点，沿这条边看该边指向的点是否已访问，如果没有访问，那么从该指向的点继续操作。那么什么时候结束呢，这里我们在图的 ADT 实现里加上一个标志数组。该数组记录某一顶点是否已访问，如果找不到不到能继续往前访问的未
12、访问点，则结束。你可能会问，如果指定图不是连通图（既有 2 个以上的连通分量）呢?OK,解决这个问题，我们可以让每一个顶点都有机会从它开始周游。下面看 deepFirstTravel 的实现： /* (non-Javadoc)* see algorithms.graph.Graph#deepFirstTravel(algorithms.graph.GraphVisitor)*/Overridepublic void deepFirstTravel(GraphVisitor visitor) Arrays.fill(visitTags, false);/reset all visit tagsf
13、or(int i=0;inumVertexes;i+)if(!visitTagsi)do_DFS(i,visitor);private final void do_DFS(int v, GraphVisitor visitor) /first visit this vertexvisitor.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 algorithmsfor(Edge e=firs
14、tEdge(v);isEdge(e);e=nextEdge(e)if(!visitTagstoVertex(e)do_DFS(toVertex(e),visitor);三 广度优先周游广度优先周游从每个指定顶点开始，自顶向下一层一层的访问。上一层所有顶点访问完了才继续下一层的访问。可以把二叉树的广度优先周游看成图的广度优先周游的特例。（二叉树是连通的无回路的有向图，也是一棵根树）同样，广度优先也要借助与一个队列来存储待访问顶点下面是 breathFirstTravel 的实现，为了减小 Java 库的影响，我自己实现一个很简单的队列。（你也可以使用ArrayList,但是记住队列的定义，只能在
15、头删除，在尾插入）：private static class _IntQueueprivate static class _IntQueueNode_IntQueueNode next;int value;_IntQueueNode first;_IntQueueNode last;/queue can only insert to the tailvoid add(int i)_IntQueueNode node=new _IntQueueNode();node.value=i;node.next=null;if(first=null)first=node;else last.next=no
16、de;last=node;boolean isEmpty()return first=null;/queue can only remove from the headint remove()int val=first.value;if(first=last)first=last=null;elsefirst=first.next;return val;/* (non-Javadoc)* see algorithms.graph.Graph#breathFirstTravel(algorithms.graph.GraphVisitor)*/Overridepublic void breathFir
