什么是二分图？
二分图（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# 实现了相应的算法，并演示了如何构建匹配关系。通过这种方式，工厂可以更高效地分配人力资源，优化生产流程。
