📄 7_6.htm
字号:
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=gb_2312-80">
<META NAME="Generator" CONTENT="Microsoft Word 97">
<TITLE>第 2 章 线性表</TITLE>
</HEAD>
<BODY>
<B><FONT SIZE=3><P ALIGN="JUSTIFY">6. </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>构造生成树的算法</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> void</B> DFSTree ( Graph G, <B>int</B> v, CSTree <B>&</B>T ) </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>{</P>
</B></FONT><FONT SIZE=3><P ALIGN="JUSTIFY">// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>从第</FONT><FONT SIZE=3> <I>v</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>个顶点出发深度优先遍历</FONT><FONT SIZE=3> <I>G</I></FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>，建立以</FONT><FONT SIZE=3> <I>T</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>为根的生成树，</FONT><I><FONT SIZE=3>T</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>以孩子兄弟链表作为存储结构</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> visited [v] = TRUE; first = TRUE;</P>
<P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> <B>for</B> ( w = FirstAdjVex ( G, v ); w; w = NextAdjVex ( G, v, w ) )</P>
<P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><B><FONT SIZE=3>if</B> ( <B>!</B> visited [w] ) </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>{						</B></FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>第</FONT><FONT SIZE=3> <I>v</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>顶点为新的生成树的根结点</P>
<P ALIGN="JUSTIFY">		</FONT><FONT SIZE=3> p = ( CSTree ) <B>malloc</B> ( <B>sizeof</B> ( CSNode ) );	// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>分配孩子结点</P>
<P ALIGN="JUSTIFY">		</FONT><FONT SIZE=3> *p = </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>{</B></FONT><FONT SIZE=3> GetVex ( G, w ), NULL, NULL </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>}</B></FONT><FONT SIZE=3>;</P>
<P ALIGN="JUSTIFY">	</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> <B>if</B> ( first ) </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>{								</B></FONT><FONT SIZE=3>// <I>w</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>是</FONT><FONT SIZE=3> <I>v</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>的第一个其他未被访问的邻接顶点</P>
<P ALIGN="JUSTIFY">	</FONT><FONT SIZE=3> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>		</FONT><FONT SIZE=3>T->firstchild = p;	</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>					</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>是根的第一个孩子结点</P>
<P ALIGN="JUSTIFY">	</FONT><FONT SIZE=3> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>		</FONT><FONT SIZE=3>first = FALSE;</P>
<P ALIGN="JUSTIFY">	</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>}</B></FONT><FONT SIZE=3> // if </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>结束</P>
<P ALIGN="JUSTIFY">		</FONT><FONT SIZE=3> <B>else</B> q->nextsibiling = p;</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>					</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>是上一个邻接顶点的右兄弟结点</P>
<P ALIGN="JUSTIFY">		</FONT><FONT SIZE=3> q = p; DFSTree ( G, w, q );</P><DIR>
<P ALIGN="JUSTIFY"> // </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>从第</FONT><FONT SIZE=3> <I>w</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>个顶点出发深度优先遍历图</FONT><FONT SIZE=3> <I>G</I></FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>，建立子生成树</FONT><FONT SIZE=3> <I>q</P>
</I></FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3><P ALIGN="JUSTIFY">}</B></FONT><FONT SIZE=3> // if </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>结束</P></DIR>
<B><P ALIGN="JUSTIFY">}</B></FONT><FONT SIZE=3> // DFSTree</P></FONT></BODY>
</HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -