图基本算法(一) 图的基本算法实现
yuyutoo 2024-10-12 00:58 9 浏览 0 评论
本文是学习 Algorithms on Graphs 的笔记。
图表示
邻接矩阵
邻接表
边链表
不同的表示方式决定了不同操作的时间复杂度。
图遍历
问题：我们怎么能够找到 A 能够达到的所有顶点？
算法描述：
上面的算法还需要解决两个问题：
怎么记录哪些边 / 顶点已经访问过了？
以什么顺序来访问新加进来的顶点？
我们可以通过一个 map 来记录顶点是否访问过，而对于新增的顶点，我们采样深度优先的方案，一直访问下去。
DFS
如果我们要访问图中所有的点，方法如下：
Previsit and Postvisit Functions
我们在 explore 节点的时候，加上 Previsit 和 Postvisit 功能：
根据这个功能我们就可以实现一个时钟:
连通性
问题
我们可以通过修改 DFS 来做
Directed Acyclic Graphs 有向非循环图
定义：
A source is a vertex with no incoming edges.
A sink is a vertex with no outgoing edges.
现在我们的目标是找到一个 Linear Ordering，什么叫 Linear Ordering，看下图：
怎么找呢？根据 sink 的概念，我们先去找 sink
整个过程如下：
Find sink.
Put at end of order.
Remove from graph.
Repeat.
整个算法如下：
具体来说就是先按 DFS 访问图，然后再根据 Postvisit clock 排序从大到小就是我们需要求的值。
因为 DFS 总是一直走到最深处，即先找到 sink 为 0 的节点。
Strongly Connected Components
在无向图中有联通一说，在有向图中会更复杂点
定义
在有向图中，联通意味着集合里的点都能互相到达，画到一起就是下面这样子：
叫做 metagraph ，也是一个 DAG。
下面我们来描述如何计算一个 SCC（Strongly Connected Components）。
SCC 计算
简单算法
另一种思路是跟找 sink 节点一样，此时我们找一个聚合的 sink。
，但是怎么找到呢?
在无向图中，我们对 postOrder 进行排序，postOrder 小的就是 sink，在有向图中，我们有下面的理论：
因此有大的 postOrder 的是 source ，但是我们需要的是 sink，因此我们可以做如下操作：
下面我们开始给出具体的算法。
基本算法
上面做法就是不断通过 DFS 遍历，然后找到 postOrder 最大的顶点，从他开始找到所有能达到的点，然后删除，不断重复。
下面是一个改进算法，不用每次都 dfs：
总结
本文是对 Algorithms on Graphs 第 1-2 周 课程的一个记录，笔记更多的是给自己复习时快速查阅用。
你的鼓励是我继续写下去的动力，期待我们共同进步。
相关推荐
- 墨尔本一华裔男子与亚裔男子分别失踪数日 警方寻人
-
中新网5月15日电据澳洲新快网报道，据澳大利亚维州警察局网站消息，22岁的华裔男子邓跃(Yue‘Peter’Deng，音译)失踪已6天，维州警方于当地时间13日发布寻人通告，寻求公众协助寻找邓跃。华...
- 网络交友须谨慎!美国犹他州一男子因涉嫌杀害女网友被捕
-
伊森·洪克斯克（图源网络，侵删）据美国广播公司（ABC）25日报道，美国犹他州一名男子于24日因涉嫌谋杀被捕。警方表示，这名男子主动告知警局，称其杀害了一名在网络交友软件上认识的25岁女子。雷顿警...
- 一课译词:来龙去脉（来龙去脉 的意思解释）
-
Mountainranges[Photo/SIPA]“来龙去脉”，汉语成语，本指山脉的走势和去向，现比喻一件事的前因后果（causeandeffectofanevent），可以翻译为“i...
- 高考重要考点:range（range高考用法）
-
range可以用作动词，也可以用作名词，含义特别多，在阅读理解中出现的频率很高，还经常作为完形填空的选项，而且在作文中使用是非常好的高级词汇。...
- C++20 Ranges:现代范围操作（现代c++白皮书）
-
1.引言：C++20Ranges库简介C++20引入的Ranges库是C++标准库的重要更新，旨在提供更现代化、表达力更强的方式来处理数据序列（范围，range）。Ranges库基于...
- 学习VBA，报表做到飞 第二章 数组 2.4 Filter函数
-
第二章数组2.4Filter函数Filter函数功能与autofilter函数类似，它对一个一维数组进行筛选，返回一个从0开始的数组。...
- VBA学习笔记:数组:数组相关函数—Split，Join
-
Split拆分字符串函数，语法Split（expression，字符，Limit，compare），第1参数为必写，后面3个参数都是可选项。Expression为需要拆分的数据，“字符”就是以哪个字...
- VBA如何自定义序列，学会这些方法，让你工作更轻松
-
No.1在Excel中，自定义序列是一种快速填表机制，如何有效地利用这个方法，可以大大增加工作效率。通常在操作工作表的时候，可能会输入一些很有序的序列，如果一一录入就显得十分笨拙。Excel给出了一种...
- Excel VBA入门教程1.3 数组基础（vba数组详解）
-
1.3数组使用数组和对象时，也要声明，这里说下数组的声明：'确定范围的数组，可以存储b-a+1个数，a、b为整数Dim数组名称(aTob)As数据类型Dimarr...
- 远程网络调试工具百宝箱-MobaXterm
-
MobaXterm是一个功能强大的远程网络工具百宝箱，它将所有重要的远程网络工具（SSH、Telnet、X11、RDP、VNC、FTP、MOSH、Serial等）和Unix命令（bash、ls、cat...
- AREX:携程新一代自动化回归测试工具的设计与实现
-
一、背景随着携程机票BU业务规模的不断提高，业务系统日趋复杂，各种问题和挑战也随之而来。对于研发测试团队，面临着各种效能困境，包括业务复杂度高、数据构造工作量大、回归测试全量回归、沟通成本高、测试用例...
- Windows、Android、IOS、Web自动化工具选择策略
-
Windows平台中应用UI自动化测试解决方案AutoIT是开源工具，该工具识别windows的标准控件效果不错，但是当它遇到应用中非标准控件定义的UI元素时往往就无能为力了，这个时候选择silkte...
- python自动化工具:pywinauto（python快速上手 自动化）
-
简介Pywinauto是完全由Python构建的一个模块，可以用于自动化Windows上的GUI应用程序。同时，它支持鼠标、键盘操作，在元素控件树较复杂的界面，可以辅助我们完成自动化操作。我在...
- 时下最火的 Airtest 如何测试手机 APP?
-
引言Airtest是网易出品的一款基于图像识别的自动化测试工具，主要应用在手机APP和游戏的测试。一旦使用了这个工具进行APP的自动化，你就会发现自动化测试原来是如此简单！！连接手机要进行...
- 【推荐】7个最强Appium替代工具，移动App自动化测试必备!
-
在移动应用开发日益火爆的今天，自动化测试成为了确保应用质量和用户体验的关键环节。Appium作为一款广泛应用的移动应用自动化测试工具，为测试人员所熟知。然而，在不同的测试场景和需求下，还有许多其他优...
欢迎 你 发表评论:
- 一周热门
- 最近发表
- 标签列表
-
- mybatis plus (70)
- scheduledtask (71)
- css滚动条 (60)
- java学生成绩管理系统 (59)
- 结构体数组 (69)
- databasemetadata (64)
- javastatic (68)
- jsp实用教程 (53)
- fontawesome (57)
- widget开发 (57)
- vb net教程 (62)
- hibernate 教程 (63)
- case语句 (57)
- svn连接 (74)
- directoryindex (69)
- session timeout (58)
- textbox换行 (67)
- extension_dir (64)
- linearlayout (58)
- vba高级教程 (75)
- iframe用法 (58)
- sqlparameter (59)
- trim函数 (59)
- flex布局 (63)
- contextloaderlistener (56)