page578.html

来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 90 行

HTML
90 行
字号 
<HTML><HEAD><TITLE>Kruskal's Algorithm</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html7795" HREF="page579.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7793" HREF="page573.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7789" HREF="page577.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html7797" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION0016520000000000000000">Kruskal's Algorithm</A></H2><P>Like Prim's algorithm,<em>Kruskal's algorithm</em><A NAME=53597>&#160;</A>also constructs the minimum spanning treeof a graph by adding edges to the spanning tree one-by-one.At all points during its execution the set of edgesselected by Prim's algorithm forms exactly one tree.On the other hand,the set of edges selected by Kruskal's algorithm forms a forest of trees.<P>Kruskal's algorithm is conceptually quite simple.The edges are selected and added to the spanning treein increasing order of their weights.An edge is added to the tree only if it does not create a cycle.<P>The beauty of Kruskal's algorithmis the way that potential cycles are detected.Consider an undirected graph  <IMG WIDTH=73 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70549" SRC="img2166.gif"  >.We can view the set of vertices,  <IMG WIDTH=11 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline70551" SRC="img2167.gif"  >,as a <em>universal set</em><A NAME=53599>&#160;</A>and the set of edges,  <IMG WIDTH=9 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline70557" SRC="img2168.gif"  >,as the definition of an <em>equivalence relation</em><A NAME=53601>&#160;</A>over the universe  <IMG WIDTH=11 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline70551" SRC="img2167.gif"  >.(See Definition&nbsp;<A HREF="page412.html#defnsetsequivalence"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>).In general, an equivalence relation partitionsa universal set into a set of equivalence classes.If the graph is connected,there is only one equivalence class--all the elements of the universal set are <em>equivalent</em>.Therefore, a <em>spanning tree</em> is a minimal set of equivalencesthat result in a single equivalence class.<P>Kruskal's algorithm computes, <IMG WIDTH=119 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline72233" SRC="img2441.gif"  >,a sequence of <em>partitions</em><A NAME=53607>&#160;</A>of the set of vertices  <IMG WIDTH=11 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline70551" SRC="img2167.gif"  >.(Partitions are discussed in Section&nbsp;<A HREF="page403.html#secsetspartitions"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>).The initial partition consists of  <IMG WIDTH=18 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline70975" SRC="img2249.gif"  > sets of size one:<P> <IMG WIDTH=356 HEIGHT=19 ALIGN=BOTTOM ALT="displaymath72221" SRC="img2442.gif"  ><P>Each subsequent element of the sequence is obtainedfrom its predecessor by <em>joining</em> two of the elements of the partition.Therefore,  <IMG WIDTH=15 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline72239" SRC="img2443.gif"  > has the form<P> <IMG WIDTH=346 HEIGHT=22 ALIGN=BOTTOM ALT="displaymath72222" SRC="img2444.gif"  ><P>for  <IMG WIDTH=103 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline72241" SRC="img2445.gif"  >.<P>To construct the sequencethe edges in  <IMG WIDTH=9 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline70557" SRC="img2168.gif"  > are considered one-by-onein increasing order of their weights.Suppose we have computed the sequence up to  <IMG WIDTH=15 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline72239" SRC="img2443.gif"  >and the next edge to be considered is  <IMG WIDTH=42 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline72173" SRC="img2431.gif"  >.If <I>v</I> and <I>w</I> are both members of the same element of partition  <IMG WIDTH=15 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline72239" SRC="img2443.gif"  >,then the edge forms a cycle,and is not part of the minimum-cost spanning tree.<P>On the other hand, suppose <I>v</I> and <I>w</I> are members of two differentelements of partition  <IMG WIDTH=15 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline72239" SRC="img2443.gif"  >, say  <IMG WIDTH=15 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline72261" SRC="img2446.gif"  > and  <IMG WIDTH=14 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline72263" SRC="img2447.gif"  > (respectively).Then  <IMG WIDTH=42 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline72173" SRC="img2431.gif"  > must be an edge in the minimum-cost spanning tree.In this case, we compute  <IMG WIDTH=29 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline72267" SRC="img2448.gif"  > by <em>joining</em>  <IMG WIDTH=15 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline72261" SRC="img2446.gif"  > and  <IMG WIDTH=14 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline72263" SRC="img2447.gif"  >.That is, we replace  <IMG WIDTH=15 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline72261" SRC="img2446.gif"  > and  <IMG WIDTH=14 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline72263" SRC="img2447.gif"  > in  <IMG WIDTH=15 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline72239" SRC="img2443.gif"  >by the <em>union</em>  <IMG WIDTH=49 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline72279" SRC="img2449.gif"  >.<P>Figure&nbsp;<A HREF="page578.html#figgraph18"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> illustrates how Kruskal's algorithm determinesthe minimum-cost spanning tree of the graph  <IMG WIDTH=25 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline72147" SRC="img2423.gif"  > shown in Figure&nbsp;<A HREF="page575.html#figgraph16"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.The algorithm computes the following sequence of partitions:<P> <IMG WIDTH=500 HEIGHT=146 ALIGN=BOTTOM ALT="eqnarray53618" SRC="img2450.gif"  ><P><P><P><A NAME="54628">&#160;</A><A NAME="figgraph18">&#160;</A> <IMG WIDTH=575 HEIGHT=389 ALIGN=BOTTOM ALT="figure53620" SRC="img2451.gif"  ><BR><STRONG>Figure:</STRONG> Operation of Kruskal's algorithm.<BR><P><BR> <HR><UL> <LI> <A NAME="tex2html7798" HREF="page579.html#SECTION0016521000000000000000">Implementation</A><LI> <A NAME="tex2html7799" HREF="page580.html#SECTION0016522000000000000000">Running Time Analysis</A></UL><HR><A NAME="tex2html7795" HREF="page579.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html7793" HREF="page573.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html7789" HREF="page577.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html7797" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright &#169; 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a>  All rights reserved.</ADDRESS></BODY></HTML>

page578.html - 源码说明

本页面展示了「Data Structures And Algorithms With Object-Oriented Design Patterns In Python (2003) source code and」中的 page578.html 源码文件，采用 HTML 编程语言编写，共 90 行代码。您可以在线阅读完整代码内容，也可以返回资源详情页下载完整源码包进行本地学习和开发。

虫虫下载站收录了大量与Object-Oriented相关的技术资源，包括源代码、技术文档、电路图等，是电子工程师和嵌入式开发者的专业学习平台。

⌨️ 快捷键说明

复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?