package com.wly.algorithmbase.datastructure;
/** 
 * 無(wú)向圖 
 * @author wly 
 * 
 */
public class NoDirectionGraph {
	private int mMaxSize;
	//圖中包含的最大頂點(diǎn)數(shù) 
	private GraphVertex[] vertexList;
	//頂點(diǎn)數(shù)組 
	private int[][] indicatorMat;
	//指示頂點(diǎn)之間的連通關(guān)系的鄰接矩陣 
	private int nVertex;
	//當(dāng)前實(shí)際保存的頂點(diǎn)數(shù)目 
	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("---插入失敗，頂點(diǎn)數(shù)量已達(dá)上限!");
		}
	}
	/** 
   * 修改鄰接矩陣，添加新的邊 
   * @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();
		}
	}
	/** 
   * 深度優(yōu)先遍歷 
   * @param vertexIndex 表示要遍歷的起點(diǎn),即圖的鄰接矩陣中的行數(shù) 
   */
	public void DFS(int vertexIndex) {
		ArrayStack stack = new ArrayStack();
		//1.添加檢索元素到棧中 
		vertexList[vertexIndex].setVisited(true);
		stack.push(vertexIndex);
		int nextVertexIndex = getNextVertexIndex(vertexIndex);
		while(!stack.isEmpty()) {
			//不斷地壓棧、出棧，直到棧為空(檢索元素也沒(méi)彈出了棧)為止 
			if(nextVertexIndex != -1) {
				vertexList[nextVertexIndex].setVisited(true);
				stack.push(nextVertexIndex);
				stack.printElems();
			} else {
				stack.pop();
			}
			//檢索當(dāng)前棧頂元素是否包含其他未遍歷過(guò)的節(jié)點(diǎn) 
			if(!stack.isEmpty()) {
				nextVertexIndex = getNextVertexIndex(stack.peek());
			}
		}
	}
	/** 
   * 得到當(dāng)前頂點(diǎn)的下一個(gè)頂點(diǎn)所在行 
   * @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;
	}
	/** 
   * 廣度優(yōu)先遍歷 
   * @param vertexIndex 表示要遍歷的起點(diǎn),即圖的鄰接矩陣中的行數(shù) 
   */
	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;
/** 
 * 使用數(shù)組實(shí)現(xiàn)棧結(jié)構(gòu) 
 * @author wly 
 * 
 */
public class ArrayStack {
	private int[] tArray;
	private int topIndex = -1;
	//表示當(dāng)前棧頂元素的索引位置 
	private int CAPACITY_STEP = 12;
	//數(shù)組容量擴(kuò)展步長(zhǎng) 
	public ArrayStack() {
		/***創(chuàng)建泛型數(shù)組的一種方法***/
		tArray = new int[CAPACITY_STEP];
	}
	/** 
   * 彈出棧頂元素方法 
   * @return 
   */
	public int pop() {
		if(isEmpty()) {
			System.out.println("錯(cuò)誤，棧中元素為空，不能pop");
			return -1;
		} else {
			int i = tArray[topIndex];
			tArray[topIndex--] = -1;
			//擦除pop元素 
			return i;
		}
	}
	/** 
   * 向棧中插入一個(gè)元素 
   * @param t 
   */
	public void push(int t) {
		//檢查棧是否已滿 
		if(topIndex == (tArray.length-1)) {
			//擴(kuò)展容量 
			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("錯(cuò)誤，棧中元素為空，不能peek");
			return -1;
		} else {
			return tArray[topIndex];
		}
	}
	/** 
   * 判斷當(dāng)前棧是否為空 
   * @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;
/** 
 * 使用鏈表實(shí)現(xiàn)隊(duì)列 
 * 
 * @author wly 
 * 
 */
public class ChainQueue {
	private QueueNode head;
	// 指向隊(duì)列頭節(jié)點(diǎn) 
	private QueueNode tail;
	// 指向隊(duì)列尾節(jié)點(diǎn) 
	private int size = 0;
	// 隊(duì)列尺寸 
	public ChainQueue() {
	}
	/** 
   * 插入新節(jié)點(diǎn)到隊(duì)列尾 
   */
	public void insert(QueueNode node) {
		// 當(dāng)然也可以這么寫(xiě),添加tail.prev = node 
		if (head == null) {
			head = node;
			tail = head;
		} else {
			node.next = tail;
			tail.prev = node;
			// 雙向連接，確保head.prev不為空 
			tail = node;
		}
		size++;
	}
	/** 
   * 移除隊(duì)列首節(jié)點(diǎn) 
   */
	public QueueNode remove() {
		if (!isEmpty()) {
			QueueNode temp = head;
			head = head.prev;
			size--;
			return temp;
		} else {
			System.out.println("異常操作，當(dāng)前隊(duì)列為空!");
			return null;
		}
	}
	/** 
   * 隊(duì)列是否為空 
   * 
   * @return 
   */
	public Boolean isEmpty() {
		if (size > 0) {
			return false;
		} else {
			return true;
		}
	}
	/** 
   * 返回隊(duì)列首節(jié)點(diǎn)，但不移除 
   */
	public QueueNode peek() {
		if (!isEmpty()) {
			return head;
		} else {
			System.out.println();
			System.out.println("異常操作，當(dāng)前隊(duì)列為空!");
			return null;
		}
	}
	/** 
   * 返回隊(duì)列大小 
   * 
   * @return 
   */
	public int size() {
		return size;
	}
	/** 
   * 打印隊(duì)列中的元素 
   */
	public void printElems() {
		QueueNode tempNode = head;
		while(tempNode != null) {
			System.out.print(tempNode.data + " ");
			tempNode = tempNode.prev;
		}
		System.out.println();
	}
}
/** 
 * 節(jié)點(diǎn)類 
 * 
 * @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;
/** 
 * 基于圖的深度優(yōu)先搜索 
 * @author wly 
 * 
 */
public class Test_BFS_DFS {
	public static void main(String[] args) {
		//初始化測(cè)試數(shù)據(jù) 
		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();
		//測(cè)試深搜 
		System.out.println("--深度優(yōu)先搜索--");
		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("--廣度優(yōu)先搜索--");
		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  
--深度優(yōu)先搜索-- 
0 1  
0 1 3  
0 1 3 6  
0 1 4  
0 2  
0 2 5  
--廣度優(yōu)先搜索-- 
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