图的广度优先搜索

1. 原理描述：
   设图G的初始状态是所有顶点均为访问过。以G中任选一顶点V为起点，则描述为：首先访问出发点V，
接着依次访问V的所有邻接点W1,W2,...,Wi，然后再依次访问与W1,W2,...,Wi邻接的所有未曾访问过的
顶点。依次类推，直到图中所有和起点V有路径相同的顶点都已访问为止。此时从V开始搜索过程结束。

2. 算法设计基本步骤：
   (1) 确定图的存储方式。
   (2) 设计搜索过程中的操作，其中包括为输出问题解而进行的存储操作。
   (3) 输出问题的解空间。

3. 一种实现：求从一个城市到另一个城市间经过的城市最少的路线。

package com.maozj.datastruct.graphic;

/**
 * 图的广度优先搜索
 * 
 * @author 毛正吉
 * 
 */
public class BreadthSearch {
	public static void main(String[] args) {
		BreadthSearch s = new BreadthSearch();
		s.set(8);
		s.search();
	}

	private int[][] jz;
	private SQ[] sq;
	private int qh;
	private int qe;
	private int[] visited;

	public BreadthSearch() {
		/** 存储图的邻接矩阵 */
		jz = new int[][] { { 0, 1, 1, 1, 0, 1, 0, 0 },
				{ 1, 0, 0, 0, 0, 1, 0, 0 }, { 1, 0, 0, 1, 1, 0, 0, 0 },
				{ 1, 0, 1, 0, 0, 0, 1, 0 }, { 0, 0, 1, 0, 0, 0, 1, 1 },
				{ 1, 1, 0, 0, 0, 0, 0, 1 }, { 0, 0, 0, 1, 1, 0, 0, 1 },
				{ 0, 0, 0, 0, 1, 1, 1, 0 } };

		/** 队列集合 */
		sq = new SQ[100];

		visited = new int[100];
	}

	public void search() {
		/** 队首 */
		qh = 0;

		/** 队尾 */
		qe = 1;
		
        sq[1] = new SQ();
		sq[1].city = 1;
		sq[1].pre = 0;

		visited[1] = 0;

		/** 当队列不为空 */
		while (qh != qe) {
			/** 节点出队 */
			qh = qh + 1;

			/** 扩展节点 */
			for (int i = 0; i < 8; i++) {
				if (jz[sq[qh].city][i] == 1 && visited[i] == 0) {
					/** 节点入队 */
					qe++;
					sq[qe] = new SQ();
					sq[qe].city = i;
					sq[qe].pre = qh;
					visited[i] = 1;

					if (sq[qe].city == 7) {
						out();
						return;
					}

				}
			}
		}
		System.out.println("No avaliable way");

	}

	/** 输出路径 */
	public void out() {
		System.out.print(sq[qe].city);
		while (sq[qe].pre != 0) {
			qe = sq[qe].pre;
			System.out.print("---" + sq[qe].city);
		}
	}

	public void set(int n) {
		for (int i = 0; i < n; i++) {
			visited[i] = 0;
		}
	}
}

class SQ {
	int city;
	int pre;
}