“2012级--讨论记录 (第二学期)”的版本间的差异

来自问题求解
跳转至: 导航搜索
2013年3月8日
 
(未显示同一用户的21个中间版本)
第1行: 第1行:
=2013年3月8日=
 
[[媒体文件:讨论记录-第二学期-2班-第2次.pdf|[课件下载]]]
 
<ol>
 
  <li>加法和乘法原理的应用:识别元素;识别不相交的集合。</li>
 
  <li>
 
    列表、置换和子集。
 
    <ul>
 
      <li>列表:本质是函数。</li>
 
      <li>置换:本质是双射函数。</li>
 
      <li>k-元素置换:本质是列表。</li>
 
      <li>k-元素子集:也可以看作函数。</li>
 
    </ul>
 
  </li>
 
  <li>双射在counting中的作用:元素个数不变,但更容易计算。</li>
 
  <li>等价关系在counting中的作用:等价类大小相同时,可以做除法。</li>
 
</ol>
 
 
 
=2013年3月1日=
 
=2013年3月1日=
 
[[媒体文件:讨论记录-第二学期-2班-第1次.pdf|[课件下载]]]
 
[[媒体文件:讨论记录-第二学期-2班-第1次.pdf|[课件下载]]]
第56行: 第39行:
 
     </ul>
 
     </ul>
 
   </li>
 
   </li>
 +
</ol>
 +
 +
=2013年3月8日=
 +
[[媒体文件:讨论记录-第二学期-2班-第2次.pdf|[课件下载]]]
 +
<ol>
 +
  <li>加法和乘法原理的应用:识别元素;识别不相交的集合。</li>
 +
  <li>
 +
    列表、置换和子集。
 +
    <ul>
 +
      <li>列表:本质是函数。</li>
 +
      <li>置换:本质是双射函数。</li>
 +
      <li>k-元素置换:本质是列表。</li>
 +
      <li>k-元素子集:也可以看作函数。</li>
 +
    </ul>
 +
  </li>
 +
  <li>双射在counting中的作用:元素个数不变,但更容易计算。</li>
 +
  <li>等价关系在counting中的作用:等价类大小相同时,可以做除法。</li>
 +
</ol>
 +
 +
=2013年3月15日=
 +
[[媒体文件:讨论记录-第二学期-2班-第3次.pdf|[课件下载]]]
 +
<ol>
 +
  <li>
 +
    maximum-subarray problem。
 +
    <ul>
 +
      <li>divide、conquer和combine在这个算法中分别如何体现。</li>
 +
      <li>找max-crossing-subarray的方式与brute-force不同,从而节约操作。</li>
 +
      <li>运行时间的递归表示。</li>
 +
      <li>利用recursion tree来猜测运行时间的渐进表示法。</li>
 +
      <li>利用substitution或master theorem来证明。</li>
 +
    </ul>
 +
  </li>
 +
  <li>
 +
    substitution证明的一些细节。
 +
    <ul>
 +
      <li>为低阶项保留余量。</li>
 +
      <li>恰当运用替换。</li>
 +
    </ul>
 +
  </li>
 +
  <li>
 +
    recursion tree。
 +
    <ul>
 +
      <li>作用:猜测运行时间;直接证明运行时间。</li>
 +
      <li>构建的步骤:中间节点;叶子节点;每层的和;层数;总合。</li>
 +
    </ul>
 +
  </li>
 +
</ol>
 +
 +
=2013年3月22日=
 +
[[媒体文件:讨论记录-第二学期-2班-第4次.pdf|[课件下载]]]
 +
<ol>
 +
  <li>
 +
    induction, recursion, recurrences。
 +
    <ul>
 +
      <li>induction、recursion和recurrences的两两关系。</li>
 +
      <li>well-ordering principle和induction的关系:反证法+well-ordering principle=induction。</li>
 +
      <li>top-down比bottom-up的优势:思路更直接;不用证明构建的完备性;base case更直接。</li>
 +
    </ul>
 +
  </li>
 +
  <li>
 +
    first-order constant coefficient linear recurrence。
 +
    <ul>
 +
      <li>结论的来源:通过递推展开来猜测。</li>
 +
      <li>结论的证明:数学归纳法。</li>
 +
    </ul>
 +
  </li>
 +
  <li>the master theorem的证明:基于递归树的时间复杂度分析。</li>
 +
