图论里匈牙利算法 V1←{x0}，V2←∅ 是什么意思？
答案:1 悬赏:80 手机版
解决时间 2021-11-21 04:32
- 提问者网友：心如荒岛囚我终老
- 2021-11-20 15:08
图论里匈牙利算法 V1←{x0}，V2←∅ 是什么意思？
最佳答案
- 五星知识达人网友：逃夭
- 2021-11-20 16:24
V1,V2是两个点集.
其实匈牙利的本质就找用增广路.
所谓增广路,其实是这样一种路径:这条路径的起点和终点所连的边为虚边,而其余每一个点连的两条边都是一虚一实.实边是已匹配边,虚边是可以匹配但未匹配的边.
A ... B --- C ... D
这就是一条增广路.
找到增广路之后,只需要把其中的实边变成虚边,虚边变成实边,就可以实现找到新的一个匹配.
A ... B --- C ... D => A --- B ... C --- D
其实匈牙利的本质就找用增广路.
所谓增广路,其实是这样一种路径:这条路径的起点和终点所连的边为虚边,而其余每一个点连的两条边都是一虚一实.实边是已匹配边,虚边是可以匹配但未匹配的边.
A ... B --- C ... D
这就是一条增广路.
找到增广路之后,只需要把其中的实边变成虚边,虚边变成实边,就可以实现找到新的一个匹配.
A ... B --- C ... D => A --- B ... C --- D
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
大家都在看
推荐资讯