package com.wly.algorithmbase.datastructure;
/** 
 * 无向图 
 * @author wly 
 * 
 */
public class NoDirectionGraph {
 private int mMaxSize;
 //图中包含的最大顶点数 
 private GraphVertex[] vertexList;
 //顶点数组 
 private int[][] indicatorMat;
 //指示顶点之间的连通关系的邻接矩阵 
 private int nVertex;
 //当前实际保存的顶点数目 
 public NoDirectionGraph(int maxSize) {
  mMaxSize = maxSize;
  vertexList = new GraphVertex[mMaxSize];
  indicatorMat = new int[mMaxSize][mMaxSize];
  nVertex = 0;
  //初始化邻接矩阵元素为0 
  for (int j=0;j<mMaxSize;j++) {
   for (int k=0;k<mMaxSize;k++) {
    indicatorMat[j][k] = 0;
   }
  }
 }
 public void addVertex(GraphVertex v) {
  if(nVertex < mMaxSize) {
   vertexList[nVertex++] = v;
  } else {
   System.out.println("---插入失败，顶点数量已达上限!");
  }
 }
 /** 
   * 修改邻接矩阵，添加新的边 
   * @param start 
   * @param end 
   */
 public void addEdge(int start,int end) {
  indicatorMat[start][end] = 1;
  indicatorMat[end][start] = 1;
 }
 /** 
   * 打印邻接矩阵 
   */
 public void printIndicatorMat() {
  for (int[] line:indicatorMat) {
   for (int i:line) {
    System.out.print(i + " ");
   }
   System.out.println();
  }
 }
 /** 
   * 深度优先遍历 
   * @param vertexIndex 表示要遍历的起点,即图的邻接矩阵中的行数 
   */
 public void DFS(int vertexIndex) {
  ArrayStack stack = new ArrayStack();
  //1.添加检索元素到栈中 
  vertexList[vertexIndex].setVisited(true);
  stack.push(vertexIndex);
  int nextVertexIndex = getNextVertexIndex(vertexIndex);
  while(!stack.isEmpty()) {
   //不断地压栈、出栈，直到栈为空(检索元素也没弹出了栈)为止 
   if(nextVertexIndex != -1) {
    vertexList[nextVertexIndex].setVisited(true);
    stack.push(nextVertexIndex);
    stack.printElems();
   } else {
    stack.pop();
   }
   //检索当前栈顶元素是否包含其他未遍历过的节点 
   if(!stack.isEmpty()) {
    nextVertexIndex = getNextVertexIndex(stack.peek());
   }
  }
 }
 /** 
   * 得到当前顶点的下一个顶点所在行 
   * @param column 
   * @return 
   */
 public int getNextVertexIndex(int column) {
  for (int i=0;i<indicatorMat[column].length;i++) {
   if(indicatorMat[column][i] == 1 && !vertexList[i].isVisited()) {
    return i;
   }
  }
  return -1;
 }
 /** 
   * 广度优先遍历 
   * @param vertexIndex 表示要遍历的起点,即图的邻接矩阵中的行数 
   */
 public void BFS(int vertexIndex) {
  ChainQueue queue = new ChainQueue();
  vertexList[vertexIndex].setVisited(true);
  queue.insert(new QueueNode(vertexIndex));
  int nextVertexIndex = getNextVertexIndex(vertexIndex);
  while(!queue.isEmpty()) {
   if(nextVertexIndex != -1) {
    vertexList[nextVertexIndex].setVisited(true);
    queue.insert(new QueueNode(nextVertexIndex));
   } else {
    queue.remove();
   }
   if(!queue.isEmpty()) {
    nextVertexIndex = getNextVertexIndex(queue.peek().data);
    queue.printElems();
   }
  }
 }
}

package com.wly.algorithmbase.datastructure;
/** 
 * 使用数组实现栈结构 
 * @author wly 
 * 
 */
public class ArrayStack {
 private int[] tArray;
 private int topIndex = -1;
 //表示当前栈顶元素的索引位置 
 private int CAPACITY_STEP = 12;
 //数组容量扩展步长 
 public ArrayStack() {
  /***创建泛型数组的一种方法***/
  tArray = new int[CAPACITY_STEP];
 }
 /** 
   * 弹出栈顶元素方法 
   * @return 
   */
 public int pop() {
  if(isEmpty()) {
   System.out.println("错误，栈中元素为空，不能pop");
   return -1;
  } else {
   int i = tArray[topIndex];
   tArray[topIndex--] = -1;
   //擦除pop元素 
   return i;
  }
 }
 /** 
   * 向栈中插入一个元素 
   * @param t 
   */
 public void push(int t) {
  //检查栈是否已满 
  if(topIndex == (tArray.length-1)) {
   //扩展容量 
   int[] tempArray = new int[tArray.length + CAPACITY_STEP];
   for (int i=0;i<tArray.length;i++) {
    tempArray[i] = tArray[i];
   }
   tArray = tempArray;
   tempArray = null;
  } else {
   topIndex ++;
   tArray[topIndex] = t;
  }
 }
 /** 
   * 得到栈顶元素，但不弹出 
   * @return 
   */
 public int peek() {
  if(isEmpty()) {
   System.out.println("错误，栈中元素为空，不能peek");
   return -1;
  } else {
   return tArray[topIndex];
  }
 }
 /** 
   * 判断当前栈是否为空 
   * @return 
   */
 public Boolean isEmpty() {
  return (topIndex < 0);
 }
 /** 
   * 打印栈中元素 
   */
 public void printElems() {
  for (int i=0;i<=topIndex;i++) {
   System.out.print(tArray[i] + " ");
  }
  System.out.println();
 }
}

package com.wly.algorithmbase.datastructure;
/** 
 * 使用链表实现队列 
 * 
 * @author wly 
 * 
 */
public class ChainQueue {
 private QueueNode head;
 // 指向队列头节点 
 private QueueNode tail;
 // 指向队列尾节点 
 private int size = 0;
 // 队列尺寸 
 public ChainQueue() {
 }
 /** 
   * 插入新节点到队列尾 
   */
 public void insert(QueueNode node) {
  // 当然也可以这么写,添加tail.prev = node 
  if (head == null) {
   head = node;
   tail = head;
  } else {
   node.next = tail;
   tail.prev = node;
   // 双向连接，确保head.prev不为空 
   tail = node;
  }
  size++;
 }
 /** 
   * 移除队列首节点 
   */
 public QueueNode remove() {
  if (!isEmpty()) {
   QueueNode temp = head;
   head = head.prev;
   size--;
   return temp;
  } else {
   System.out.println("异常操作，当前队列为空!");
   return null;
  }
 }
 /** 
   * 队列是否为空 
   * 
   * @return 
   */
 public Boolean isEmpty() {
  if (size > 0) {
   return false;
  } else {
   return true;
  }
 }
 /** 
   * 返回队列首节点，但不移除 
   */
 public QueueNode peek() {
  if (!isEmpty()) {
   return head;
  } else {
   System.out.println();
   System.out.println("异常操作，当前队列为空!");
   return null;
  }
 }
 /** 
   * 返回队列大小 
   * 
   * @return 
   */
 public int size() {
  return size;
 }
 /** 
   * 打印队列中的元素 
   */
 public void printElems() {
  QueueNode tempNode = head;
  while(tempNode != null) {
   System.out.print(tempNode.data + " ");
   tempNode = tempNode.prev;
  }
  System.out.println();
 }
}
/** 
 * 节点类 
 * 
 * @author wly 
 * 
 */
class QueueNode {
 QueueNode prev;
 QueueNode next;
 int data;
 public QueueNode(int data) {
  this.data = data;
 }
 public int getData() {
  return data;
 }
 public void setData(int data) {
  this.data = data;
 }
 @Override 
   public String toString() {
  // TODO Auto-generated method stub 
  super.toString();
  return data + "";
 }
}

package com.wly.algorithmbase.search;
import com.wly.algorithmbase.datastructure.GraphVertex;
import com.wly.algorithmbase.datastructure.NoDirectionGraph;
/** 
 * 基于图的深度优先搜索 
 * @author wly 
 * 
 */
public class Test_BFS_DFS {
 public static void main(String[] args) {
  //初始化测试数据 
  NoDirectionGraph graph = new NoDirectionGraph(7);
  graph.addVertex(new GraphVertex("A"));
  graph.addVertex(new GraphVertex("B"));
  graph.addVertex(new GraphVertex("C"));
  graph.addVertex(new GraphVertex("D"));
  graph.addVertex(new GraphVertex("E"));
  graph.addVertex(new GraphVertex("F"));
  graph.addVertex(new GraphVertex("G"));
  graph.addEdge(0, 1);
  graph.addEdge(0, 2);
  graph.addEdge(1, 3);
  graph.addEdge(1, 4);
  graph.addEdge(3, 6);
  graph.addEdge(2, 5);
  System.out.println("--图的邻接矩阵--");
  graph.printIndicatorMat();
  //测试深搜 
  System.out.println("--深度优先搜索--");
  graph.DFS(0);
  graph = new NoDirectionGraph(7);
  graph.addVertex(new GraphVertex("A"));
  graph.addVertex(new GraphVertex("B"));
  graph.addVertex(new GraphVertex("C"));
  graph.addVertex(new GraphVertex("D"));
  graph.addVertex(new GraphVertex("E"));
  graph.addVertex(new GraphVertex("F"));
  graph.addVertex(new GraphVertex("G"));
  graph.addEdge(0, 1);
  graph.addEdge(0, 2);
  graph.addEdge(1, 3);
  graph.addEdge(1, 4);
  graph.addEdge(3, 6);
  graph.addEdge(2, 5);
  System.out.println("--广度优先搜索--");
  graph.BFS(0);
 }
}

--图的邻接矩阵-- 
0 1 1 0 0 0 0  
1 0 0 1 1 0 0  
1 0 0 0 0 1 0  
0 1 0 0 0 0 1  
0 1 0 0 0 0 0  
0 0 1 0 0 0 0  
0 0 0 1 0 0 0  
--深度优先搜索-- 
0 1  
0 1 3  
0 1 3 6  
0 1 4  
0 2  
0 2 5  
--广度优先搜索-- 
0 1  
0 1 2  
1 2  
1 2 3  
1 2 3 4  
2 3 4  
2 3 4 5  
3 4 5  
3 4 5 6  
4 5 6  
5 6  
6