</ol>
 +
 +
=2013年3月29日=
 +
[[媒体文件:讨论记录-第二学期-2班-第5次.pdf|[课件下载]]]
 +
<ol>
 +
  <li>
 +
    probability。
 +
    <ul>
 +
      <li>从集合的角度理解sample space, element, event。</li>
 +
      <li>区分probability weight和probability,并基于probability weight理解probability distribution function的三个条件。</li>
 +
      <li>uniform probability distribution的意义:probability-->counting。</li>
 +
    </ul>
 +
  </li>
 +
  <li>the principle of inclusion and exclusion:基于Venn图解释公式。</li>
 +
  <li>
 +
    conditional probability。
 +
    <ul>
 +
      <li>基于Venn图解释conditional probability和独立性。</li>
 +
      <li>independent trials process和tree diagram。</li>
 +
    </ul>
 +
  </li>
 +
  <li>random variable:理解random variable, expected value, additivity of expectation。</li>
 +
</ol>
 +
 +
=2013年4月7日=
 +
[[媒体文件:讨论记录-第二学期-2班-第6次.pdf|[课件下载]]]
 +
<ol>
 +
  <li>indicator random variable:原理与应用。</li>
 +
  <li>
 +
    随机化。
 +
    <ul>
 +
      <li>expected running time vs. average-case running time:随机算法 vs. 一般算法的所有输入。</li>
 +
      <li>随机数生成方法:计算方法;物理方法。</li>
 +
      <li>数组随机排序方法:permute-by-sorting;randomize-in-place。</li>
 +
    </ul>
 +
  </li>
 +
  <li>计算expected running time的方法:定义;indicator random variable;线性性质;条件期望。</li>
 +
  <li>
 +
    probability distributions and variance。
 +
    <ul>
 +
      <li>distribution function vs. cumulative distribution function:点和区间。</li>
 +
      <li>variance及其来源。</li>
 +
    </ul>
 +
  </li>
 +
</ol>
 +
 +
=2013年4月12日=
 +
[[媒体文件:讨论记录-第二学期-2班-第7次.pdf|[课件下载]]]
 +
<ol>
 +
  <li>快速排序。
 +
    <ul>
 +
      <li>正确性证明:loop invariant;递归程序正确性的归纳证明。</li>
 +
      <li>运行时间:worst-case;best-case;average-case。</li>
 +
      <li>随机化的快速排序:随机化的意义;期望运行时间。</li>
 +
    </ul>
 +
  </li>
 +
  <li>线性时间排序算法。
 +
    <ul>
 +
      <li>基于比较的排序:运行时间的下界。</li>
 +
      <li>counting sort:stable;从左往右扫描的改法;对输入的要求及缺点。</li>
 +
      <li>radix sort:从高位开始排序的改法;分解的灵活性;对输入的要求。</li>
 +
      <li>bucket sort:最优运行时间。</li>
 +
    </ul>
 +
  </li>
 +
  <li>选择问题:找最大、最小元;随机化的选择算法;确定性的选择算法。</li>
 +
</ol>
 +
 +
=2013年4月19日=
 +
[[媒体文件:讨论记录-第二学期-2班-第8次.pdf|[课件下载]]]
 +
<ol>
 +
  <li>dynamic set:含义;基本操作。</li>
 +
  <li>linked list。
 +
    <ul>
 +
      <li>支持的操作:search, insert, delete。</li>
 +
      <li>insert/delete的抽象实现。</li>
 +
      <li>基于数组的具体实现:多数组;单数组。</li>
 +
      <li>dynamic set操作的实现。</li>
 +
    </ul>
 +
  </li>
 +
  <li>stack。
 +
    <ul>
 +
      <li>支持的操作:test-empty, push, pop。</li>
 +
      <li>具体实现:基于数组;基于链表。</li>
 +
      <li>dynamic set操作的实现。</li>
 +
    </ul>
 +
  </li>
 +
  <li>queue。
 +
    <ul>
 +
      <li>支持的操作:test-empty, enqueue, dequeue。</li>
 +
      <li>具体实现:基于数组;基于链表。</li>
 +
      <li>dynamic set操作的实现。</li>
 +
    </ul>
 +
  </li>
 +
  <li>rooted tree。
 +
    <ul>
 +
      <li>与linked list的异同。</li>
 +
      <li>left-child, right-sibling representation的抽象实现。</li>
 +
      <li>dynamic set操作的实现。</li>
 +
    </ul>
 +
  </li>
 +
  <li>allocating and freeing objects。
 +
    <ul>
 +
      <li>意义。</li>
 +
      <li>free list的本质:基于linked list实现的stack。</li>
 +
      <li>service several linked lists with a single linked list的优缺点。</li>
 +
    </ul>
 +
  </li>
 +
</ol>
 +
 +
=2013年4月26日=
 +
[[媒体文件:讨论记录-第二学期-2班-第9次.pdf|[课件下载]]]
 +
<ol>
 +
  <li>heap、heapsort、priority queue:各算法的作用、基本原理、正确性证明、运行时间。</li>
 +
  <li>分层抽象。
 +
    <ul>
 +
      <li>priority queue <-- heap <-- array。</li>
 +
      <li>tree <-- binary tree <-- array。</li>
 +
      <li>优缺点:更简单的正确性证明 vs. 更复杂的运行时间分析。</li>
 +
    </ul>
 +
  </li>
 +
  <li>tree的前序、中序、后序遍历。</li>
 +
  <li>其它ADT:union-find;dictionary。</li>
 +
  <li>single-linkage agglomerative clustering。
 +
    <ul>
 +
      <li>最终hierarchy的保存:binary out-tree。</li>
 +
      <li>hierarchy的计算过程:priority queue (+ dictionary)。</li>
 +
      <li>计算过程的监控:union-find。</li>
 +
    </ul>
 +
  </li>
 +
</ol>
 +
 +
=2013年5月3日=
 +
[[媒体文件:讨论记录-第二学期-2班-第10次.pdf|[课件下载]]]
 +
<ol>
 +
  <li>dictionary。
 +
    <ul>
 +
      <li>操作;用途。</li>
 +
      <li>direct-address table:原理;优缺点。</li>
 +
      <li>hash table:原理;优缺点。</li>
 +
    </ul>
 +
  </li>
 +
  <li>collision。
 +
    <ul>
 +
      <li>expected number of items per location。</li>
 +
      <li>expected number of empty locations。</li>
 +
      <li>expected number of collisions。</li>
 +
    </ul>
 +
  </li>
 +
  <li>collision resolution。
 +
    <ul>
 +
      <li>chaining:原理;运行时间;优缺点。</li>
 +
      <li>open addressing:原理;三种实现方式的区别;运行时间;优缺点。</li>
 +
      <li>降低alpha的方式:扩容。</li>
 +
      <li>perfect hashing:原理;运行时间;优缺点。</li>
 +
    </ul>
 +
  </li>
 +
  <li>hash function。
 +
    <ul>
 +
      <li>目标:simple uniform hashing;depends on all the bits of the key;fast。</li>
 +
      <li>应对蓄意构造的坏情况:choose the hash function randomly。</li>
 +
    </ul>
 +
  </li>
 +
</ol>
 +
 +
=2013年5月10日=
 +
[[媒体文件:讨论记录-第二学期-2班-第11次.pdf|[课件下载]]]
 +
<ol>
 +
  <li>binary search trees。
 +
    <ul>
 +
      <li>操作;用途。</li>
 +
      <li>各操作:原理;正确性。</li>
 +
      <li>binary search tree vs. hash table:运行时间;前后继;范围搜索;排序;对输入的要求(hash function vs. total order);重hash。</li>
 +
    </ul>
 +
  </li>
 +
  <li>red-black trees。
 +
    <ul>
 +
      <li>平衡性及其原因。</li>
 +
      <li>rotation的性质。</li>
 +
      <li>插入和删除的宏观思路。</li>
 +
    </ul>
 +
  </li>
 +
</ol>
 +
 +
=2013年5月17日=
 +
[[媒体文件:讨论记录-第二学期-2班-第12次.pdf|[课件下载]]]
 +
