深度优先算法与最小生成树

• 深度优先搜索（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);
    }

}