📄 ds7.3.2.htm
字号:
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<meta name="GENERATOR" content="Microsoft FrontPage 4.0">
<meta name="ProgId" content="FrontPage.Editor.Document">
<title>第一章 绪论</title>
<meta name="Microsoft Theme" content="hounk 010">
</head>
<body background bgcolor="#000099" text="#CCCC99" link="#FF9900" vlink="#996600" alink="#FF3300">
<h4 align="center"><span lang="EN-US"><font color="#FFFF00"><b><font size="6">7</font></b></font></span><font color="#FFFF00"><b><font size="6"><span lang="EN-US">.3.2</span><span style="mso-spacerun: yes; font-family: 黑体" 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><b><font size="5" color="#FFFFFF"><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></h4>
<p class="MsoNormal"><span style="mso-spacerun: yes" lang="EN-US"> <font color="#FFFFFF"><b><font size="5">
</font></b></font></span><font color="#FFFFFF"><b><font size="5"><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman""> 广度优先搜索（</span><span lang="EN-US">Breadth_First
Search</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">）</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><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><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><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><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><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><span lang="EN-US">1,2,…</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">的顶点。</span></b></font><img border="0" src="ds7.3.11.gif" align="right" width="263" height="148"></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 style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">所示无向图</span><span lang="EN-US">
</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><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><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><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">问</span><span lang="EN-US">v1 </span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">和</span><span lang="EN-US">v1</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">的邻接点</span><span lang="EN-US">v2</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">和</span><span lang="EN-US">v3</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">，然后依次访问</span><span lang="EN-US">v2 </span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">的邻接点</span><span lang="EN-US">v4 </span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">和</span><span lang="EN-US">v5 </span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">及</span><span lang="EN-US">v3
</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">的邻接点</span><span lang="EN-US">v6</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">和</span><span lang="EN-US">v7</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">，最后访问</span><span lang="EN-US">v4
</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">的邻接点</span><span lang="EN-US">v8</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">。由于这些顶点的邻接点均已被访问，并且图中所有顶点都被访问，由些完成了图的遍历。得到的顶点访问序列为：</span></b></font></p>
<p class="MsoNormal" style="margin-left:18.0pt;text-indent:-18.0pt;mso-list:l24 level1 lfo24;
tab-stops:list 18.0pt" align="center"><font size="5" color="#FFFFFF"><b><span lang="EN-US">v1</span><span style="font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"">→</span><span lang="EN-US">v2
</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">→</span><span lang="EN-US">v3
</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">→</span><span lang="EN-US">v4</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">→</span><span lang="EN-US">
v5</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">→</span><span lang="EN-US">
v6</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">→</span><span lang="EN-US"> v7 </span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">→</span><span lang="EN-US">v8</span></b></font></p>
<p class="MsoNormal" style="text-indent:21.0pt"><span style="font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman""><font color="#FFFFFF"><b><font size="5">和深度优先搜索类似，在遍历的过程中也需要一个访问标</font></b></font></span><font color="#FFFFFF"><b><font size="5">
<span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -