图论--无向无权图

图论

图的基本概念

图是由很多结点和边组成的

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

点的表示:v,点的集合:V

边的表示:e,边的集合:E

图:G = (V,E)

无向图和有向图

无向图:边没有方向

有向图:边有方向

无权图和有权图

无权图:所有边的权重都是一样的,都等于1

有权图:边有权重,权重的大小各不相同

权重的物理意义:可以是距离、长度、宽度等

不存在的边可以是权重无穷大、权重为0的边

图的数据结构

无向无权图

邻接表

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

邻接矩阵

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

一条边对应邻接矩阵的两个元素

邻接矩阵是对称的

有向无权图

邻接表

邻接矩阵

行为To,列为From

一条边对应邻接矩阵的一个元素

邻接矩阵通常是对称的

无向有权图

邻接矩阵

一条边对应邻接矩阵的两个元素

邻接矩阵是对称的

有向有权图

邻接矩阵

一条边对应邻接矩阵的一个元素

邻接矩阵通常是非对称的

最短路问题

概念

路径:可以表示为结点的序列或边的序列

简单路径的概念:路径上没有重复结点

路径不存在:路径的长度为正无穷

无权图路径的长度 = 路径边数

有权图路径的长度 = 路径边权重总和

最短路问题:

输入图和起点s,输出s到其它所有结点的最短路径

记录到每个结点的最短路径、前一个结点

算法:寻找无权图中的最短路

以有向图为例,同样适用于无向图

空队列、表(bool是否访问过该节点, int路径长度, path前一个结点)

算法:寻找有权图中的最短路

最近更新

  1. 使用爬虫爬取豆瓣电影Top250(方法二)

    2024-06-10 14:40:01       0 阅读
  2. dos格式文档转unix格式

    2024-06-10 14:40:01       0 阅读
  3. ubuntu版本升级命令记录

    2024-06-10 14:40:01       0 阅读
  4. Android_Android Studio 常用快捷键 for mac

    2024-06-10 14:40:01       0 阅读
  5. PyTorch tutorials:快速学会使用PyTorch

    2024-06-10 14:40:01       0 阅读
  6. Kotlin 数据类(Data Class)

    2024-06-10 14:40:01       0 阅读
  7. 乘积最大3

    2024-06-10 14:40:01       0 阅读
  8. MySQL中的隐式转换(Implicit Conversion)

    2024-06-10 14:40:01       0 阅读

热门阅读

  1. 为何数据仓库需要“分层次”?

    2024-06-10 14:40:01       7 阅读
  2. tensorRT 自定义算子plugin的实现

    2024-06-10 14:40:01       4 阅读
  3. 使用git stash暂存改动,并备注改动内容

    2024-06-10 14:40:01       7 阅读
  4. Vue3学习

    2024-06-10 14:40:01       3 阅读
  5. 使用c语言实字符串倒置及逆波兰数(栈)

    2024-06-10 14:40:01       3 阅读
  6. web前端报名点:深入探索与报名流程指南

    2024-06-10 14:40:01       5 阅读
  7. 深拷贝&浅拷贝解析,从原理理解深拷贝

    2024-06-10 14:40:01       4 阅读
  8. 不要使用业务键作为数据库主键

    2024-06-10 14:40:01       6 阅读
  9. 爬山算法的详细介绍

    2024-06-10 14:40:01       5 阅读