<ol>
 +
  <li>dynamic programming。
 +
    <ul>
 +
      <li>面向的问题:优化。</li>
 +
      <li>适用的问题:有最优子结构。</li>
 +
      <li>有用的问题:子问题重复。</li>
 +
      <li>代价:空间换时间。</li>
 +
    </ul>
 +
  </li>
 +
  <li>dynamic programming的运行时间。
 +
    <ul>
 +
      <li>性能要素:子问题数量;每个子问题中的决策数量。</li>
 +
      <li>计算方法:top-down vs. bottom-up。</li>
 +
    </ul>
 +
  </li>
 +
  <li>问题实例及其四步骤。
 +
    <ul>
 +
      <li>rod cutting。</li>
 +
      <li>matrix-chain multiplication。</li>
 +
      <li>unweighted shortest/longest simple path。</li>
 +
      <li>longest common subsequence。</li>
 +
      <li>optimal binary search trees。</li>
 +
    </ul>
 +
  </li>
 +
</ol>
 +
 +
=2013年5月24日=
 +
[[媒体文件:讨论记录-第二学期-第13次.pdf|[课件下载]]]
 +
<ol>
 +
  <li>greedy algorithms。
 +
    <ul>
 +
      <li>基本原理。</li>
 +
      <li>greedy-choice property和optimal substructure。</li>
 +
      <li>效率高于动态规划:计算的子问题少。</li>
 +
      <li>实例:activity-selection和Huffman codes。</li>
 +
    </ul>
 +
  </li>
 +
  <li>amortized analysis。
 +
    <ul>
 +
      <li>与average-case analysis的异同:per operation vs. per algorithm; worst-case vs. average-case。</li>
 +
      <li>aggregate analysis:按行计算改为按列计算。</li>
 +
      <li>accounting method:在别处分摊代价。</li>
 +
      <li>potential function:全局集中的代价寄存;从accounting method的角度理解potential function。</li>
 +
      <li>实例:stack operations; incrementing a binary counter; table expansion和contraction。</li>
 +
    </ul>
 +
  </li>
 +
</ol>
 +
 +
=2013年5月31日=
 +
[[媒体文件:讨论记录-第二学期-2班-第14次.pdf|[课件下载]]]
 +
<ol>
 +
  <li>union-find的应用。
 +
    <ul>
 +
      <li>connected component。</li>
 +
      <li>how many tables。</li>
 +
      <li>the suspects。</li>
 +
    </ul>
 +
  </li>
 +
  <li>union-find的实现。
 +
    <ul>
 +
      <li>linked-list representation及其改进:weighted-union heuristic。</li>
 +
      <li>disjoint-set forests及其改进:union by rank;path compression。</li>
 +
    </ul>
 +
  </li>
 +
  <li>single-linkage agglomerative clustering的实现:优先队列+并查集+树。</li>
 +
</ol>
 +
 +
=2013年6月7日=
 +
[[媒体文件:讨论记录-第二学期-2班-第15次.pdf|[课件下载]]]
 +
<ol>
 +
  <li>用图来建模问题。</li>
 +
  <li>图的集合表示。
 +
    <ul>
 +
      <li>无向图:函数;multiset。</li>
 +
      <li>有向图:函数;multiset。</li>
 +
    </ul>
 +
  </li>
 +
  <li>图论中的术语。</li>
 +
</ol>
 +
 +
=2013年6月21日=
 +
[[媒体文件:讨论记录-第二学期-2班-第16次.pdf|[课件下载]]]
 +
<ol>
 +
  <li>图的计算机表示。
 +
    <ul>
 +
      <li>方法与优缺点:Two-dimensional array;List of lists;Dictionary of keys;Coordinate list;Yale format。</li>
 +
      <li>结合使用。</li>
 +
    </ul>
 +
  </li>
 +
  <li>图的搜索。
 +
    <ul>
 +
      <li>BFS:三种颜色的含义;BFS-tree的构建。</li>
 +
      <li>DFS:子孙关系的三个充要条件;SCC算法的原理。</li>
 +
    </ul>
 +
  </li>
 +
  <li>最小生成树:Kruskal及其实现;Prim及其实现;拟阵。</li>
 
</ol>
 
</ol>

2013年6月21日 (五) 12:40的最新版本

2013年3月1日

