欧拉路径
性质：
不重复边，遍历所有边
条件：
无向图中，没有度数为奇数的点，或只有两个度数为奇数的点（一个起点一个终点）。
有向图中，各个点的出度与入度相等，或只有一个点出度比入度多一（起点），一个点入度比出度多一（终点）。
欧拉回路
性质：
不重复边，遍历所有边，回到起点
条件：
无向图中，没有度数为奇数的点。
有向图中，各个点出度等于入度。
哈密顿路径
不重复点，遍历所有点
NPC问题
哈密顿回路
不重复点，遍历所以点，回到起点
算法：
kruskal
prim
例题：
poj2349（北极的网络）kruskal模板
kosaraju
思路：
正反DFS
正向DFS得到逆序
据此反向DFS，每次反向DFS都是一组强连通分量
tarjan
任何一个强连通分量，必定是原图的深度优先搜索树的子树。确定每个强连通分量的子树的根，然后根据这些根从树的最低层开始，一个一个的拿出强连通分量。
gabow
例题：
poj2186（最受欢迎的奶牛）强连通分量（染色缩环）+DFS
路径 欧拉路径性质：不重复边，遍历所有边条件：无向图中，没有度数为奇数的点，或只有两个度数为奇数的点（一个起点一个...
图的存储 邻接矩阵 邻接表 图的遍历 DFS（双向DFS） BFS（剪枝） 单源最短路径算法 dij 条件：无负权...
BFS 优化： 双向BFS注意点： 每轮遍历整层； 每轮选取已搜索点数少的一边搜一层； DFS 优化： 剪枝这里以...
强连通分量 POJ 3180: The Cow Prom找出有多少个点数大于等于2的scc即可。代码如下 POJ ...
摘要：二分图的概念：二分图又称作二部图，是图论中的一种特殊模型 二分图的概念：二分图又称作二部图，是图论中的一种特...
摘要: [图论] [网络爬虫] [图的遍历] 图论 说到图论,必须要提的就是KonigsBerg七桥问题,简单说就...
图论介绍 一、图的概念 图是一种特殊的数据结构，由节点和边组成 图论涉及的研究领域如下举例 二、图的分类 1). ...
廿八学会 - 《宇宙图论》只是想将一切看得更清晰些（微信公众号：宇宙猜想） 《宇宙图论》目录 大目录 一、宇宙图论...
iOS实录16：GCD使用小结（二） iOS实录16：GCD使用小结（二）
离散数学包括数理逻辑，集合论，图论，近世代数。 图论 哥尼斯堡七桥问题（图论的起源）：只有每个点的度都是偶数的情况...
本文标题：图论小结（二）
本文链接：https://www.haomeiwen.com/subject/prdabftx.html
网友评论