什么是二分图?
二分图(Bipartite Graph)是一种特殊的图结构,其中的顶点可以分为两个不相交的集合 U 和 V,图中的每条边都连接着一个来自集合 U 的顶点和一个来自集合 V 的顶点。这种结构使得二分图特别适合用于建立各种合适的匹配关系,包括工人和工作岗位之间的关系。
二分图的基本特性
- 无奇环:二分图中不存在奇数长度的环。这个特性使得二分图在许多算法(如最大匹配)中表现出色。
- 匹配:可以将集合 U 中的顶点与集合 V 中的顶点一一匹配,以最大化匹配的数量。
工厂中的应用场景
在工厂中,工人技能与生产加工站位之间的对应关系可以用二分图来表示。例如,工厂有一组工人,每个工人具备不同的技能。同时,工厂也有多个加工站位,这些站位需要特定的技能来完成任务。通过建立二分图,我们可以有效地安排工人的排班计划,并确保每个岗位都有合适的工人。
实例设计
假设我们有以下工人和相关的加工站位:
工人:
- 工人 A:具备焊接技能
- 工人 B:具备装配技能
- 工人 C:具备焊接与检验技能
- 工人 D:具备装配与焊接技能
加工站位:
- 加工站 1:需要焊接技能
- 加工站 2:需要装配技能
- 加工站 3:需要检验技能
建立二分图模型
根据工人技能和加工站位的需求,我们可以建立如下的二分图:
- 工人 A 连接 加工站 1(焊接)
- 工人 B 连接 加工站 2(装配)
- 工人 C 连接 加工站 1(焊接)、加工站 3(检验)
- 工人 D 连接 加工站 2(装配)、加工站 1(焊接)
C# 实现最大匹配算法
下面是一个使用 C# 编写的示例,利用 Hopcroft-Karp 算法来找到最大匹配,并为工人分配对应的加工站位。
C# 代码实现
using System;
using System.Collections.Generic;
class BipartiteGraph
{
private int _uVertices; // 工人(集合 U)的数量
private int _vVertices; // 加工站(集合 V)的数量
private List[] _adjacencyList; // 邻接表
public BipartiteGraph(int uVertices, int vVertices)
{
_uVertices = uVertices;
_vVertices = vVertices;
_adjacencyList = new List[uVertices];
for (int i = 0; i < uVertices; i++)
{
_adjacencyList[i] = new List();
}
}
public void AddEdge(int u, int v)
{
_adjacencyList[u].Add(v); // 添加边
}
private bool BFS(int[] pairU, int[] pairV, int[] dist)
{
Queue queue = new Queue();
for (int u = 0; u < _uvertices u if pairuu='= -1)' distu='0;' queue.enqueueu else distu='int.MaxValue;' dist-1='int.MaxValue;' while queue.count> 0)
{
int u = queue.Dequeue();
if (dist[u] < dist[-1])
{
foreach (var v in _adjacencyList[u])
{
if (dist[pairV[v]] == int.MaxValue)
{
dist[pairV[v]] = dist[u] + 1;
queue.Enqueue(pairV[v]);
}
}
}
}
return (dist[-1] != int.MaxValue);
}
private bool DFS(int[] pairU, int[] pairV, int[] dist, int u)
{
if (u != -1)
{
foreach (var v in _adjacencyList[u])
{
if (dist[pairV[v]] == dist[u] + 1)
{
if (DFS(pairU, pairV, dist, pairV[v]))
{
pairV[v] = u;
pairU[u] = v;
return true;
}
}
}
dist[u] = int.MaxValue;
return false;
}
return true;
}
public int HopcroftKarp()
{
int[] pairU = new int[_uVertices];
int[] pairV = new int[_vVertices];
int[] dist = new int[_uVertices + 1];
for (int i = 0; i < _uVertices; i++)
{
pairU[i] = -1; // 初始化配对
}
for (int i = 0; i < _vVertices; i++)
{
pairV[i] = -1; // 初始化配对
}
int matching = 0;
while (BFS(pairU, pairV, dist))
{
for (int u = 0; u < _uVertices; u++)
{
if (pairU[u] == -1 && DFS(pairU, pairV, dist, u))
{
matching++;
}
}
}
return matching;
}
public void PrintMatches(int[] pairU)
{
Console.WriteLine("工人与加工站位的匹配情况:");
for (int i = 0; i < _uVertices; i++)
{
if (pairU[i] != -1)
{
Console.WriteLine($"工人 {i} 匹配到 加工站 {pairU[i]}");
}
}
}
}
class Program
{
static void Main(string[] args)
{
// 创建二分图,工人有 4 人,加工站有 3 个
BipartiteGraph bg = new BipartiteGraph(4, 3);
// 添加工人与加工站位的边
bg.AddEdge(0, 0); // 工人 A 连接到 加工站 1
bg.AddEdge(1, 1); // 工人 B 连接到 加工站 2
bg.AddEdge(2, 0); // 工人 C 连接到 加工站 1
bg.AddEdge(2, 2); // 工人 C 连接到 加工站 3
bg.AddEdge(3, 1); // 工人 D 连接到 加工站 2
bg.AddEdge(3, 0); // 工人 D 连接到 加工站 1
// 运行最大匹配算法
int maxMatching = bg.HopcroftKarp();
Console.WriteLine("最大匹配数: " + maxMatching);
// 打印匹配结果
int[] pairU = new int[4];
bg.PrintMatches(pairU);
}
}
代码说明
- Graph Initialization:初始化一个二分图,传入工人和加工站位的数量。
- AddEdge():添加工人与加工站之间的边,以表示技能匹配。
- BFS() 和 DFS():这些方法用于实现 Hopcroft-Karp 算法以查找最大匹配。
- HopcroftKarp():执行算法并返回最大匹配的数量。
- Main():测试所实现的程序,创建工人与加工站位的连接,并输出最大匹配数量及匹配结果。
总结
二分图在工厂排班问题上的应用,能够有效地解决工人技能与加工站位之间的匹配关系。在上述示例中,我们利用 C# 实现了相应的算法,并演示了如何构建匹配关系。通过这种方式,工厂可以更高效地分配人力资源,优化生产流程。