图论 - smartxxyx的专栏 - 博客频道 - CSDN.NET

图的匹配问题与最大流问题(五)――计算二分图的最大匹配

介绍二分图最大匹配的解法，一是最大流算法来计算，二是匈牙利算法来计算，最后Java实现。...

2013-07-31 20:38 阅读(833) 评论(0)

图的匹配问题与最大流问题（四）――计算图的边连通度和点连通度

前三篇文章内容，（一）讲述了基础概念；（二）介绍了最大流算法的实现原理以及证明；（三）用Java语言予以了实现。这里，我们讲述如何利用最大流算法来求图的点连通度和边连通度，有图有代码，呵呵...

2013-07-25 15:22 阅读(881) 评论(0)

图的匹配问题与最大流问题（三）――最大流问题Ford-Fulkerson方法Java实现

上篇文章主要介绍了Ford-Fulkerson方法的理论基础，本篇给出一种Java的实现。改写一下，原来的太冗余了。...

2013-07-10 18:52 阅读(919) 评论(6)

图的匹配问题与最大流问题（二）――最大流问题Ford-Fulkerson方法

本篇承接上一篇文章，主要讲解最大流问题的Ford-Fulkerson解法。可是说这是一种方法，而不是算法，因为它包含具有不同运行时间的几种实现。该方法依赖于三种重要思想：残留网络，增广路径和割。本文将会详细介绍这些内容，下一篇文章我们提供一种该方法的Java实现。...

2013-07-10 18:22 阅读(2510) 评论(1)

图的匹配问题与最大流问题(一)

准备写个系列，关于图的匹配，最大流，线性规划等这些图论中的重要而且有着千丝万缕连续的问题，顺便介绍求图的最大匹配问题的著名的匈牙利算法。算是对前段时间学习的一个小结吧。（对内容进行了部分修改，原来使用Word编辑的公式这里无法显示，只能截图了）...

2013-07-08 21:06 阅读(1417) 评论(0)

计算任意一个图生成树的个数――Kirchhoff 的Matrix Tree 方法Java实现

计算任意一个图的生成树的个数，是Kirchhoff提出的理论，通常称为Matrix Tree Theorem，原理很简单： Let G be a graph with V(G)={v1,v2,...,vn},let A={aij}be the adjacentcy matrix of G,and let C={cij}be the n*n matrix, where cij=deg vi if...

2013-04-19 10:07 阅读(400) 评论(0)

最小生成树算法――Kruskal算法Java实现

闲来无事，写个算法，最小生成树的Kruskal算法，相对比Prim算法实现起来麻烦一点点package trees; import java.util.HashMap; import java.util.HashSet; import java.util.Map; import java.util.PriorityQueue; import java.util.Set; /** * 最小生成树...

2013-04-18 21:00 阅读(502) 评论(0)

算法之强连通分支

深度优先搜索有一种经典的应用：把一个有向图分解为各强连通分支。很多有关有向图的算法都是从这种步骤开始的。（算法导论P338，觉得简洁而精妙，分享下） STRONGLY-CONNECTED-COMPONENTS(G) 1 call DFS(G) to compute finishing times f[u] for each vertex u 2 compute GT       3 cal...

Read full article from 图论 - smartxxyx的专栏 - 博客频道 - CSDN.NET