day7：图论（下）

太过爱你忘了你带给我的痛 2024-04-17 05:22 46阅读 0赞

# day7：图论（下） #

又是自闭的一天，讲的都是几乎对于我来说是全新的，唯一一个**二分图最大匹配匈牙利算法**在暑假做题的时候偶然遇到了，然后自学了一下，其余…

**（一）：**

首先讲了昨天还剩下一点没讲完的最短路径：多源点问题 **Floyd算法**

就是用了动态规划的思想，代码简单，对于我这种记模板的小白来说是最好用不过了，直接三重for循环不断更新每两个点之间的最短路径，显然总的时间复杂度O（n^3）

**（二）:**

这个一讲完就开始我自闭的一上午了

直接上来就讲**强联通图、强联通分量**  
虽然这些理论知识以前学离散的时候都有所涉及，但是我还是太天真了  
直接上几个算法，搞的我一脸懵逼了

开始讲**连通分量**感觉还好，直接用一下**DFS**就能判断一个**无向图中有多少个连通分量**

接下来的强联通分量，感觉听上去还好，但是我想多了

前提：**前连通分量是针对有向图而言**

至于判断有向图是不是强联通图，直接用DFS感觉就可以，

但是如果有向图没强连通，即：**非强连通有向图的极大连通子图称为强连通分量**

重点来了，**求非强联通有向图的强连通分量**

**两种算法：  
1、Kosaraju算法：两次DFS，实现较容易  
2、Tarjan算法：一次DFS，实现较复杂，  
还有一种Tarjan算法的改进版，但是我并没有看**

至于这两种算法，也只是在下午了解了下原理，代码实现一直都没来得急。。。

1、Kosaraju算法：对有向图和它的逆图实施两次DFS  
时间复杂度O（N+M）

2、Tarjan算法：感觉还是挺巧妙的，在DFS时，运用了一个栈，进行相关操作

保留两个大佬的博客，到时候等有时间的时候，一定要找些题，用代码实现下:

[传送门1][1]

[传送门2][2]

讲完连通分量之后，有稍微介绍了下：**双连通分量**，调用Tarjan算法稍微变形

**（三）:**

终于能让我缓缓了，接下来的二分图，由于暑假有自学到，于是感觉还挺简单的，但是还是好多东西没掌握，只是小巫见大巫

虽然二分图匹配问题：**匈牙利算法**有所了解，但是只是了解了它的**DFS**实现，但是没了解它的**BFS**实现

回到二分图…

只要是：

二分图最大匹配——匈牙利算法

最小点覆盖=最大匹配数——匈牙利算法

最大独立集=顶点数-最大匹配数——匈牙利算法

最小路径覆盖数=原图点数-新图最大匹配数——匈牙利算法

针对这个，下午做了几道有代表性的简单题

具体见这篇博客：[https://blog.csdn.net/boliu147258/article/details/100006006][https_blog.csdn.net_boliu147258_article_details_100006006]

虽然**匈牙利算法**掌握的差不多了，但是关于匈牙利的改进算法：**Hopcroft-Karp算法**  
以及在带权的二分图找权值最大的完备匹配算法：**KM（Kuhn-Munkres）算法**  
还是没有掌握，这一下子要补的东西越来越多了

**（四）：**

**网络流**

好吧，没来得及看， 关键是太懒了，  
找了一篇博客，以后回来补吧…

[https://www.cnblogs.com/fzl194/p/8855085.html][https_www.cnblogs.com_fzl194_p_8855085.html]

[1]: https://www.cnblogs.com/five20/p/7594239.html
[2]: https://edwiv.com/archives/564
[https_blog.csdn.net_boliu147258_article_details_100006006]: https://blog.csdn.net/boliu147258/article/details/100006006
[https_www.cnblogs.com_fzl194_p_8855085.html]: https://www.cnblogs.com/fzl194/p/8855085.html

发表评论取消回复

表情：

评论列表（有 0 条评论，46人围观）

还没有评论，来说两句吧...

相关阅读

相关 day7：图论（下）

day7：图论（下）又是自闭的一天，讲的都是几乎对于我来说是全新的，唯一一个**二分图最大匹配匈牙利算法**在暑假做题的时候偶然遇到了，然后自学了一下，其余… *...

太过爱你忘了你带给我的痛/ 2024年04月17日 05:22/ 0 赞/ 47 阅读

相关图论

一、图的常用概念　　1、顶点（vertex）　　2、边（edge）　　3、路径　　4、无向图：顶点之间的连接没有方向　　![1007094-201909

柔光的暖阳◎/ 2023年10月10日 07:53/ 0 赞/ 77 阅读

相关图论基础

图图由节点和图构成；有向图：连线有方向；不对称性；无向图：连线无方向；是有向图的一种特殊请情况；有权图：连线有权值；无权图：连线无权值；简

柔情只为你懂/ 2023年08月17日 17:48/ 0 赞/ 154 阅读

相关图论之欧拉图

欧拉路径/欧拉回路欧拉路径是一条经过图中所有边且只经过一次的路径（类似于一笔画问题）；欧拉回路的话就是起点和终点相同的欧拉路径欧拉通路（欧拉路径）：S点到T点的

蔚落/ 2023年08月17日 16:26/ 0 赞/ 168 阅读

相关数据分析疫情图——day7

数据分析疫情图——day7 一. 异常二 . 集合API 三. Map接口四.简单爬取页面数据前言

素颜马尾好姑娘i/ 2023年01月08日 09:27/ 0 赞/ 133 阅读

相关图论方法应用

声明：本博客题目和题解均来自www.acwing.com，侵权联删。各种图论题目最合适的解法如下： ![在这里插入图片描述][watermark_type_ZmFu

小鱼儿/ 2022年10月17日 00:54/ 0 赞/ 155 阅读

相关图论

http://[blog.csdn.net/pipisorry/article/details/52518118][blog.csdn.net_pipisorry_articl

清疚/ 2022年09月25日 15:21/ 0 赞/ 261 阅读

相关图论算法

Problem1一笔画问题题目描述给出一个图，求其欧拉回路（若没有回路，则求其欧拉路径），若不存在则输出‘No solution’ 输入输入的第一

妖狐艹你老母/ 2022年01月06日 22:13/ 0 赞/ 272 阅读

相关 day 6：图论（上）

day 6：图论（上）今天讲的还是挺简单的，但是还是对Prim算法不熟练，这应该是要闭着眼都得会的模板啊… 然后，在求最短路径时，如果存在负权时：Dijkstra算法

叁歲伎倆/ 2021年10月30日 06:12/ 0 赞/ 247 阅读

相关图论重点复习

一、重点概念 1、图：一个图是一个序偶（V，E），记为G=( V , E),其中：（1） V是一个有限的非空集合，称为顶点集合,其元素称为顶点或点。用|V|表示顶点

冷不防/ 2021年09月26日 18:36/ 0 赞/ 1137 阅读