[课件下载]

  1. 计算问题与算法。
    • 计算问题:input + output + their relationship。
    • 算法:well-defined computational procedure for achieving an input-output relationship。
  2. 好算法。
    • 要素:正确性、高效性、易实现性。
    • 设计流程:思路-->过程-->正确性-->效率。
  3. 算法的正确性分析。
    • partially correct:基于checkpoint和invariant。
    • totally correct:partially correct + termination。
  4. 算法的效率分析。
    • RAM的要素:数据类型、数据存储方式;指令类型、指令执行方式。
    • running time的计算:cost*times;best/worst/average case。
  5. 算法效率的渐进表示法。
    • Theta, O和Omega的含义:基于集合;基于极限。
    • Theta vs. O:用O避免分情况讨论。
    • O vs. o:基于集合;基于极限。
    • 渐进表示法的比喻:大小关系;相似的性质,但无trichotomy。

2013年3月8日

[课件下载]

  1. 加法和乘法原理的应用:识别元素;识别不相交的集合。
  2. 列表、置换和子集。
    • 列表:本质是函数。
    • 置换:本质是双射函数。
    • k-元素置换:本质是列表。
    • k-元素子集:也可以看作函数。
  3. 双射在counting中的作用:元素个数不变,但更容易计算。
  4. 等价关系在counting中的作用:等价类大小相同时,可以做除法。

2013年3月15日

[课件下载]

  1. maximum-subarray problem。
    • divide、conquer和combine在这个算法中分别如何体现。
    • 找max-crossing-subarray的方式与brute-force不同,从而节约操作。
    • 运行时间的递归表示。
    • 利用recursion tree来猜测运行时间的渐进表示法。
    • 利用substitution或master theorem来证明。
  2. substitution证明的一些细节。
    • 为低阶项保留余量。
    • 恰当运用替换。
  3. recursion tree。
    • 作用:猜测运行时间;直接证明运行时间。
    • 构建的步骤:中间节点;叶子节点;每层的和;层数;总合。

2013年3月22日

[课件下载]

  1. induction, recursion, recurrences。
    • induction、recursion和recurrences的两两关系。
    • well-ordering principle和induction的关系:反证法+well-ordering principle=induction。
    • top-down比bottom-up的优势:思路更直接;不用证明构建的完备性;base case更直接。
  2. first-order constant coefficient linear recurrence。
    • 结论的来源:通过递推展开来猜测。
    • 结论的证明:数学归纳法。
  3. the master theorem的证明:基于递归树的时间复杂度分析。

2013年3月29日

[课件下载]

  1. probability。
    • 从集合的角度理解sample space, element, event。
    • 区分probability weight和probability,并基于probability weight理解probability distribution function的三个条件。
    • uniform probability distribution的意义:probability-->counting。
  2. the principle of inclusion and exclusion:基于Venn图解释公式。
  3. conditional probability。
    • 基于Venn图解释conditional probability和独立性。
    • independent trials process和tree diagram。
  4. random variable:理解random variable, expected value, additivity of expectation。

2013年4月7日

[课件下载]

  1. indicator random variable:原理与应用。
  2. 随机化。
    • expected running time vs. average-case running time:随机算法 vs. 一般算法的所有输入。
    • 随机数生成方法:计算方法;物理方法。
    • 数组随机排序方法:permute-by-sorting;randomize-in-place。
  3. 计算expected running time的方法:定义;indicator random variable;线性性质;条件期望。
  4. probability distributions and variance。
    • distribution function vs. cumulative distribution function:点和区间。
    • variance及其来源。

2013年4月12日

[课件下载]

  1. 快速排序。
    • 正确性证明:loop invariant;递归程序正确性的归纳证明。
    • 运行时间:worst-case;best-case;average-case。
    • 随机化的快速排序:随机化的意义;期望运行时间。
  2. 线性时间排序算法。
    • 基于比较的排序:运行时间的下界。
    • counting sort:stable;从左往右扫描的改法;对输入的要求及缺点。
    • radix sort:从高位开始排序的改法;分解的灵活性;对输入的要求。
    • bucket sort:最优运行时间。
  3. 选择问题:找最大、最小元;随机化的选择算法;确定性的选择算法。

2013年4月19日

[课件下载]

  1. dynamic set:含义;基本操作。
  2. linked list。
    • 支持的操作:search, insert, delete。
    • insert/delete的抽象实现。
    • 基于数组的具体实现:多数组;单数组。
    • dynamic set操作的实现。
  3. stack。
    • 支持的操作:test-empty, push, pop。
    • 具体实现:基于数组;基于链表。
    • dynamic set操作的实现。
  4. queue。
    • 支持的操作:test-empty, enqueue, dequeue。
    • 具体实现:基于数组;基于链表。
    • dynamic set操作的实现。
  5. rooted tree。
    • 与linked list的异同。
    • left-child, right-sibling representation的抽象实现。
    • dynamic set操作的实现。
  6. allocating and freeing objects。
    • 意义。
    • free list的本质:基于linked list实现的stack。
    • service several linked lists with a single linked list的优缺点。

