1、 序言
又很久没有学习了，上次学到哈希表又称散列表的相关知识，这次我们学习一种新的数据结构来建立网络模型。这种数据结构被称作图。首先，我们先应该先了解一下什么是图，其次学习第一种图的算法，这种图的算法被称作是广度优先搜索算法（breadth-first search ,BFS）。
广度优先搜索算法其实就是帮助你找出两样东西之间的最短距离，掌握了这种算法之后，我们可以完成以下几项内容：
编写国际跳棋AI，计算出最少走多少步可以获胜
编写拼写检查器，计算最少编辑多少个地方就可以将错拼的单词改成正确的单词，如将READED改为READER需要编辑一个地方
根据你的人际关系网络找到关系最近的医生
--------此示例来源于《算法图解》
2、 图简介
听说户县到咸阳的大巴已经停运了，那么我们去咸阳的话就需要重新计算路线，（我们暂时排除自驾到咸阳的路线）假设我们乘坐公共交通工具前往，并且希望中间的换乘最少，可以到达的部分交通线路如下：
我们从图中可以发现想从石油大学直接到达咸阳湖景区，除了自驾其它并不能一步到达景区，接着我们使用两步、三步、四步发现都不能直接到达景区，最少也得需要五步，路线为：从石油大学东门（周南站）乘坐101路到鄠邑站，然后乘坐动车到达阿房宫站，然后乘坐1061路到达沣东第一学校站，接着换成咸阳郭杜线到达统一广场站，最终不步行到达咸阳湖景区。当然还有其他到达景区的路线，但它们执行起来路程会更远。这个算法发现，前往咸阳湖景区需要五步，这种问题在专业上称为“最短路径问题（shorterest-path problem）”。解决最短路径的问题的算法被称为广度优先搜索。
就像上图一样，我们将路线用图解的形式展现出来，这就是图！其实非常简单，图由节点和边组成。一个节点可能与众多节点直接相连，这些众多节点都被称为这个节点的邻节点，在上图，大十字站和亚迪路站都被称为郭寨桥站的邻节点。
一句话概括起来：图用于模拟不同的东西是如何相连的。
3、 广度优先搜索
广度优先搜索算法是一种可用于图的查找算法，可以帮助回答两类问题：
从节点A出发，有前往节点B的路径吗？
从节点A出发，前往节点B的哪条路径最短？
举个例子，假设你经营着一个果园，每年秋天果子成熟了你需要将苹果卖给他。在微信上，你在好友列表中去找这么一个人。这种查找很简单，只需每看到一个人，然后想想他是不是收苹果的。
假设你没有朋友是收苹果的，那么就必须在朋友的朋友中进行查找。然后问到信息之后立马把他记在小本本上，这样一来，不仅需要在朋友中进行查找，还需要在朋友的朋友中查找。如果你当前看到的朋友并不是收苹果的，就将其加入小本本里，这就意味着你将在他的人际关系中进行查找。这种算法最终会将你整个人际关系网进行搜索，直到找到苹果经销商，这就是广度优先搜索算法。
广度优先搜索算法过程
在刚才的例子中，我们先从自己的朋友开始找起，后来从朋友的朋友继续查找，自己朋友称为一度关系，朋友的朋友称为二度关系，显然，一度关系优于二度关系。
搜索时，肯定是先自己的朋友，其次是朋友的朋友。当然只有按添加顺序查找时，才能达到搜索的目的。举个例子，张三是自己的朋友，李四是张三的朋友，但是李四先添加到名单中时，假设张三和李四都是收苹果的，但是由于添加顺序不对，必定会先搜索李四，然后再搜索张三，这样的话只是搜索到了苹果经销商，但没搜索到最近的朋友。
别忘了广度优先搜索需要解决两个问题：第一个是存在吗？第二个是最短吗？
但是这种按照顺序存储的数据结构竟然存在，它的专业术语叫做“队列”。
队列
数据结构的队列就如同我们吃饭排队，秉承先来后到的原则，先到的先吃饭。队列类似于栈，你不能随机地访问队列中的元素，队列只支持两种操作：入队和出队。
队列是一种先进先出的数据结构（First in First Out，FIFO）
3、 代码实现
package cn.yanhao.breadthfirstsearch;
/**
* 定义图类
*/
public class Graph
{
private final int Max_VERTS = 6; //图中顶点的个数
private Vertex vertexList[]; //用来存储顶点的数组
//用邻接矩阵来存储边，数组元素表示没有边界，1表示有边界
private int adjMat[][];
private int nVerts; //顶点个数
private QueueX queue; //用队列实现广度优先搜索
/*
顶点类
*/
class Vertex{
public char label;
public boolean wasVisited;
public Vertex(char label){
this.label = label;
wasVisited = false;
}
}
Graph(){
//顶点数组长度初始化为20
vertexList = new Vertex[Max_VERTS];
//初始化20x20矩阵
adjMat = new int[Max_VERTS][Max_VERTS];
nVerts = 0; //初始化顶点个数为0
//初始化邻接矩阵所有元素都为0，即所有顶点没有边
for (int i = 0; i < Max_VERTS; i++) {
for (int j = 0; j < Max_VERTS; j++) {
adjMat[i][j] = 0;
}
}
queue = new QueueX();
}
//将顶点添加到数组中，是否访问位置置为wasVisited = false(未访问）
public void addVertex(char lab){
//先添加在加1
vertexList[nVerts++] = new Vertex(lab);
}
//用邻接矩阵表示边，是对称的，两部分都要赋值
public void addEdge(int start,int end){
adjMat[start][end] = 1;
adjMat[end][start] = 1;
}
//打印某个顶点表示的值
public void displayVertex(int v){
System.out.print(vertexList[v].label+"");
}
//找到与某一顶点邻接且未被访问的顶点
public int getAdjUnvisitedVertex(int v){
for (int i = 0; i < nVerts; i++) {
//v顶点与i顶点相邻且未被访问
if(adjMat[v][i] == 1 && vertexList[i].wasVisited == false){
return i;
}
}
return -1;
}
/**
* 广度优先搜索
* 1、用remove方法检查栈顶
* 2、试图找到这个顶点还未被访问的邻接点
* 3、如果没有找到，该顶点出列
* 4、如果找到这样的顶点，访问这个顶点，并把它放入队列中
*/
public void breadthFirstSearch()
{
//第一个顶点可访问
vertexList[0].wasVisited = true;
//打印第一个顶点的值
displayVertex(0);
//队列插入第一个元素
queue.insert(0);
int v2;
//如果队列不为空
while(!queue.isEmpty()){
int v1 = queue.remove();
while ((v2 = getAdjUnvisitedVertex(v1)) != -1){
vertexList[v2].wasVisited = true;
displayVertex(v2);
queue.insert(v2);
}
}
//搜索完毕，初始化，便于下次搜索
for (int i = 0; i < nVerts; i++) {
vertexList[i].wasVisited = false;
}
}
public static void main(String[] args) {
Graph graph = new Graph();
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addVertex('E');
graph.addEdge(0,1); //AB
graph.addEdge(1,2); //BC
graph.addEdge(0,3); //AD
graph.addEdge(3,4); //DE
System.out.println("广度优先搜索算法：");
graph.breadthFirstSearch();
}
}