图基本算法(一) 图的基本算法实现
yuyutoo 2024-10-12 00:58 5 浏览 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 周 课程的一个记录，笔记更多的是给自己复习时快速查阅用。
你的鼓励是我继续写下去的动力，期待我们共同进步。
相关推荐
- 深度解读Spring框架的核心原理
-
深度解读Spring框架的核心原理在Java开发的世界里，提到Spring框架，就像提起一位久经沙场的老将，它几乎成了企业级应用开发的代名词。那么，这个被无数开发者膜拜的框架究竟有何独特之处？今天，我...
- 「Spring认证」Spring 框架概述
-
Spring是最流行的企业Java应用程序开发框架。全球数以百万计的开发人员使用SpringFramework来创建高性能、易于测试和可重用的代码。Spring框架是一个开源的Java...
- 学习Spring框架 这一篇就够了
-
1.spring概述1.1Spring是什么（理解）...
- Spring框架双核解析:IOC与AOP的本质与实战
-
#Spring核心#IOC容器#AOP编程#Java框架设计...
- Spring Boot与传统Spring框架的对比:探索Java开发的新境界
-
SpringBoot与传统Spring框架的对比：探索Java开发的新境界在Java生态系统中，Spring框架无疑是一个里程碑式的存在。从最初的简单依赖注入容器，到如今覆盖企业级开发方方面面的庞大...
- Spring MVC框架源码深度剖析:从入门到精通
-
SpringMVC框架源码深度剖析：从入门到精通SpringMVC框架简介SpringMVC作为Spring框架的一部分，为构建Web应用程序提供了强大且灵活的支持。它遵循MVC（Model-V...
- Spring框架入门
-
一.spring是什么？Spring是分层...
- 程序员必知必会技能之Spring框架基础——面向切面编程!
-
面向切面编程AOP（AspectOrientedProgramming）与OOP（ObjectOrientedProgramming，面向对象编程）相辅相成。AOP提供了与OOP不同的抽象软件结...
- Spring Security安全框架深度解读:为你的应用穿上“钢铁铠甲”
-
SpringSecurity安全框架深度解读：为你的应用穿上“钢铁铠甲”在现代网络世界里，保护我们的应用程序免受各种威胁攻击至关重要。而在这个过程中，SpringSecurity框架无疑是我们最可...
- Spring框架的设计哲学与实现:打造轻量级的企业级Java应用
-
Spring框架的设计哲学与实现：打造轻量级的企业级Java应用Spring框架自2003年诞生以来，已成为企业级Java应用开发的代名词。它不仅仅是一个框架，更是一种设计理念和哲学的体现。本文将带你...
- Spring框架深度解析:从核心原理到底层实现的全方位避坑指南
-
一、Spring框架核心概念解析1.控制反转（IoC）与依赖注入（DI）Spring的核心思想是通过IoC容器管理对象的生命周期和依赖关系。传统开发中，对象通过new主动创建依赖对象，导致高耦合；而S...
- Java框架 —— Spring简介
-
简介一般来说，Spring指的是SpringFramework，它提供了很多功能，例如：控制反转（IOC）、依赖注入...
- Spring 框架概述，模块划分
-
Spring框架以控制反转（InversionofControl，IoC）和面向切面编程（Aspect-OrientedProgramming，AOP）为核心，旨在简化企业级应用开发，使开发者...
- spring框架怎么实现依赖注入?
-
依赖注入的作用就是在使用Spring框架创建对象时，动态的将其所依赖的对象注入到Bean组件中，其实现方式通常有两种，一种是属性setter方法注入，另一种是构造方法注入。具体介绍如下：●属性set...
- Spring框架详解
-
Spring是一种开放源码框架，旨在解决企业应用程序开发的复杂性。一个主要优点就是它的分层体系结构，层次结构让你可以选择要用的组件，同时也为J2EE应用程序开发提供了集成框架。 Spring特征...
欢迎 你 发表评论:
- 一周热门
-
-
前端面试:iframe 的优缺点? iframe有那些缺点
-
带斜线的表头制作好了，如何填充内容?这几种方法你更喜欢哪个?
-
漫学笔记之PHP.ini常用的配置信息
-
推荐7个模板代码和其他游戏源码下载的网址
-
其实模版网站在开发工作中很重要，推荐几个参考站给大家
-
[干货] JAVA - JVM - 2 内存两分 [干货]+java+-+jvm+-+2+内存两分吗
-
正在学习使用python搭建自动化测试框架?这个系统包你可能会用到
-
织梦(Dedecms)建站教程 织梦建站详细步骤
-
【开源分享】2024PHP在线客服系统源码(搭建教程+终身使用)
-
2024PHP在线客服系统源码+完全开源 带详细搭建教程
-
- 最近发表
- 标签列表
-
- 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)