图论算法
图结构
基本概念
定义
图论(Graph Theory)是离散数学的一个分支，是一门研究图(Graph)的学问
图的分类
- 有无方向
- 有向图
- 无向图
- 有无权重
- 无权图
- 有权图
连通性
图论中，连通图基于连通的概念，在一个无向图G中，若从顶点i到顶点j有路径相连(当然从j到i也一定有路径)，则称i和j是连通的
如果图中任意两点都是连通的，那么图被称作连通图，如果此图是有向图，则称为强连通图
完全图
完全图是一个简单的无向图，其中每对不同的顶点之间都恰连有一条边相连
图的表示
图的表示方式有两种：二维数组表示(邻接矩阵)、链表表示(邻接表)
邻接矩阵
邻接表
十字链表[有向图]
图的类型
欧拉图
回路与通路的定义：
- 欧拉通路(欧拉路径): 通过图中所有边恰好一次且行遍所有顶点的通路
- 欧拉回路: 通过图中所有边恰好一次且行遍所有顶点的回路
欧拉图与半欧拉图：
- 欧拉图(Eulerian graph): 具有欧拉回路的图称
- 半欧拉图(semi-Eulerian graph): 具有欧拉通路但不具有欧拉回路的图
欧拉回路是欧拉路径，欧拉路径不一定是欧拉回路
特征
在无向图中：
- 无向图G为
欧拉图，当且仅当G为连通图且所有顶点的度为偶数 - 无向图G为
半欧拉图，当且仅当G为连通图且除了两个顶点的度为奇数之外，其它所有顶点的度为偶数
在有向图中
- 有向图G为
欧拉图，当且仅当G为连通图且所有顶点的入度等于出度 - 有向图G为
半欧拉图，当且仅当G为连通图且存在某一顶点的入度比出度大1，还存在另一个顶点的入度比出度小1，而其它所有顶点的入度等于出度
对于有向图的半欧拉图，它的欧拉路径的起点的度是出度=入度+1，终点的度是入度=出度+1
Hierholzer算法
用于寻找欧拉路径或欧拉回路(该算法假定图有欧拉路径或欧拉回路)，其流程如下：
- 从起点出发，进行深度优先搜索(DFS)
- 每次沿着某条边从某个顶点移动到另外一个顶点的时候，都将这条边标记为已走过
- 如果遇到阻塞(即当前顶点没有后续邻边或该顶点的邻边都走过)，则将当前顶点加入到栈中，并回溯到上一顶点查找其可移动到的顶点
哈密顿图
回路与通路的定义：
- 哈密顿路: 给定无向图G中，通过图中每个结点一次而且仅一次的路径
- 哈密顿回路: 给定无向图G中，通过图中每个结点一次而且仅一次的回路
哈密顿(Hamilton)图与半哈密顿图：
- 哈密顿图: 具有哈密顿回路的图
- 半哈密顿图: 有哈密顿路径而没有哈密顿回路的图
哈密尔顿图和半哈密尔顿图是连通图
哈密顿图和欧拉图联系
两者都是遍历问题，但是
欧拉图考虑的是边，而哈密顿考虑的是结点同时判定欧拉图具有充要条件，但哈密顿图没有简单的充要条件，只有必要条件和充分条件
二部图
定义
二分图又称作二部图，是图论中的一种特殊模型
设G=(V, E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边(i, j)所关联的两个顶点i和j分别属于这两个不同的顶点集($i \in A$，$j \in B$)，则称图G为一个二分图
竞赛图(有向完全图)
定义
竞赛图也叫有向完全图。每对顶点之间都有一条边相连的有向图称为竞赛图
简单的性质：
竞赛图没有自环，没有二元环，若竞赛图存在环，则一定存在三元环
如果存在一个环大于三元，那么一定存在另一个三元的小环
任意竞赛图都有哈密顿路径(经过每个点一次的路径，不要求回到出发点)
图存在哈密顿回路的充要条件是强联通
哈密顿问题中，对于n阶竞赛图，当n大于等于2时一定存在哈密顿通路
acm题目
题目大意：
现在有比赛，所有队伍两两进行比赛，赢的积2分，输的积0分，如果平局的话就各自都积1分
现在给出每只队伍的得分情况，判断是否合法
思路：
- 给出的 m 个队伍可以构成一个竞赛图，问得分情况是否合法实质是在问竞赛图是否合法
- 根据竞赛图的
兰道定理，将得分视为比分序列，将所有得分进行排序，然后依次处理 - 由于每次比赛胜利都会使得总分 +2，那么前i只队伍的得分情况必须大于等于 i*(i-1)
- 当判断到最后一只队伍时，有前 n-1 只队伍的得分必须大于 n*(n-1)
遍历算法
深度搜索
广度搜索
最短路径算法
Floyd
Dijkstra
最小生成树算法
Prim
Kruskal
关键路径
拓扑排序
二分图匹配
配对
匈牙利算法
中心性算法
社区发现算法
标签传播算法LPA
标签传播算法(Label Propagation Algorithm，简称 LPA)是一个在图中快速发现社群的算法
