首页| JavaScript| HTML/CSS| Matlab| PHP| Python| Java| C/C++/VC++| C#| ASP| 其他|
购买积分 购买会员 激活码充值

您现在的位置是:虫虫源码 > Java > 在 java 中的 Hopcroft 卡普算法的实现

在 java 中的 Hopcroft 卡普算法的实现

  • 资源大小:14.96 kB
  • 上传时间:2021-06-29
  • 下载次数:0次
  • 浏览次数:0次
  • 资源积分:1积分
  • 标      签: Java开发 java 算法 实现

资 源 简 介

Hopcroft — — 卡普算法是作为一种算法输入二部图,并生成作为输出最大基数匹配 — — 一套尽可能多尽可能边缘没有两个边缘份额的财产终结点。它运行在 O (|E|sqrt {|V |})在最坏的情况,在那里 E 一套在图中,边和 V 设置关系图的顶点数的时间。在稠密图时间绑定变成 O (|荧光 ^ {2.5}),和它运行在接近线性时间的随机图论。该算法被发现由约翰 Hopcroft 和理查德 · 卡普 (1973 年)。与以前的方法,用于匹配匈牙利算法和埃德蒙兹 (1965 年) 的工作,Hopcroft — — 卡普算法一再增加部分通过寻找增加路径匹配的大小。然而,而不是寻找只是单一的增广路径,每个迭代,该算法发现最短增广路径最大集。因此需要只有 O(sqrt{n}) 迭代。同样的原则也用于开发更为复杂的算法,对于非二部图匹配随着运行时间作为 Hopcroft — — 卡普算法相同的渐近。

文 件 列 表

HopcroftKarp-master
build.xml
manifest.mf
nbproject
src
VIP VIP
  • 大智若愚 4小时前 成为了本站会员

  • Mason 6小时前 成为了本站会员

  • 7小时前 成为了本站会员

  • Half_Punch 1天前 成为了本站会员

  • liqing71718 1天前 成为了本站会员

  • 伟国 1天前 成为了本站会员

  • songy 1天前 成为了本站会员

  • 纯色幽默 1天前 成为了本站会员

  • odd? 1天前 成为了本站会员

  • 52JOY... 1天前 成为了本站会员

0.177076s