讯享网

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