danieldzzz/bipartite

bipartite 图的 PHP 实现

维护者

详细信息

github.com/danielzzz/bipartite-matching

源代码

问题

安装: 0

依赖: 0

建议者: 0

安全: 0

星标: 0

关注者: 1

分支: 0

开放问题: 0

1.0.0 2022-08-19 21:45 UTC

Requires (Dev)

MIT 1afbf340ebb4e32bf3ffb9518534d197529f324e

  • daniel <daniel.woop@zelisko.net>

This package is auto-updated.

Last update: 2024-09-20 02:28:44 UTC

README

接受一个无权 bipartite 图作为输入，并返回最大基数匹配。

这是 Hopcroft-Karp bipartite 匹配算法的 PHP 实现。
https://en.wikipedia.org/wiki/Hopcroft%E2%80%93Karp_algorithm

安装

composer require danielzzz/bipartite

实际应用

此算法可用于例如，当组 A 的每个成员需要与组 B 的人进行多次会议时，最大化会议数量。

$input = [
    'personA' => ['person3', 'person1'],
    'personB' => ['person3'],
    'personC' => ['person4', 'person2'],
    'personD' => ['person2']
];

$bipartite = new Bipartite();
$result = $bipartite->match($input);

/*
result:
^ array:4 [
  "personA" => "person1"
  "personC" => "person4"
  "personD" => "person2"
  "personB" => "person3"
]

*/

测试

composer test