7.2 图的几种分类
分类 几种 7.2
2023-09-11 14:20:29 时间
首先可以按有向无向来进行分类。可以分为无向图和有向图。需要注意的是,无向图的计算式实现实际上是内存里存储了两个方向的有向图。所以可以把无向图看成双向的有向图。有向图的例子很多,流程图或者更确切的例子是工作流,就是有向图。面向对象程序的内存结构也是一个有向图。
比如以下是无向图的例子:
有向图的例子,在多线程开发中比较多,比如JAVA得fork/join就是有向无环图。下面是3-puzzle游戏的状态转换图:
当然,这不是一个很好的例子。因为反方向运动也可以变成无向图。
有向无向都是边的特点。如果边再加上权重属性,就构成了加权图。权重不是边的长度,初学图算法可以用边的长度来辅助理解。但是有时候,权重也会是负数,这个时候使用几何概念长度来理解就不对了:
在求最短路径的应用中,比如说地铁图,加权图的最短路径是求最短距离,无权图的最短路径是最少换乘。最后介绍下有向无环图,简称为DAG。为什么单独提出这个呢?因为在多线程编程、工作流算法中,用的就是有向无环图。无环是为了避免进入无限循环。以下是一个多线程数组求和的有向无环图的例子:
好了,图按边还有很多分类方法,但是常见且实用的就这么几种。
相关文章
- Google Earth Engine——USGS GAP Hawaii 2001夏威夷的详细植被和土地覆盖分类
- fastText实现文本分类
- 【堡垒机】堡垒机怎么分类?哪种更好用?
- 4.3.6 无分类编址CIDR(构成超网)
- 机器学习笔记之线性分类——线性回归基本性质介绍与线性分类
- OC的类别(分类)和拓展
- 《Linux C编程从入门到精通》一第1章 Linux基础1.1 Linux的起源、发展和分类
- H3C IPv6地址分类
- 如何在 Python 中创建用于分类的模拟数据
- Excel-返回列表或数据库中的分类汇总(汇总可以实现要还是不要统计隐藏行功能) subtotal()
- 机器学习-分类简单介绍
- (3.11)mysql基础深入——mysql文件分类与配置文件管理
- BW中DSO的分类及应用
- 原来恶意软件在各个国家的投放都是有分类的……