graphtheory.html

用Java开发的实用数学建模程序 简单易懂 初学者可以用来学习java知识

</TR>
</TABLE>

<A NAME="ADJACENT"><!-- --></A><H3>
ADJACENT</H3>
<PRE>
public static final int <B>ADJACENT</B></PRE>
<DL>
<DD>说明构造方法所传过来的矩阵是邻接矩阵。
<P>
<DL>
<DT><B>See Also:</B><DD><A HREF="../constant-values.html#algorithm.GraphTheory.ADJACENT">Constant Field Values</A></DL>
</DL>
<HR>

<A NAME="INCIDENCE"><!-- --></A><H3>
INCIDENCE</H3>
<PRE>
public static final int <B>INCIDENCE</B></PRE>
<DL>
<DD>说明构造方法所传过来的矩阵是关联矩阵。
<P>
<DL>
<DT><B>See Also:</B><DD><A HREF="../constant-values.html#algorithm.GraphTheory.INCIDENCE">Constant Field Values</A></DL>
</DL>
<HR>

<A NAME="WEIGHT"><!-- --></A><H3>
WEIGHT</H3>
<PRE>
public static final int <B>WEIGHT</B></PRE>
<DL>
<DD>说明构造方法所传过来的矩阵是权矩阵。
<P>
<DL>
<DT><B>See Also:</B><DD><A HREF="../constant-values.html#algorithm.GraphTheory.WEIGHT">Constant Field Values</A></DL>
</DL>
<HR>

<A NAME="n"><!-- --></A><H3>
n</H3>
<PRE>
public int <B>n</B></PRE>
<DL>
<DD>图的结点数。
<P>
<DL>
</DL>
</DL>
<HR>

<A NAME="m"><!-- --></A><H3>
m</H3>
<PRE>
public int <B>m</B></PRE>
<DL>
<DD>图的边数。
<P>
<DL>
</DL>
</DL>

<!-- ========= CONSTRUCTOR DETAIL ======== -->

<A NAME="constructor_detail"><!-- --></A>
<TABLE BORDER="1" WIDTH="100%" CELLPADDING="3" CELLSPACING="0" SUMMARY="">
<TR BGCOLOR="#CCCCFF" CLASS="TableHeadingColor">
<TD COLSPAN=1><FONT SIZE="+2">
<B>Constructor Detail</B></FONT></TD>
</TR>
</TABLE>

<A NAME="GraphTheory(int[][], int)"><!-- --></A><H3>
GraphTheory</H3>
<PRE>
public <B>GraphTheory</B>(int[][]&nbsp;matrix,
                   int&nbsp;matrixType)</PRE>
<DL>
<DD>用所给矩阵生成一个图。
<P>
<DT><B>Parameters:</B><DD><CODE>matrix</CODE> - 图所对应的矩阵，这个矩阵在GraphTheory类中产生克隆副本，GraphTheory的成员方法不会对该矩阵生产影响。<DD><CODE>matrixType</CODE> - 矩阵类型，可以为<A HREF="../algorithm/GraphTheory.html#ADJACENT"><CODE>ADJACENT</CODE></A>、<A HREF="../algorithm/GraphTheory.html#INCIDENCE"><CODE>INCIDENCE</CODE></A>、<A HREF="../algorithm/GraphTheory.html#WEIGHT"><CODE>WEIGHT</CODE></A>。</DL>

<!-- ============ METHOD DETAIL ========== -->

<A NAME="method_detail"><!-- --></A>
<TABLE BORDER="1" WIDTH="100%" CELLPADDING="3" CELLSPACING="0" SUMMARY="">
<TR BGCOLOR="#CCCCFF" CLASS="TableHeadingColor">
<TD COLSPAN=1><FONT SIZE="+2">
<B>Method Detail</B></FONT></TD>
</TR>
</TABLE>

<A NAME="dijkstra(int, int)"><!-- --></A><H3>
dijkstra</H3>
<PRE>
public java.util.Vector <B>dijkstra</B>(int&nbsp;start,
                                 int&nbsp;end)</PRE>
<DL>
<DD>Dijkstra算法，根据权矩阵计算图中任意两结点间的最短路。
<p>计算最短路的图必须是正权有向图。
<p>受int大小的限制，权值必须小于Integer.MAX_VALUE，即2147483647。
对于无向图，用户必须先把它的权矩阵转换成有向图的权矩阵。
<P>
<DD><DL>
<DT><B>Parameters:</B><DD><CODE>start</CODE> - 开始结点，结点编号从0开始<DD><CODE>end</CODE> - 结束结点，结点编号从0开始
<DT><B>Returns:</B><DD>Vector类的一个实例，该Vector中只有三个元素，int[]、Integer及int[]的实例。
			<p>其中第一int[]是从start结点到任一结点的最短路径矩阵path，int[end]中所存放的是从start到end的最短路径中end的前一结点。
			<p>Integer是最短路径的长度的整型数封装。当Integer为-1时，说明不存在从start到end的路径。
			<p>第二个int[]是从start到各结点（包括自身）的最短路径长度len，上面的Integer就是对int[]中第end个元素的封装。
			如果Integer为-1，则len中部分元素还保持初值Integer.MAX_VALUE。
			<p>如果构造该类时的矩阵不是权矩阵，或者不是图不是正权图，则返回null。</DL>
</DD>
</DL>
<HR>

<A NAME="hamilton()"><!-- --></A><H3>
hamilton</H3>
<PRE>
public int[] <B>hamilton</B>()</PRE>
<DL>
<DD>用分支与界法求解旅行商问题。
<p>计算旅行商问题的图必须是无向完全图。由于无向图的权矩阵是对称阵，因此该方法不检查权矩阵是否真的为对称阵，
而是直接使用权矩阵对角线以上的元素，对权矩阵对称性的检查就在输入端完成。
<p>图的结点数不能小于3。
<p>受int大小的限制，权值必须小于Integer.MAX_VALUE，即2147483647。
<P>
<DD><DL>

<DT><B>Returns:</B><DD>整型数组int[]，其中int[].length==n+1，int[0]是哈密顿圈的长度，从int[1]到int[n]记录哈密顿圈依次经过的结点。
			结点从0从开始。
			<p>以下三种情况返回null：该图不是完全图、结点数小于3、构造GraphTheory类时matrixType不为WEIGHT。</DL>
</DD>
</DL>
<HR>

<A NAME="generateHuffmanTree(java.util.LinkedList)"><!-- --></A><H3>
generateHuffmanTree</H3>
<PRE>
public static void <B>generateHuffmanTree</B>(java.util.LinkedList&nbsp;binTree)</PRE>
<DL>
<DD>Huffman算法，根据所给树的结点链表对构造Huffman树的过程作一次递归。
<p>构造的过程是把权最小的两个结点合并为一个结点。
<P>
<DD><DL>
<DT><B>Parameters:</B><DD><CODE>binTree</CODE> - 等待构树的结点链表。
			<p>最终得到的binTree是这样一个链表：该链表中只有一个元素，为Huffman树的根结点，是一个二叉树结点类，
			根据该根结点，可以找到二叉树的全部结点。
			<p>需要注意的是：生成Huffman树的过程是对方法自身的不断递归调用，
			因此得到的BinaryTree中的info域并未被初始化。
			<p>要得到含有路径信息的Huffman树，应调用huffman方法。<DT><B>See Also:</B><DD><A HREF="../algorithm/GraphTheory.html#huffman(int[])"><CODE>huffman(int[])</CODE></A>, 
<A HREF="../algorithm/GraphTheory.html#generateHuffmanPath(ADT.BinaryTree)"><CODE>generateHuffmanPath(ADT.BinaryTree)</CODE></A></DL>
</DD>
</DL>
<HR>

<A NAME="generateHuffmanPath(ADT.BinaryTree)"><!-- --></A><H3>
generateHuffmanPath</H3>
<PRE>
public static void <B>generateHuffmanPath</B>(<A HREF="../ADT/BinaryTree.html" title="class in ADT">BinaryTree</A>&nbsp;currentNode)</PRE>
<DL>
<DD>根据已生成的Huffman树生成树中各结点的路径。
<p>由于Huffman树是二叉树，因此用0和1表示从根结点到当前结点的路径，
0表示从父结点向左走得到下一结点，1表示从父结点向右走得到下一结点。
<P>
<DD><DL>
<DT><B>Parameters:</B><DD><CODE>currentNode</CODE> - 当前结点<DT><B>See Also:</B><DD><A HREF="../algorithm/GraphTheory.html#huffman(int[])"><CODE>huffman(int[])</CODE></A>, 
<A HREF="../algorithm/GraphTheory.html#generateHuffmanTree(java.util.LinkedList)"><CODE>generateHuffmanTree(java.util.LinkedList)</CODE></A></DL>
</DD>
</DL>
<HR>

<A NAME="huffman(int[])"><!-- --></A><H3>
huffman</H3>
<PRE>
public static <A HREF="../ADT/BinaryTree.html" title="class in ADT">BinaryTree</A>[] <B>huffman</B>(int[]&nbsp;leafVertex)</PRE>
<DL>
<DD>Huffman算法，根据所给树叶结点的权构造最优二叉树，该树称为Huffman树。
<P>
<DD><DL>
<DT><B>Parameters:</B><DD><CODE>leafVertex</CODE> - 树叶结点的权数组
<DT><B>Returns:</B><DD>Huffman树的树叶结点数组，每个结点中都含有从根到该树叶结点的路径。
			<p>0表示向左，1表示向右。<DT><B>See Also:</B><DD><A HREF="../algorithm/GraphTheory.html#generateHuffmanTree(java.util.LinkedList)"><CODE>generateHuffmanTree(java.util.LinkedList)</CODE></A>, 
