图基本算法(一) 图的基本算法实现
yuyutoo 2024-10-12 00:58 1 浏览 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 周 课程的一个记录，笔记更多的是给自己复习时快速查阅用。
你的鼓励是我继续写下去的动力，期待我们共同进步。
相关推荐
- jQuery VS AngularJS 你更钟爱哪个?
-
在这一次的Web开发教程中，我会尽力解答有关于jQuery和AngularJS的两个非常常见的问题，即jQuery和AngularJS之间的区别是什么？也就是说jQueryVSAngularJS？...
- Jquery实时校验，指定长度的「负小数」，小数位未满末尾补0
-
在可以输入【负小数】的输入框获取到焦点时，移除千位分隔符，在输入数据时，实时校验输入内容是否正确，失去焦点后，添加千位分隔符格式化数字。同时小数位未满时末尾补0。HTML代码...
- 如何在pbootCMS前台调用自定义表单?pbootCMS自定义调用代码示例
-
要在pbootCMS前台调用自定义表单，您需要在后台创建表单并为其添加字段，然后在前台模板文件中添加相关代码，如提交按钮和表单验证代码。您还可以自定义表单数据的存储位置、添加文件上传字段、日期选择器、...
- 编程技巧:Jquery实时验证，指定长度的「负小数」
-
为了保障【负小数】的正确性，做成了通过Jquery，在用户端，实时验证指定长度的【负小数】的方法。HTML代码<inputtype="text"class="forc...
- 一篇文章带你用jquery mobile设计颜色拾取器
-
【一、项目背景】现实生活中，我们经常会遇到配色的问题，这个时候去百度一下RGB表。而RGB表只提供相对于的颜色的RGB值而没有可以验证的模块。我们可以通过jquerymobile去设计颜色的拾取器...
- 编程技巧:Jquery实时验证，指定长度的「正小数」
-
为了保障【正小数】的正确性，做成了通过Jquery，在用户端，实时验证指定长度的【正小数】的方法。HTML做成方法<inputtype="text"class="fo...
- jquery.validate检查数组全部验证
-
问题：html中有多个name[]，每个参数都要进行验证是否为空，这个时候直接用required:true话，不能全部验证，只要这个数组中有一个有值就可以通过的。解决方法使用addmethod...
- Vue进阶(幺叁肆):npm查看包版本信息
-
第一种方式npmviewjqueryversions这种方式可以查看npm服务器上所有的...
- layui中使用lay-verify进行条件校验
-
一、layui的校验很简单，主要有以下步骤：1.在form表单内加上class="layui-form"2.在提交按钮上加上lay-submit3.在想要校验的标签，加上lay-...
- jQuery是什么?如何使用? jquery是什么功能组件
-
jQuery于2006年1月由JohnResig在BarCampNYC首次发布。它目前由TimmyWilson领导,并由一组开发人员维护。jQuery是一个JavaScript库，它简化了客户...
- django框架的表单form的理解和用法-9
-
表单呈现...
- jquery对上传文件的检测判断 jquery实现文件上传
-
总体思路：在前端使用jquery对上传文件做部分初步的判断，验证通过的文件利用ajaxFileUpload上传到服务器端，并将文件的存储路径保存到数据库。<asp:FileUploadI...
- Nodejs之MEAN栈开发(四)-- form验证及图片上传
-
这一节增加推荐图书的提交和删除功能，来学习node的form提交以及node的图片上传功能。开始之前需要源码同学可以先在git上fork：https://github.com/stoneniqiu/R...
- 大数据开发基础之JAVA jquery 大数据java实战
-
上一篇我们讲解了JAVAscript的基础知识、特点及基本语法以及组成及基本用途，本期就给大家带来了JAVAweb的第二个知识点jquery，大数据开发基础之JAVAjquery，这是本篇文章的主要...
- 推荐四个开源的jQuery可视化表单设计器
-
jquery开源在线表单拖拉设计器formBuilder(推荐)jQueryformBuilder是一个开源的WEB在线html表单设计器，开发人员可以通过拖拉实现一个可视化的表单。支持表单常用控件...
欢迎 你 发表评论:
- 一周热门
- 最近发表
- 标签列表
-
- 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)