2013年4月26日

[课件下载]

  1. heap、heapsort、priority queue:各算法的作用、基本原理、正确性证明、运行时间。
  2. 分层抽象。
    • priority queue <-- heap <-- array。
    • tree <-- binary tree <-- array。
    • 优缺点:更简单的正确性证明 vs. 更复杂的运行时间分析。
  3. tree的前序、中序、后序遍历。
  4. 其它ADT:union-find;dictionary。
  5. single-linkage agglomerative clustering。
    • 最终hierarchy的保存:binary out-tree。
    • hierarchy的计算过程:priority queue (+ dictionary)。
    • 计算过程的监控:union-find。

2013年5月3日

[课件下载]

  1. dictionary。
    • 操作;用途。
    • direct-address table:原理;优缺点。
    • hash table:原理;优缺点。
  2. collision。
    • expected number of items per location。
    • expected number of empty locations。
    • expected number of collisions。
  3. collision resolution。
    • chaining:原理;运行时间;优缺点。
    • open addressing:原理;三种实现方式的区别;运行时间;优缺点。
    • 降低alpha的方式:扩容。
    • perfect hashing:原理;运行时间;优缺点。
  4. hash function。
    • 目标:simple uniform hashing;depends on all the bits of the key;fast。
    • 应对蓄意构造的坏情况:choose the hash function randomly。

2013年5月10日

[课件下载]

  1. binary search trees。
    • 操作;用途。
    • 各操作:原理;正确性。
    • binary search tree vs. hash table:运行时间;前后继;范围搜索;排序;对输入的要求(hash function vs. total order);重hash。
  2. red-black trees。
    • 平衡性及其原因。
    • rotation的性质。
    • 插入和删除的宏观思路。

2013年5月17日

[课件下载]

  1. dynamic programming。
    • 面向的问题:优化。
    • 适用的问题:有最优子结构。
    • 有用的问题:子问题重复。
    • 代价:空间换时间。
  2. dynamic programming的运行时间。
    • 性能要素:子问题数量;每个子问题中的决策数量。
    • 计算方法:top-down vs. bottom-up。
  3. 问题实例及其四步骤。
    • rod cutting。
    • matrix-chain multiplication。
    • unweighted shortest/longest simple path。
    • longest common subsequence。
    • optimal binary search trees。

2013年5月24日

[课件下载]

  1. greedy algorithms。
    • 基本原理。
    • greedy-choice property和optimal substructure。
    • 效率高于动态规划:计算的子问题少。
    • 实例:activity-selection和Huffman codes。
  2. amortized analysis。
    • 与average-case analysis的异同:per operation vs. per algorithm; worst-case vs. average-case。
    • aggregate analysis:按行计算改为按列计算。
    • accounting method:在别处分摊代价。
    • potential function:全局集中的代价寄存;从accounting method的角度理解potential function。
    • 实例:stack operations; incrementing a binary counter; table expansion和contraction。

2013年5月31日

[课件下载]

  1. union-find的应用。
    • connected component。
    • how many tables。
    • the suspects。
  2. union-find的实现。
    • linked-list representation及其改进:weighted-union heuristic。
    • disjoint-set forests及其改进:union by rank;path compression。
  3. single-linkage agglomerative clustering的实现:优先队列+并查集+树。

2013年6月7日

[课件下载]

  1. 用图来建模问题。
  2. 图的集合表示。
    • 无向图:函数;multiset。
    • 有向图:函数;multiset。
  3. 图论中的术语。

2013年6月21日

[课件下载]

  1. 图的计算机表示。
    • 方法与优缺点:Two-dimensional array;List of lists;Dictionary of keys;Coordinate list;Yale format。
    • 结合使用。
  2. 图的搜索。
    • BFS:三种颜色的含义;BFS-tree的构建。
    • DFS:子孙关系的三个充要条件;SCC算法的原理。
  3. 最小生成树:Kruskal及其实现;Prim及其实现;拟阵。