<A HREF="../algorithm/GraphTheory.html#generateHuffmanPath(ADT.BinaryTree)"><CODE>generateHuffmanPath(ADT.BinaryTree)</CODE></A></DL>
</DD>
</DL>
<!-- ========= END OF CLASS DATA ========= -->
<HR>


<!-- ======= START OF BOTTOM NAVBAR ====== -->
<A NAME="navbar_bottom"><!-- --></A>
<A HREF="#skip-navbar_bottom" title="Skip navigation links"></A>
<TABLE BORDER="0" WIDTH="100%" CELLPADDING="1" CELLSPACING="0" SUMMARY="">
<TR>
<TD COLSPAN=3 BGCOLOR="#EEEEFF" CLASS="NavBarCell1">
<A NAME="navbar_bottom_firstrow"><!-- --></A>
<TABLE BORDER="0" CELLPADDING="0" CELLSPACING="3" SUMMARY="">
  <TR ALIGN="center" VALIGN="top">
  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="../overview-summary.html"><FONT CLASS="NavBarFont1"><B>Overview</B></FONT></A>&nbsp;</TD>
  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="package-summary.html"><FONT CLASS="NavBarFont1"><B>Package</B></FONT></A>&nbsp;</TD>
  <TD BGCOLOR="#FFFFFF" CLASS="NavBarCell1Rev"> &nbsp;<FONT CLASS="NavBarFont1Rev"><B>Class</B></FONT>&nbsp;</TD>
  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="package-tree.html"><FONT CLASS="NavBarFont1"><B>Tree</B></FONT></A>&nbsp;</TD>
  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="../deprecated-list.html"><FONT CLASS="NavBarFont1"><B>Deprecated</B></FONT></A>&nbsp;</TD>
  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="../index-all.html"><FONT CLASS="NavBarFont1"><B>Index</B></FONT></A>&nbsp;</TD>
  <TD BGCOLOR="#EEEEFF" CLASS="NavBarCell1">    <A HREF="../help-doc.html"><FONT CLASS="NavBarFont1"><B>Help</B></FONT></A>&nbsp;</TD>
  </TR>
</TABLE>
</TD>
<TD ALIGN="right" VALIGN="top" ROWSPAN=3><EM>
</EM>
</TD>
</TR>

<TR>
<TD BGCOLOR="white" CLASS="NavBarCell2"><FONT SIZE="-2">
&nbsp;<A HREF="../algorithm/Fit.html" title="class in algorithm"><B>PREV CLASS</B></A>&nbsp;
&nbsp;<A HREF="../algorithm/HamiltonSort.html" title="class in algorithm"><B>NEXT CLASS</B></A></FONT></TD>
<TD BGCOLOR="white" CLASS="NavBarCell2"><FONT SIZE="-2">
  <A HREF="../index.html" target="_top"><B>FRAMES</B></A>  &nbsp;
&nbsp;<A HREF="GraphTheory.html" target="_top"><B>NO FRAMES</B></A>  &nbsp;
&nbsp;<SCRIPT type="text/javascript">
  <!--
  if(window==top) {
    document.writeln('<A HREF="../allclasses-noframe.html"><B>All Classes</B></A>');
  }
  //-->
</SCRIPT>
<NOSCRIPT>
  <A HREF="../allclasses-noframe.html"><B>All Classes</B></A>
</NOSCRIPT>

</FONT></TD>
</TR>
<TR>
<TD VALIGN="top" CLASS="NavBarCell3"><FONT SIZE="-2">
  SUMMARY:&nbsp;NESTED&nbsp;|&nbsp;<A HREF="#field_summary">FIELD</A>&nbsp;|&nbsp;<A HREF="#constructor_summary">CONSTR</A>&nbsp;|&nbsp;<A HREF="#method_summary">METHOD</A></FONT></TD>
<TD VALIGN="top" CLASS="NavBarCell3"><FONT SIZE="-2">
DETAIL:&nbsp;<A HREF="#field_detail">FIELD</A>&nbsp;|&nbsp;<A HREF="#constructor_detail">CONSTR</A>&nbsp;|&nbsp;<A HREF="#method_detail">METHOD</A></FONT></TD>
</TR>
</TABLE>
<A NAME="skip-navbar_bottom"></A>
<!-- ======== END OF BOTTOM NAVBAR ======= -->

<HR>

</BODY>
</HTML>