📄 ds7.3.1.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.1</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></h4>
<p class="MsoNormal"><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><span lang="EN-US">Depth_Fisrst
Search</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">）遍历类似于树的先根遍历，是树的先根遍历的推广。</span></font></b></p>
<p class="MsoNormal"><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><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></font></b></p>
<p class="MsoNormal" align="center"><img border="0" src="ds7.3.11.gif" width="263" height="148"></p>
<p class="MsoNormal"><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><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">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">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">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">v8
</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">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">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">
v8</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">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">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">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">v3</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">，再继续进行下去由此，得到的顶点访问序列为：</span></font></b></p>
<p class="MsoNormal"><b><font size="5" color="#FFFFFF"><span lang="EN-US"><span style="mso-spacerun:
yes">
</span><span style="mso-spacerun: yes"> </span>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">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><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="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></font></b></p>
<p class="MsoNormal" style="text-indent:21.0pt"><b><span style="font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman""><font size="5" color="#FFFFFF">显然，这是一个递归的过程。为了在遍历过程中便于区分顶点是否已被访问，需附设访问标志数组</font></span><font size="5" color="#FFFFFF"><span lang="EN-US">visited[0:n-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">FALSE
</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">，一旦某个顶点被访问，则其相应的分量置为</span><span lang="EN-US">TRUE</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">。</span></font></b></p>
<b><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"><font size="5" color="#FFFFFF">
从图的某一点</font></span><font size="5" color="#FFFFFF"><span lang="EN-US" style="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">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; 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></font></b>
<p class="MsoNormal" style="text-indent: 0; margin: 0"><span lang="EN-US"><font size="5" color="#FFFFFF"><b>void
DFS(Graph G,int v )</b></font></span></p>
<p class="MsoNormal" style="text-indent: 0; margin: 0"><font size="5" color="#FFFFFF"><b><span lang="EN-US">{</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">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">G*/</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[v]=TRUE;VisitFunc(v);<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">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">*/</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=FisrAdjVex(G,v);w; w=NextAdjVex(G,v,w))</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">if (!visited[w]) DFS(G,w);<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 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> </p>
<p> </p>
<p align="center"> </p>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -