📄 ds7.3.2.htm
字号:
"Times New Roman"">志数组。并且，为了顺次访问路径长度为</span><span lang="EN-US">2</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">、</span><span lang="EN-US">3</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">、…的顶点，需附设队列以存储已被访问的路径长度为</span><span lang="EN-US">1</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">、</span><span lang="EN-US">2</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">、…</span><span style="mso-spacerun: yes" lang="EN-US">
</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">的顶点。</span></font></b></font></p>
<p class="MsoNormal" style="text-indent:21.0pt"><font size="5" color="#FFFFFF"><b><span style="font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">从图的某一点</span><span lang="EN-US">v</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">出发，递归地进行广度优先遍历的过程如算法</span></b></font><font size="5" color="#FFFFFF"><b>下：</b></font></p>
<p class="MsoNormal" style="text-indent: 0; margin: 0"><span lang="EN-US"><font color="#FFFFFF"><b><font size="5">void<span style="mso-spacerun: yes">
</span>BFSTraverse(Graph G, Status(*Visit)(int v))</font></b></font></span></p>
<p class="MsoNormal" style="text-indent: 0; margin: 0"><b><font size="5" color="#FFFFFF"><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">{/*</span></font><font color="#FFFFFF" size="4"><span style="mso-bidi-font-size: 10.0pt"><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">按广度优先非递归遍历图</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">G</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">。使用辅助队列</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">Q</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">和访问标志数组</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">visited</span></span></font><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><font size="5" color="#FFFFFF">*/<o:p>
</o:p>
</font></span></b></p>
<p class="MsoNormal" style="text-indent: 0; margin: 0"><span lang="EN-US"><span style="mso-spacerun: yes"><font color="#FFFFFF"><b><font size="5">
</font></b></font></span><font color="#FFFFFF"><b><font size="5">for
(v=0;v<G,vexnum;++v)</font></b></font></span></p>
<p class="MsoNormal" style="text-indent: 0; margin: 0"><span lang="EN-US"><span style="mso-spacerun: yes"><font color="#FFFFFF"><b><font size="5">
</font></b></font></span><font color="#FFFFFF"><b><font size="5">visited[v]=FALSE</font></b></font></span></p>
<p class="MsoNormal" style="text-indent: 0; margin: 0"><span lang="EN-US"><span style="mso-spacerun: yes"><font color="#FFFFFF"><b><font size="5">
</font></b></font></span><font color="#FFFFFF"><b><font size="5">InitQueue(Q);<span style="mso-spacerun: yes">
</span></font></b></font></span><font color="#FFFFFF"><b><font size="5"><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">/*</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">置空的国债队列</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">Q*/</span></font></b></font></p>
<p class="MsoNormal" style="text-indent: 0; mso-list: l24 level1 lfo24; tab-stops: list 18.0pt; margin: 0"><font size="5" color="#FFFFFF"><b><span style="font-style: normal; font-variant: normal; font-family: Times New Roman; mso-bidi-font-size: 10.0pt" lang="EN-US">
</span><span lang="EN-US">if (!visited[v])<span style="mso-spacerun: yes">
</span></span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">/*v</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">尚未访问</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">*/<o:p>
</o:p>
</span></b></font></p>
<p class="MsoNormal" style="text-indent: 0; mso-list: l24 level1 lfo24; tab-stops: list 18.0pt; margin: 0"><font size="5" color="#FFFFFF"><b><span style="font-style: normal; font-variant: normal; font-family: Times New Roman; mso-bidi-font-size: 10.0pt" lang="EN-US">
</span><span lang="EN-US">{</span></b></font></p>
<p class="MsoNormal" style="text-indent: 0; mso-list: l24 level1 lfo24; tab-stops: list 18.0pt; margin: 0"><font size="5" color="#FFFFFF"><b><span lang="EN-US">
EnQucue(Q,v);<span style="mso-spacerun: yes"> </span></span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">/*v</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">入队列</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">*/<o:p>
</o:p>
</span></b></font></p>
<p class="MsoNormal" style="text-indent: 0; mso-list: l24 level1 lfo24; tab-stops: list 18.0pt; margin: 0"><font size="5" color="#FFFFFF"><b><span style="font-style: normal; font-variant: normal; font-family: Times New Roman" lang="EN-US">
</span><span lang="EN-US">while (!QueueEmpty(Q))</span></b></font></p>
<p class="MsoNormal" style="text-indent: 0; mso-list: l24 level1 lfo24; tab-stops: list 18.0pt; margin: 0"><font size="5" color="#FFFFFF"><b><span style="font-style: normal; font-variant: normal; font-family: Times New Roman; mso-bidi-font-size: 10.0pt" lang="EN-US">
</span><span lang="EN-US">{ </span></b></font></p>
<p class="MsoNormal" style="text-indent: 0; mso-list: l24 level1 lfo24; tab-stops: list 18.0pt; margin: 0"><font size="5" color="#FFFFFF"><b><span lang="EN-US">
DeQueue(Q,u); <span style="mso-spacerun:
yes"> </span><span style="mso-spacerun: yes"> </span></span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">/*</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">队头元素出队并置为</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">u*/<o:p>
</o:p>
</span></b></font></p>
<p class="MsoNormal" style="text-indent: 0; mso-list: l24 level1 lfo24; tab-stops: list 18.0pt; margin: 0"><font size="5" color="#FFFFFF"><b><span style="font-style: normal; font-variant: normal; font-family: Times New Roman" lang="EN-US">
</span><span lang="EN-US">visited[u]=TRUE; visit(u); <span style="mso-spacerun:
yes"> </span>/</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">*</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">访问</span><span lang="EN-US">u</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">*/</span></b></font></p>
<p class="MsoNormal" style="text-indent: 0; mso-list: l24 level1 lfo24; tab-stops: list 18.0pt; margin: 0"><font size="5" color="#FFFFFF"><b><span style="font-style: normal; font-variant: normal; font-family: Times New Roman" lang="EN-US">
</span><span lang="EN-US">for(w=FistAdjVex(G,u); w; w=NextAdjVex(G,u,w))</span></b></font></p>
<p class="MsoNormal" style="text-indent: 0; mso-list: l24 level1 lfo24; tab-stops: list 18.0pt; margin: 0"><b><font size="5" color="#FFFFFF"><span style="font-style: normal; font-variant: normal; font-family: Times New Roman" lang="EN-US">
</span><span lang="EN-US">if (!visited[w]) EnQueue(Q,w);</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">
<span style="mso-spacerun:
yes"> </span></span></font></b></p>
<p class="MsoNormal" style="text-indent: 0; mso-list: l24 level1 lfo24; tab-stops: list 18.0pt; margin: 0"><font size="5" color="#FFFFFF"><b><span style="font-style: normal; font-variant: normal; font-family: Times New Roman" lang="EN-US">
</span><span lang="EN-US">}</span></b></font></p>
<p class="MsoNormal" style="text-indent: 0; mso-list: l24 level1 lfo24; tab-stops: list 18.0pt; margin: 0"><font size="5" color="#FFFFFF"><b><span style="font-style: normal; font-variant: normal; font-family: Times New Roman" lang="EN-US"> </span><span lang="EN-US"><span style="mso-spacerun:
yes"> </span>}</span></b></font></p>
<p class="MsoNormal" style="text-indent: 0; mso-list: l24 level1 lfo24; tab-stops: list 18.0pt; margin: 0"><font size="5" color="#FFFFFF"><b><span lang="EN-US">}/*BFSTraverse*/</span></b></font></p>
<p class="MsoNormal" style="text-indent: 0; mso-list: l24 level1 lfo24; tab-stops: list 18.0pt; margin: 0"><span lang="EN-US"><font size="5" color="#FFFFFF"><b> <o:p>
</o:p>
</b></font></span></p>
<font size="5" color="#FFFFFF"><b><span style="mso-spacerun: yes; mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA" lang="EN-US">
</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">分析上述算法，每个顶点至多进一次队列。遍历图的过程实质是通过边或弧找邻接点的过程，因此广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同，两者不同之处仅仅在于对顶点访问的顺序不同。</span></b></font>
<p> </p>
<p align="center"><b><a href="ds7.3.htm"><font size="5" color="#FFFF00">返回</font></a></b></p>
<p align="center"> </p>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -