- 首页 > it技术 > >
- 深度优先搜索（DFS），可以被形象的描述为“打破沙锅问到底”，具体一点就是访问一个顶点之后，我继而访问它的下一个邻接的顶点，如此往复，直到当前顶点一被访问或者它不存在邻接的顶点。
以下为深度优先算法的规则
- 规则1、：访问一个邻接的未访问的节点，标记它，并把它放入栈中
- 规则2、当不能执行规则1是，从栈弹出一个顶点
- 规则3、如果不能完成规则1 规则2则完成搜索
对于最小生成树，和深度优先算法相似，具体区别是多一个记录，如下mst方法
/**
*
*/
package com.xzg.heap;
/**
* @author hasee
* @TIME 2017年5月2日
* 1、图的表示，使用临接表或邻接矩阵
* 2、深度优先搜索算法，核心：栈。规则1、：访问一个邻接的未访问的节点，标记它，并把它放入栈中
* 规则2、当不能执行规则1是，从栈弹出一个顶点
* 规则3、如果不能完成规则1 规则2则完成搜索
*/
public class DeepSearch {
//测试
public static void main(String[] args){
Graph theGraph = new Graph();
theGraph.addVertex('A');
theGraph.addVertex('B');
theGraph.addVertex('C');
theGraph.addVertex('D');
theGraph.addVertex('E');
theGraph.addEdge(0, 1);
//ab
theGraph.addEdge(1, 2);
//BC
theGraph.addEdge(0, 3);
//AD
theGraph.addEdge(3, 4);
//DE
theGraph.dfs();
}}
/**
* @author hasee
* @TIME 2017年5月2日
* 简单实现栈
*/
class StackX{
//初始大小
private final int SIZE = 20;
private int[] st;
private int top;
public StackX(){
st = new int[SIZE];
top =-1;
}
public void push(int j){
st[++top] = j;
}
public int pop(){
return st[top--];
}
public int peek(){
return st[top];
}
public boolean isEmpty(){
return top == -1;
}
}
/**
* @author hasee
* @TIME 2017年5月2日
* 作为储存搜索的节点，包括数值和是否访问过的标志位
*/
class Vertx{
public char lable;
public boolean wasVisited;
public Vertx(char lab){
this.lable = lab;
this.wasVisited = false;
}
}
class Graph{
private final int MAX_VRERTS = 20;
private Vertx vertxList[];
//包含所有的节点信息
private int adjMat[][];
//邻接矩阵
private int nVert;
//当前vertxList的指向下标
private StackX theaStack;
//初始化
public Graph(){
vertxList = new Vertx[MAX_VRERTS];
adjMat = new int[MAX_VRERTS][MAX_VRERTS];
nVert = 0;
for(int j=0;
j
* Description:
* 【深度优先算法与最小生成树】Copyright: Copyright (c) 2013
*
* @author xiongzhenggang
* @version 1.0
* @date ${date}
*/
public class TaskUtil {private TaskUtil() {}public static List divide(int totalSize, int persize) {
List parts = new ArrayList();
if (totalSize <= 0 || persize <= 0) {
return parts;
}if (persize >= totalSize) {
parts.add("0:" + totalSize);
return parts;
}int num = totalSize / persize + (totalSize % persize == 0 ? 0 : 1);
for (int i=0;
i totalSize) {
end = totalSize;
}
parts.add(start + ":" + end);
}
return parts;
}public static List getSubList(List allKeys, String part) {
int start = Integer.parseInt(part.split(":")[0]);
int end = Integer.parseInt(part.split(":")[1]);
if (end > allKeys.size()) {
end = allKeys.size();
}
return allKeys.subList(start, end);
}}
推荐阅读
