# km

**Repository Path**: xzming/km

## Basic Information

- **Project Name**: km
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2021-03-26
- **Last Updated**: 2021-03-26

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# Introduction

Kuhn-Munkres算法，也称KM算法，是Kuhn和Munkres二人在1955～1957年各自独立提出的一种算法，是一种求解最大最小权匹配问题的经典算法。最初的Kuhn-Munkres算法以矩阵为基础结构，但是Edmonds在1965年发布了匈牙利算法之后，Kuhn-Munkres算法也基于匈牙利算法进行了改进。当给定的二部图存在完美匹配的情况下，Kuhn-Munkres算法通过给每个顶点设置一个标号（叫作顶标）的方式把求最大权匹配的问题转化为求完美匹配的问题的，最终得到一个最大权完美匹配。