📄 7_7.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">7. </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>构造最小生成树的普里姆算法</P>
</B></FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> <B>struct</B> </FONT><B><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>{</P>
</B></FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> VertexType</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>		</FONT><FONT SIZE=3>adjvex;	</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>					</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>存储该边依附的在</FONT><FONT SIZE=3> <I>U</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>中的顶点</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> VRType	 </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3>lowcost;	</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>					</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>存储该边上的权</P>
<B><P ALIGN="JUSTIFY">}</B></FONT><FONT SIZE=3> closedge[ MAX_VERTEX_NUM ];</P>
<B><P ALIGN="JUSTIFY"> void</B> MiniSpanTree_Prim ( MGraph G, VertexType u ) </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>Prim</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>）算法从第</FONT><FONT SIZE=3> <I>u</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</P>
</I><P ALIGN="JUSTIFY">// </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>G</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>采用邻接矩阵存储结构。</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> k = LocateVex ( G, u );</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>						</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>确定顶点</FONT><FONT SIZE=3> <I>u</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>在图</FONT><FONT SIZE=3> <I>G</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>中的位置</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3> <B>for</B> ( j = 0; j < G.vexnum; ++j )</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>				</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>辅助数组初始化</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> <B>if</B> ( j <B>! </B>= k ) closedge[j] = { u,G.arcs[k][j].adj };</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> adjvex, lowcost </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> closedge[k].lowcost = 0;</P>
<P ALIGN="JUSTIFY"> // </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>初始，</FONT><I><FONT SIZE=3>U</I> = {<I>u</I></FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>}，</FONT><FONT SIZE=3>closedge[k].lowcost = 0 </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>表示顶点</FONT><FONT SIZE=3> <I>k</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>并入</FONT><FONT SIZE=3> <I>U</P>
</I><P ALIGN="JUSTIFY"> <B>for</B> ( i = 1; i < G.vexnum; ++i ) </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>G</I>.lowcost-1 </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>个顶点</P>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3>k = Minimum (closedge);</P>
<P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>求出</FONT><FONT SIZE=3> <I>T</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>的下一个结点：第</FONT><FONT SIZE=3> <I>k</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>顶点。此时</FONT><FONT SIZE=3> closedge[k].lowcost =</P><DIR>
<P ALIGN="JUSTIFY">// MIN </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>{</FONT><FONT SIZE=3> closedge[v<SUB>i</SUB>].lowcost | closedge[v<SUB>i</SUB>].lowcost > 0, <I>v<SUB>i</I></SUB></FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>∈</FONT><I><FONT SIZE=3>V</I>-<I>U </I></FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>}</P></DIR>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY"> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><B><FONT SIZE=3>printf</B> ( closedge[k].adjvex, G.vexs[k] )</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>			</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>输出生成树的边</P><DIR>
</FONT><FONT SIZE=3><P ALIGN="JUSTIFY">closedge[k].lowcost = 0;</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>						</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>第</FONT><FONT SIZE=3> <I>k</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>个顶点并入</FONT><FONT SIZE=3> <I>U</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>集</P>
</FONT><B><FONT SIZE=3><P ALIGN="JUSTIFY">for</B> ( j = 0; j < G.vexnum; ++j )</P>
<B><P ALIGN="JUSTIFY"> if</B> ( G.arcs[k][j].adj < closedge[j].lowcost )</P><DIR>
<P ALIGN="JUSTIFY">closedge[j] = { G.vexs[k], G.arcs[k][j].adj };</FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>	</FONT><FONT SIZE=3>// </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>新顶点并入</FONT><FONT SIZE=3> <I>U</I> </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>后重新选择最小边</P></DIR>
</DIR>
</FONT><FONT SIZE=3><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> // for </FONT><FONT FACE="宋体" LANG="ZH-CN" SIZE=3>结束</P>
<B><P ALIGN="JUSTIFY">}</B></FONT><FONT SIZE=3> // MiniSpanTree_Prim</P></FONT></BODY>
</HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -