图论初步.docx
版权申诉
93 浏览量
2023-03-13
20:58:04
上传
评论
收藏 438KB DOCX 举报
图论初步
本章知识点：
1）图论中涉及的几个概念
2）图的存储方法
3）图的深度遍历和广度遍历
4）图论中经典算法（Prim 算法和 Kruskal 算法求最小生成树；Dijkstra 算法、SPFA 算法和 Floyed 算法求
最短路径；拓扑排序算法；关键路径）
图是一种数据结构，方便存取我们所要处理的数据。图中有二个重要的组成部分：点和边。
图论是解决处理图这种数据结构的算法，以使我们建立了图这种模型后能够高效方便的出结果（在信
息学竞赛范围内讨论）。在图论中，有很多经典的算法，比如求最短路径、最小生成树等。我们这讲的重
点就是掌握图的基本概念和常用图论算法。
一．图中的几个概念
1.图的定义
简单讲，一个图是由一些点和这些点之间的连线组成的。严格意义讲，图是一种数据结构，定义为：
graph=（V，E），V 是点（称为“顶点”）的非空有限集合，E 是线（称为“边”）的集合，边一般用（v ，
x
v ）表示，其中 v ，v 属于 V。
y
x
y
图（A）共有 4 个顶点、5 条边，表示为：V={v ，v ，v ，v }，E={（v ，v ），（v ，v ），（v ，v ），（v ，
1
2
3
4
1
2
1
3
1
4
2
v ），（v ，v ）}
4
3
2
2.图的分类
图分为无向图和有向图两大类：如果边是没有方向的，称此图为“无向图”，如图（A）和图（C），用
一对圆括号表示无向边，如图（A）中的边（v ，v ），显然（v ，v ）和（v ，v ）是两条等价的边，所以
y
1
2
x
y
x
在上面 E 的集合中没有再出现边（v ，v ）。
2
1
如果边是有方向（带箭头）的，则称此图为“有向图”，如图（B），用一对尖括号表示有向边，如图
（B）中的边<v ，v >。把边<V ，V >中 V 称为起点，V 称为终点。显然此时边<v ，v >与边<v ，v >是不同
x
1
2
x
y
x
y
的两条边。有向图中的边又称为弧，起点称为弧头，终点称为弧尾。
y
y
x
图（B）表示为：V={v ，v ，v }，E={<v ，v >，<v ，v >，<v ，v >，<v ，v >}
2
1
2
3
1
2
1
3
2
如果两个顶点 U、V 之间有一条边相连，则称 U、V 这两个顶点是关联的。
3
3
3.图的权
一个图中的两顶点间不仅是关联的，而且在边上还标明了数量关系，如图（C），这种数量关系可能是
距离、费用、时间、电阻等等，这些数值称为相应边的权。边上带有权的图称为带权图，也称为网（络）。
4.图的阶
1/20
剩余19页未读，继续阅读
资源评论
คิดถึง643
- 粉丝: 3917
- 资源: 1万+
最新资源
- 基于JavaScript和CSS的随寻订购网页设计源码 - web-order
- 基于MATLAB的声纹识别系统设计源码 - VoiceprintRecognition
- 基于Java的微服务插件集合设计源码 - wsy-plugins
- 基于Vue和微信小程序的监理日志系统设计源码 - supervisionLog
- 基于Java和LCN分布式事务框架的设计源码 - tx-lcn
- 基于Java和JavaScript的茶叶评级管理系统设计源码 - tea
- IMG_5680.JPG
- IMG_0437.jpg
- 基于Java的JAVA项目分析工具设计源码 - JAVAProjectAnalysis
- top888.json
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
