图的遍历

从图中某一顶点出发访问图中其余顶点，且每一个顶点仅被访问一次

图有2种常见的遍历方式（有向图、无向图都适用）：

1)广度优先搜索（BreadthFirstSearch，BFS），又称为宽度优先搜索、横向优先搜索

2)深度优先遍历(DepthFirstSearch,DFS)

广度优先搜索

1)理解

类似于树的层序遍历

无向图

有向图

无向图，从A点开始

第一层

A

第二层

BCDF

第三层

GEH

所以，最终的遍历顺序：A-B-C-D-F-G-E-H

2）代码实现(请先学习上一篇文章：图(Grapth))：

@Overridepublicvoidbfs(Vbegin,VertexVisitorvisitor){//获取起点VertexV,EbeginVertex=(begin);if(beginVertex==null){return;}//记录已经遍历过的节点SetVertexV,EvisitedVertices=newHashSet();QueueVertexV,Equeue=newLinkedList();//将起点加入队列(beginVertex);while(!()){//获取队列的元素VertexV,Evertex=();//遍历();//已经遍历过的添加到集合中记录下来(vertex);//将该顶点的出度节点或者说以这个顶点为起点的边，遍历，获取到另外端点(edge-{//如果没遍历过就加入到队列中if(!()){();}});}}

深度优先遍历

1）理解

从一个顶点出发，沿着当前顶点的边走到未访问的顶点，直到没有未访问过的顶点时，返回上一个顶点，继续试探别的顶点，直到所有顶点都被访问过

有向图

从A出发，邻接点有BCF

假设下一个访问节点B

那么，ABFHGCDE

在访问到G顶点时候，可以访问的下一个节点有CE

假设是C,那么就是CD，然后返回到G,然后继续访问E

2）代码实现

privatevoiddfs(VertexV,EbeginVertex,VertexVisitorvisitor){StackVertexV,Estack=newStack();//记录已经访问过的节点ListVertexV,EvisitedVertex=newArrayList();(beginVertex);(beginVertex);();while(!()){VertexV,Evertex=();(edge-{//没有访问过的if(!()){(vertex);();();();}});}}