- 1、本文档共37页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
[工学]第7章 图1
7.1 图的定义和基本术语 7.2 图的存储结构 7.2.1 数组表示法 7.2.2 邻接表 7.3 图的遍历 7.3.1 深度优先有哪些信誉好的足球投注网站 7.3.2 广度优先有哪些信誉好的足球投注网站 7.4 图的连通性 7.4.1 无向图的连通分量和生成树 7.4.3 最小生成树 7.5 有向无环图及应用 7.6 最短路径 生成树—— 一个含 n 个顶点的连通图的生成树包含图中 n 个顶点和足以构成一棵树的 n-1 条边。 * Data Structure 第七章 图 7.1 图的定义和术语 1 图的定义 图(Graph)——图G是由两个集合V(G)和E(G)组成的。 其中: V(G)是顶点的非空有限集; E(G)是边的有限集合,边是顶点的无序对或有序对 1 5 7 3 2 4 G1 6 E(G1)={(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7)} 无向图——无向图G是由两个集合V(G)和E(G)组成的 其中:V(G)是顶点的非空有限集; E(G)是边的有限集合,边是顶点的无序对. 记为(v,w)或(w,v),并且(v,w)=(w,v) V(G1)={1,2,3,4,5,6,7} 记为G=(V,E) 例 2 4 5 1 3 6 G2 E(G1)={1,2, 2,1, 2,3, 2,4, 3,5, 5,6, 6,3} 有向图——有向图G是由两个集合V(G)和E(G)组成的 其中:V(G)是顶点的非空有限集; E(G)是有向边(弧)的有限集合,弧是顶点的有序对. 记为v,w,v,w是顶点,v为弧尾,w为弧头 V(G1)={1,2,3,4,5,6} 有向完备图——n个顶点的有向图最大边数是n(n-1) 无向完备图——n个顶点的无向图最大边数是n(n-1)/2 2 1 3 2 1 3 有向完备图 无向完备图 稀疏图——边(en)较少的图。 稠密图——边接近完全图的图 权——与图的边或弧相关的数 网——带权的图 1 5 7 3 2 4 G2 5 3 8 6 3 3 5 6 2 4 5 1 3 6 图 子图——图G(V,E)和图G’(V’,E’),满足:V’?V;E’?E; 则称G’为G的子图 子图 例 2 4 5 1 3 6 G1 例 1 5 7 3 2 4 G2 6 顶点的度 无向图中,顶点的度为与每个顶点相连的边数 有向图中,顶点的度分成入度与出度 出度:以该顶点为尾的弧的数目 入度:以该顶点为头的弧的数目 顶点2的度: 顶点2入度: 出度: 顶点4入度: 出度: 顶点5的度: 3 4 1 3 1 0 路径——从顶点v到v’路径是顶点的序列V={Vi0,Vi1,……Vin}。 满足(Vij-1,Vij)?E 或 Vij-1,Vij?E,(1j?n) 简单路径——序列中顶点不重复出现的路径 简单回路——除了第一个顶点和最后一个顶点外,其余顶点不重复出现的回路 路径长度——沿路径边的数目或沿路径各边权值之和 回路(环)——第一个顶点和最后一个顶点相同的路径 例 1 5 7 3 2 4 G2 6 路径:1,2,5,7,6,5,2,3 路径长度:7 简单路径:1,2,5,7,6 回路:1,2,5,7,6,5,2,1 简单回路:1,2,3,1 连通——从顶点V到顶点W有一条路径,则说V和W是连通的 连通图——无向图中任意两个顶点都是连通的 强连通分量——有向图中的极大强连通子图 连通分量——无向图中,非连通图的每一个连通部分。 连通分量是无向图中的极大连通子图 强连通图——有向图中,如果对每一对Vi,Vj?V, Vi?Vj, 从Vi到Vj 和从Vj到 Vi都存在路径 例 2 4 5 1 3 6 连通图 3 5 6 例 强连通图 例 2 4 5 1 3 6 强连通分量 是该图中的一个极小连通子图 添加一条边,必定构成一个环 一个含 n 个顶点的生成树有且仅有 n-1 条边 小于n-1条边,非连通图 例 G1 2 4 1 3 例 1 5 3 2 4 G2 V1 V2 ^ ^ V4 ^ V3 ^ ^ V1 V2 V4 ^ V5 ^ V3 7.2 图的存储结构 多重链表 7.2.1 数组表示法 用两个数组分别存储数据元素的信息和数据元素之间的关系的信息 邻接矩阵法 顶点 边或弧 #define INFINITY INT_MAX //最大值∞#define MAX_VERTEX_NUM 20 //最大顶点
您可能关注的文档
- [工学]第3章80C51单片微机的指令系统.ppt
- [工学]第3章-车床.ppt
- [工学]第3章1线性方程组的迭代解法.pdf
- [工学]第3章80x86处理器3.ppt
- [工学]第3章 长度测量技术基础.ppt
- [工学]第3章C28xDSP的CPU与指令系统.pdf
- [工学]第3章MCS-51的指令系统NEW.pdf
- [工学]第3章 汽车分类与性能.ppt
- [工学]第3章_单片机指令系统.ppt
- [工学]第3章_VHDL设计进阶.ppt
- 浙江省临海市白云高级中学2025届高三历史3月月考试题.doc
- 云南拾谷县第一中学2024_2025学年高二物理上学期10月月考试题.doc
- 2025版高考生物总复习第13讲基因的分离定律教案苏教版.doc
- 湖北省黄石实验高中2024_2025学年高一历史下学期期末考试模拟卷.doc
- 通史版2025版高考历史大一轮复习专题七近代化的曲折发展__中日甲午战争至五四运动前4第4讲从维新思想到新文化运动课后达标检测含解析新人教版.doc
- 2024年高考数学考试大纲解读专题04导数及其应用含解析文.doc
- 河南省许汝平九校联盟2024_2025学年高一语文上学期期末考试试题扫描版无答案.doc
- 江西省吉安市吉水县第二中学2024_2025学年高一历史上学期第二次月考试题.doc
- 北京市平谷区2025届高三政治一模考试试题含解析.doc
- 2025届中考物理第四讲物态变化专项复习测试无答案新人教版.docx
文档评论(0)