- 深度优先搜索（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<MAX_VRERTS;j++)
for(int k = 0;k<MAX_VRERTS;k++)
adjMat[j][k] = 0;
theaStack = new StackX();
}
/**
* @param lab
*/
public void addVertex(char lab){
vertxList[nVert++] = new Vertx(lab);
}
/**
* @param start
* @param end
* 邻接矩阵，添加执行的
*/
public void addEdge(int start,int end){
adjMat[start][end] = 1;
adjMat[end][start] = 1;
}
/**
* @param v
* 展示节点数值
*/
public void display(int v){
System.out.println(vertxList[v].lable);
}
/**
* 深度优先搜索
* 1、使用peek方法获取栈顶2、试图找到这个栈顶还未访问的邻接点
* 3、如果没有找到出栈 4、如果找到则把这个节点push到栈中
*/
public void dfs(){
vertxList[0].wasVisited = true;//顶点标记为已读
display(0);
//初始一个栈顶为0
theaStack.push(0);
//只要不为空，就继续搜索
while(!theaStack.isEmpty()){
//theaStack.peek获取当前的顶点
int v = getAdjUnivisitedVertx(theaStack.peek());
if(v == -1){
theaStack.pop();
}
else{
vertxList[v].wasVisited = true;
display(v);
theaStack.push(v);
}
}//重置标志位
for(int j=0;j<nVert;j++){
vertxList[j].wasVisited = false;
}
}
/**
* 深度优先算法实现最小生成树
*/
public void mst(){
vertxList[0].wasVisited = true;
theaStack.push(0);
while(! theaStack.isEmpty()){
int curentVertx = theaStack.peek();
int v = getAdjUnivisitedVertx(curentVertx);
//表示已经没有邻接点
if(v == -1){
theaStack.pop();
}else{
vertxList[v].wasVisited = true;
theaStack.push(v);
//这里是最小生成树保存
display(curentVertx);//起点
display(v);//终点
}
for(int i=0;i<nVert;i++)
vertxList[i].wasVisited = true;
}
}
/**
* @param v
* @return
* 深度优先算法关键是找到邻接且没有被访问过的点。
*/
public int getAdjUnivisitedVertx(int v){
for(int i=0;i<nVert;i++){
if(adjMat[v][i] == 1 &&vertxList[i].wasVisited == false)
return i;
}
return -1;
}
}
/**
* <p>Title: ${file_name}</p>
* <p>Description: </p>
* <p>Copyright: Copyright (c) 2013</p>
*
* @author xiongzhenggang
* @version 1.0
* @date ${date}
*/
public class TaskUtil {
private TaskUtil() {}
public static List<String> divide(int totalSize, int persize) {
List<String> parts = new ArrayList<String>();
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<num; i++) {
int start = persize*i;
int end = persize*i+persize;
if (end > totalSize) {
end = totalSize;
}
parts.add(start + ":" + end);
}
return parts;
}
public static <T> List<T> getSubList(List<T> 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);
}
}
