关键词：
一般图较二分图来说，一般图内可以有偶环，也可以有奇环，任何一个无向图都可以称为一般图，这里主要说明的是一般图匹配算法。
一般图图匹配
说明：了解一般图匹配，建议先了解二分图及其匹配等知识点。可以移步二分图匹配。
在二分图中，二分图的匹配已经解决了只有偶环图的匹配，但一般图与二分图不同的是，一般图可能有奇环，那么只要解决了奇环匹配的问题就可以实现一般图的匹配，理论上来讲，一般图的匹配也能解决二分图的匹配。
一般图最大匹配与带花树算法
带花树算法的思想是，每次在图中找到一个未匹配的点，如果能在图中找到另一个未匹配的点与它匹配，则匹配成功，与匈牙利算法很相似。带花树算法是基于图的染色来实现的，每次将一个未匹配的点染成黑色，放进队列里，然后bfs找其他点，染成白色然后找匹配点，最后保证一黑一白的点可以匹配。
类比匈牙利算法，带花树算法有两个关键的数组：
$vis[i]$ 表示 $i$ 号点染成了什么颜色，$0$ 表示未染色，$1$ 表示染成黑色，$2$ 表示染成白色。
$match[i]$ 表示 $i$ 号点的匹配点的序号。
同时带花树算法和匈牙利算法一样也有时间戳的概念，即每次给某一个未匹配的点找匹配点时会进入新的时间戳，在带花树算法中，用每次初始化 $vis$ 数组来表示进入新的时间戳，初始化为0.
机器学习｜数学基础mathematicsformachinelearning系列之图论：图的基本概念
目录前言1.2基本概念1.2.1图定义1.1：图的定义定义1.2有向边/无向边有向图/无向图/混合图补充定义1.3：子图定义1.4：顶点导出子图定义1.5：边导出子图1.2.2顶点的次数（或度）定理1.1：握手定理推论1.1推论1.21.2.3同构定义1.6：图的... 查看详情
机器学习｜数学基础mathematicsformachinelearning系列之图论（11）：欧拉图
文章目录前言系列文章6.1欧拉图定义6.1巡回欧拉巡回欧拉图欧拉道路定理6.1推论6.1结语前言Hello！小伙伴！非常感谢您阅读海轰的文章，倘若文中有错误的地方，欢迎您指出～ 自我介绍ଘ(੭ˊᵕˋ)੭昵称：... 查看详情
mt90图论基础知识及相关例题
此讲适合参加全国联赛二试的同学介绍图论和我们学习的一般的知识点比如函数一样，首先要介绍一些定义，只是图论里的定义相对较多，这里给出部分在竞赛中常用到的：就像学函数的时候，学了定义和相关概念后我们要学一... 查看详情
离散数学图论
w 如何学习数据结构？-知乎 https://www.zhihu.com/question/21318658/answer/63652147 作者：知乎用户链接：https://www.zhihu.com/question/21318658/answer/63652147来源：知乎著作权归作者所有。商业转载请联系作者获得授权，非商业转载... 查看详情
机器学习｜数学基础mathematicsformachinelearning系列之图论（12）：有向欧拉图
文章目录前言系列文章6.3有向欧拉图定于6.2有向巡回有向欧拉巡回有向欧拉图有向欧拉道路定理6.4推论6.4结语前言Hello！小伙伴！非常感谢您阅读海轰的文章，倘若文中有错误的地方，欢迎您指出～ 自我介绍... 查看详情
想了解概率图模型？你要先理解图论的基本定义与形式
...，通常用来描述某些事物之间的某种特定关系。而在机器学习的世界里，我们希望从数据中挖掘出隐含信息或模型。因此，如果我们将图中的结点作为随机变量，连接作为相关性关系，那么我们就能构造出图模型，并期望解决这... 查看详情
图论问题复习总结
图论问题复习总结图论梗概：大类上，图的概念(重心，直径，LCA等)，最短路，最小生成树，图的连通性(圆方树等)，二分图(图的匹配)，网络流；杂项上，2-SAT，prufer序列，欧拉回路，矩阵树定理，拆点/边，哈密顿路，树hash，... 查看详情
普及常见图论算法整理(代码片段)
目录约定一般连通无向图的信息、操作遍历联通块二分图判定割点割边点双边双有向图信息、操作拓扑排序强连通分量、缩点简单树论直径重心约定我是怎么存图的呢？普通的邻接表。constintN=1e5+15;//点数constintM=1e6+15;//边数intct,h... 查看详情
机器学习｜数学基础mathematicsformachinelearning系列之图论：图的矩阵表示
目录前言系列文章1.3图的矩阵表示1.3.1邻接矩阵无向图的邻接矩阵小结有向图的邻接矩阵小结加权有向图的带权邻接矩阵1.3.2关联矩阵无向图的关联矩阵有向图的关联矩阵1.3.3边矩阵结语前言Hello！小伙伴！非常感谢您阅读海轰的... 查看详情
图论概述和spfa(代码片段)
...FA2019-12-28PoweredbyGauss1.图论——最短路图论是信息学学习过程中不可或缺的一个部分。图论的应用是非常广泛的，在现实生活中大家处处都能遇到，例如电子地图，机票查询等。现在的算法竞赛考试的范围是无边无际，但主... 查看详情
各种图论模型及其解答（转）
.../uid-9112803-id-411340.html摘要：本文用另一种思路重新组织《图论及其应用》相关知识。首先，用通俗化语言阐述了如何对事物间联系的问题进行图论建模；接着从现实例子出发，给出 各种典型图论模型，每种图论模型对应于图... 查看详情
简谈图论重要性(代码片段)
从外地学习回来，我对图论才有认识（以前就没接触过，非常尴尬），说实话，学好图论的重要性，就像学数学时在进行解析几何时，图极有可能是打开答案的最后秘钥，也就是数形结合，而懂的人永远明白，用图解决绝对比用... 查看详情
图论算法
图论〔GraphTheory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间... 查看详情
图论最短路总结(代码片段)
写在前面：图论题的调试真感人让我们进入正题最短路是啥emmm顾名思义最短路就是求一个点到另外一个点的最小距离一般来说最短路分为：单源最短路和多源最短路单源最短路就是求一个源点到另外多个点的最短距离而多源最... 查看详情
信息学赛培|06信息学复赛必备的图结构实现方式
...未来工作发展，提升孩子的综合能力。前面一节课，我们学习了图论的基本理论，讲解了图论的存储结构，这一节课，我们通过C++来实现一下，在信息学复赛中，如何编写图结构代码，以及如何输入图结构数据。1预备知识讲解... 查看详情
关于图论的若干巴拉巴拉
最近课堂上正在讲图论先安利MIT课程：http://open.163.com/special/opencourse/algorithms.html因为本人对图论的概念并不是很清楚，所以还是整理一下吧。1.图论的基本概念几种常见的图的分类：类型边允许多重边允许环简单图无向 否 ... 查看详情
解题报告图论专题
图论500题http://blog.csdn.net/luomingjun12315/article/details/47438607【最小生成树+并查集】1、hdu1856 基础并查集★ /*转化为图论模型求一个图的最大联通分量用并查集，每个联通分量用一个集合维护，最后求集合元素个数的最大... 查看详情
结论图论相关结论
一、生成树相关 1.完全图生成树计数n^n-2 2.左边n个点右边m个点的完全图生成树计数(n^m-1)*(m^n-1) 3..... …… 查看详情