1、深度优先
深度优先遍历也叫深度优先搜索（Depth First Search)他的遍历规则：不断地沿着顶点的深方向遍历， 顶点的深度方向是指他的零界点方向，
如图
image.png
给定一图G=<V,E>用vsitted表示顶点i的访问情况， 则初始情况下所有的visited[i]都为false ， 假设从顶点V0开始遍历， 则下一个遍历点则是顶点V0的第一个邻接点V1，接着遍历V1第一个邻接点V3~~~~~~~~~~一直到所有的顶点都访问过
假如我要以V0作为初始的顶点,
第一步，找最近的一个邻接点，然后一直遍历，
则遍历的顺序为V0-V1-V3，
第二步， 回溯法
当遍历到V3时发觉没有遍历的节点了，因为V3指向的节点只能说V0, V0已经遍历过， 所以没路可走， 这时候回退到V1， 看看V1是否有遍历的节点，V1没有时回退到V0， 看看V0是否有下一个节点遍历，V0还有个V2没有遍历， 则 遍历V2 ，遍历的顺序为V0-V1-V3-V2--V4
代码如下
public class ExampleUnitTest {
@Test
public void test(){
Graph graph = new Graph(5);
//添加图的结构数据
int[] v0 = new int[]{0, 1, 1, MAX_WEIGHT, MAX_WEIGHT};
int[] v1 = new int[]{MAX_WEIGHT, 0, MAX_WEIGHT, 1, MAX_WEIGHT};
int[] v2 = new int[]{MAX_WEIGHT, MAX_WEIGHT, 0, MAX_WEIGHT, MAX_WEIGHT};
int[] v3 = new int[]{1, MAX_WEIGHT, MAX_WEIGHT, 0, MAX_WEIGHT};
int[] v4 = new int[]{MAX_WEIGHT, MAX_WEIGHT, 1, MAX_WEIGHT, 0};
graph.matrix[0] = v0;
graph.matrix[1] = v1;
graph.matrix[2] = v2;
graph.matrix[3] = v3;
graph.matrix[4] = v4;
//深度优先
graph.dfs();
//广度优先
graph.bfs();
}
}
/**
* Created by Jett on 2018/12/21.
*/
public class Graph {
public int[] vertices;//顶点集
public int[][] matrix;//图的边的信息
public int verticesSize;
public static final int MAX_WEIGHT = Integer.MAX_VALUE;
public boolean[] isVisited;
public Graph(int verticesSize) {
this.verticesSize = verticesSize;
vertices = new int[verticesSize];
matrix = new int[verticesSize][verticesSize];
isVisited = new boolean[verticesSize];
for (int i = 0; i < verticesSize; i++) {
vertices[i] = i;
}
}
/**
* 获取第一个邻接点
*/
public int getFirstNeightBor(int v) {
for (int i = 0; i < verticesSize; i++) {
if (matrix[v][i] > 0 && matrix[v][i] != MAX_WEIGHT) {
return i;
}
}
return -1;
}
/**
* 获取到顶点v的邻接点index的下一个邻接点
*/
public int getNextNeightBor(int v, int index) {
for (int i = index + 1; i < verticesSize; i++) {
if (matrix[v][i] > 0 && matrix[v][i] != MAX_WEIGHT) {
return i;
}
}
return -1;
}
/**
* 深度优先(很象二叉树的前序)
*/
public void dfs() {
for (int i = 0; i < verticesSize; i++) {
if (!isVisited[i]) {
System.out.println("viested vertice " + i);
dfs(i);
}
}
}
public void dfs(int i) {
isVisited[i] = true;
int v = getFirstNeightBor(i);
while (v != -1) {
if (!isVisited[v]) {
System.out.println("visted vertice " + v);
dfs(v);
}
v = getNextNeightBor(i, v);
}
}
2、广度优先
广度优先遍历也交广度优先搜索（Breadth First Search）,他的遍历规则为：
1、先访问完当前的顶点的所有邻接点，
2、先访问顶点的邻接点先于后访问顶点的邻接点被访问
具体说， 给的那个上图G=<V,E>，用visited[i]表示顶点i被访问的情况，初始情况下Visited【i]都为false,假如从顶点V0开始遍历， 则是遍历的顺序为V0-V1-V2， 遍历完V0所有的节点之后， 则从邻接点V1开始， 遍历V1下所有的节点，接着就遍历V2所有的节点，如果后面还有很多的话，以此类推。
代码如下
/**
* 广度优先
*/
public void bfs(){
for (int i = 0; i < verticesSize; i++) {
isVisited[i]=false;
}
for (int i = 0; i < verticesSize; i++) {
if(!isVisited[i]){
isVisited[i]=true;
System.out.println("visited vertice:"+ i);
bfs(i);
}
}
}
public void bfs(int i) {
LinkedList<Integer> queue = new LinkedList<>();
//找第一个邻接点
int fn = getFirstNeightBor(i);
if (fn == -1) {
return;
}
if (!isVisited[fn]) {
isVisited[fn] = true;
System.out.println("visted vertice:" + fn);
queue.offer(fn);
}
//开始把后面的邻接点都入队
int next = getNextNeightBor(i, fn);
while (next != -1) {
if (!isVisited[next]) {
isVisited[next] = true;
System.out.println("visted vertice:" + next);
queue.offer(next);
}
next = getNextNeightBor(i, next);
}
//从队列中取出来一个，重复之前的操作
while(!queue.isEmpty()){
int point=queue.poll();//v1 v2
bfs(point);
}
}
网友评论