📄 krusk.html

📁 Data Structure Ebook
💻 HTML
字号:
<HTML><HEAD>
<TITLE>Data Structures and Algorithms: Kruskal's Algorithm</TITLE>

<META name="description" content="Data Structures and Algorithms Course Notes,
PLDS210 University of Western Australia">
<META name="keywords" content="data structures,algorithms,abstract data types,
Kruskal's algorithm, minimum spanning tree, greedy algorithms">
</HEAD>
<BODY BGCOLOR="#ffffff">
<TABLE BGCOLOR="#00c0f0" WIDTH="100%" CELLSPACING=0 CELLPADDING=0>
<TR BGCOLOR="#00f0f0"><TD ALIGN=right>
<FONT FACE=helvetica SIZE=+1><I>Data Structures and Algorithms</I></FONT>
</TD></TR>

<TR><TD><FONT FACE=helvetica SIZE=+2><B>Kruskal's Algorithm</B></FONT>
</TD></TR>
</TABLE>
<P>

The following sequence of diagrams illustrates Kruskal's algorithm
in operation.
<TABLE BORDER=2>
<TR><TD><IMG SRC="krusk1.gif" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/fig/krusk1.gif"></TD><TD><B>gh</B> is shortest.<P>
Either <B>g</B> or <B>h</B> could be the representative,<BR>
<B>g</B> chosen arbitrarily.</TD></TR>
<TR><TD><IMG SRC="krusk2.gif" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/fig/krusk2.gif"></TD><TD><B>ci</B> creates two trees.
<P><B>c</B> chosen as representative for second.</TD></TR>
<TR><TD><IMG SRC="krusk3.gif" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/fig/krusk3.gif"></TD><TD><B>fg</B> is next shortest.
<P>Add it, choose <B>g</B> as representative.</TD></TR>
<TR><TD><IMG SRC="krusk4.gif" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/fig/krusk4.gif"></TD><TD><B>ab</B> creates a 3rd tree</TD>
</TR>
<TR><TD><IMG SRC="krusk5.gif" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/fig/krusk5.gif"></TD><TD>Add <B>cf</B>,<BR>
merging two trees.<P>
<B>c</B> is chosen as the representative.</TD></TR>
<TR><TD><IMG SRC="krusk6.gif" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/fig/krusk6.gif"></TD><TD><B>gi</B> is next cheapest,<BR>
but a cycle would be created.
<P><B>c</B> is the representative of both.</TD>
</TR>
<TR><TD><IMG SRC="krusk7.gif" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/fig/krusk7.gif"></TD><TD>Add <B>cd</B> instead</TD></TR>
<TR><TD><IMG SRC="krusk8.gif" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/fig/krusk8.gif"></TD><TD><B>hi</B> would make a cycle</TD>
</TR>
<TR><TD><IMG SRC="krusk9.gif" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/fig/krusk9.gif"></TD><TD>Add <B>ah</B> instead</TD></TR>
<TR><TD><IMG SRC="krusk10.gif" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/fig/krusk10.gif"></TD><TD><B>bc</B> would create a cycle.
<P>Add <B>de</B> instead<BR>
to complete the spanning tree -<BR>
all trees joined,
<B>c</B> is sole representative.</TD></TR>
</TABLE>

<P>

<TABLE CELLPADDING=5 WIDTH="100%" BGCOLOR="#00f0f0" CELLSPACING=4>
<TR><TD WIDTH=50%>
Back to <A HREF="mst.html" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/mst.html">Mininum Spanning Tree</A></TD>
<TD>Back to the <A HREF="ds_ToC.html" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/ds_ToC.html">Table of Contents</A>
</TD></TR></TABLE>
<SMALL>
&copy; <A HREF=mailto:morris@ee.uwa.edu.au>John Morris</A>, 1998
</SMALL>
</BODY>
</HTML>
⌨️ 快捷键说明

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