数据结构java语言描述第（一）篇---图的遍历

2019-11-09 15:51:52

字体：大中小

来源：转载

供稿：网友

图的遍历，所谓遍历，即是对结点的访问。一般有两种访问策略：深度优先遍历，广度优先遍历。

一、深度优先遍历

1、主要思想

首先使用一个未走到过的顶点作为起始顶点，比如V0定点作为起始顶点，沿着V0定点的边访问其他未走到过的定点，首先发现V1(第一个邻接结点)还没有走到过，那么来到V1顶点，再以V1顶点作为起始顶点尝试访问其他未走到过的顶点，以此类推，当发现有一个定点不能访问到其他顶点了，需要回到上一次顶点，按照这个方法，最终遍历完整个图。显然深度优先遍历是沿着图的某一条分支遍历直到末端，然后回溯，再沿着另一条分支进行同样的访问。总结起来可以这样说：每次都在访问完当前结点后首先访问当前结点的第一个邻接结点。上图所访问的顺序是：V0–>V1–>V2–>V3–>V4–>V5–>V6–>V7–>V8

2、图的创建

通常图的存储需要用一个二维数组来存储。现在把上面的图创建出来。

public class Graph { /** * 两个顶点之间不可达 */ PRivate static final int MAX_WEIGHT=10000; /** * 顶点数量 */ private int vertexSize; /** * 顶点数组 */ private int []vertexs; private int [][]matrix; /** * 标记一个定点是否访问过 */ private boolean []book; public void init(int vertexSize) { this.vertexSize = vertexSize; this.vertexs=new int[vertexSize]; this.matrix=new int [vertexSize][vertexSize]; this.book=new boolean[vertexSize]; for(int i=0;i<vertexSize;i++){ vertexs[i]=i; } } public static Graph createGraph(int pVertexSize){ Graph graph=new Graph(); graph.init(pVertexSize); int [] a1 = new int[]{0,10,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,11,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT}; int [] a2 = new int[]{10,0,18,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,16,MAX_WEIGHT,12}; int [] a3 = new int[]{MAX_WEIGHT,MAX_WEIGHT,0,22,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,8}; int [] a4 = new int[]{MAX_WEIGHT,MAX_WEIGHT,22,0,20,MAX_WEIGHT,MAX_WEIGHT,16,21}; int [] a5 = new int[]{MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,20,0,26,MAX_WEIGHT,7,MAX_WEIGHT}; int [] a6 = new int[]{11,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,26,0,17,MAX_WEIGHT,MAX_WEIGHT}; int [] a7 = new int[]{MAX_WEIGHT,16,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,17,0,19,MAX_WEIGHT}; int [] a8 = new int[]{MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,16,7,MAX_WEIGHT,19,0,MAX_WEIGHT}; int [] a9 = new int[]{MAX_WEIGHT,12,8,21,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,0}; graph.matrix[0] = a1; graph.matrix[1] = a2; graph.matrix[2] = a3; graph.matrix[3] = a4; graph.matrix[4] = a5; graph.matrix[5] = a6; graph.matrix[6] = a7; graph.matrix[7] = a8; graph.matrix[8] = a9; return graph; }}

3、图的深度优先遍历

在真正遍历之前，要先写两个方法，用来获取某个顶点的第一个邻接点、根据前一个邻接点的下标来取得下一个邻接点

/** * 获取某个顶点的第一个邻接点 * @param pIndex * @return */ public int getFirstNeighbor(int pIndex){ //顶点pIndex到其他顶点时候可达 for(int i=0;i<vertexSize;i++){ if(matrix[pIndex][i]>0&&matrix[pIndex][i]<MAX_WEIGHT){ return i; } } return -1; } /** * 根据前一个邻接点的下标来取得下一个邻接点 * @param v 表示要找的顶点 * @param index 表示该顶点相对于哪个邻接点去获取下一个邻接点 * @return */ public int getNextNeighbor(int v,int index){ for (int i = index+1; i < vertexSize; i++) { if(matrix[v][i]>0&&matrix[v][i]<MAX_WEIGHT){ return i; } } return -1; } /** * 深度优先遍历算法 * @param i */ private void depthFirstSearch(int i){ book[i]=true; int w = getFirstNeighbor(i); while(w!=-1){ if(!book[w]){ System.out.println("访问到了"+w+"定点"); depthFirstSearch(w); } w=getNextNeighbor(i, w); } } /** * 对外公开的深度优先遍历 */ public void depthFirstSearch(){ for (int i = 0; i <vertexSize; i++) { if(!book[i]){ System.out.println("访问到了"+i+"顶点"); depthFirstSearch(i); } } }

4、测试

public static void main(String[] args) { Graph graph=createGraph(9); graph.depthFirstSearch(); }

打印结果：访问到了0顶点访问到了1定点访问到了2定点访问到了3定点访问到了4定点访问到了5定点访问到了6定点访问到了7定点访问到了8定点

一、广度优先遍历

类似于一个分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的结点的顺序，以便按这个顺序来访问这些结点的邻接结点。

1、主要思想

1、访问初始结点v并标记结点v为已访问。2、结点v入队列3、当队列非空时，继续执行，否则算法结束。4、出队列，取得队头结点u。5、查找结点u的第一个邻接结点w。6、若结点u的邻接结点w不存在，则转到步骤3；否则循环执行以下三个步骤： 1). 若结点w尚未被访问，则访问结点w并标记为已访问。 2). 结点w入队列 3). 查找结点u的继w邻接结点后的下一个邻接结点w，转到步骤6。

2、图的广度优先遍历

public void broadFirstSearch(){ book = new boolean[vertexSize]; for(int i =0;i<vertexSize;i++){ if(!book[i]){ broadFirstSearch(i); } } } /** * 实现广度优先遍历 * @param i */ private void broadFirstSearch(int i) { int u,w; LinkedList<Integer> queue = new LinkedList<Integer>(); System.out.println("访问到："+i+"顶点"); book[i] = true; queue.add(i);//第一次把v0加到队列 while(!queue.isEmpty()){ u = (Integer)(queue.removeFirst()).intValue(); w = getFirstNeighbor(u); while(w!=-1){ if(!book[w]){ System.out.println("访问到了："+w+"顶点"); book[w] = true; queue.add(w); } w = getNextNeighbor(u, w); } } }