图的定义和基本术语精.docx

目录

TOC\o"1-3"\h\z第6章图 PAGEREF_Toc7251843\h2
6.1图的定义和基本术语 PAGEREF_Toc7251844\h2
6.2图的存储和创建 PAGEREF_Toc7251845\h3
6.2.1图的存储表示 PAGEREF_Toc7251846\h3
6.2.2图的创建 PAGEREF_Toc7251847\h6
6.3图的遍历 PAGEREF_Toc7251848\h6
6.3.1深度优先搜索 PAGEREF_Toc7251849\h6
6.3.2广度优先搜索 PAGEREF_Toc7251850\h7
6.4遍历算法的应用 PAGEREF_Toc7251851\h8
6.4.1应用问题概述 PAGEREF_Toc7251852\h8
6.4.2求一条包含图中所有顶点的简单路径 PAGEREF_Toc7251853\h9
6.4.3求距v0最短路径长度最长的一个顶点 PAGEREF_Toc7251854\h10
6.5图的连通性问题 PAGEREF_Toc7251855\h11
6.5.1无向图的连通分量和生成树 PAGEREF_Toc7251856\h11
6.5.2最小生成树 PAGEREF_Toc7251857\h13
6.6有向无环图及其应用 PAGEREF_Toc7251858\h13

图
图的定义和基本术语
图的特征
任意两个数据元素之间都可能相关。结点之间的关系是多对多的。
G=(V,{E})
基本术语
结点： 顶点
结点间的关系：无向图：边(v,w)，v与w互为邻接点，边(v,w)依附于顶点v,w，边(v,w)和顶点v,w相关联v的度：和v相关联的边的数目。有向图：弧<v,w>，v弧尾，w弧头，顶点v邻接到顶点w，顶点w邻接自顶点v，弧<v,w>和顶点v,w相关联。v的入度：以v为头的弧的数目；v的出度：以v为尾的弧的数目；v的度：v的入度与出度之和。路径、回路(环)、简单路径、简单回路(简单环)连通性：若从顶点v到顶点v’有路径，则称v和v’是连通的
图的规模：顶点数n、边(弧)数e、顶点的度(有向图：入度/出度)
子图：G’=(V’,{E’}),G=(V,{E})，若V’V且E’E，则称G’是G的子图。
图的分类：
1）关系的方向性（无向/有向）、关系上是否有附加的数——权(图/网)有向图、无向图、有向网、无向网
2）边(弧)数：完全图(边数=n(n-1)/2的无向图)、有向完全图(弧数=n(n-1)的有向图)稀疏图(e<nlogn)、稠密图(e>nlogn)
3）连通性：无向图：连通图(任意两顶点都是连通的)、连通分量(极大连通子图)、生成树(极小连通子图)、生成森林有向图：强/弱连通图、强连通分量、生成树(极小连通子图)、生成森林

抽象数据类型定义
ADTGraph{
数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。
数据关系R：R={VR}VR={<v,w>|v,wV且P(v,w)，<v,w>表示从v到w的弧，谓词P(v,w)定义了弧<v,w>的意义或信息}
基本操作：
CreateGraph(&G,V,VR)
初始条件：V是图的顶点集，VR是图中弧的集合
操作结果：按V和VR的定义构造图G
DestroyGraph(&G)
初始条件：图G存在
操作结果：销毁图G
LocateVex(G,u)
初始条件：图G已存在，u和G中顶点有相同特征
操作结果：若G中存在顶点u，则返回该顶点在图中位置，否则返回其它信息
GetVex(G,v)
初始条件：图G存在，v是G中某个顶点
操作结果：返回v的值
PutVex(&G,v,value)
初始条件：图G存在，v是G中某个顶点
操作结果：对v赋值value
FirstAdjVex(G,v)
初始条件：图G存在，v是G中某个顶点
操作结果：返回v的第一个邻接顶点。若顶点在G中没有邻接顶点，则返回“空”
NextAdjVex(G,v,w)
初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点
操作结果：返回v的(相对于w的)下一个邻接顶点。若w是v的最后一个邻接点，则返回“空”
InsertVex(&G,v)
初始条件：图G存在，v和G中顶点有相同特征
操作结果：在图中增添新顶点v
DeleteVex(&G,v)
初始条件：图G存在，v是G中某个顶点
操作结果：删除G中顶点v及其相关的弧
InsertArc(&G,v,w)
初始条件：图G存在，v和w是G中两个顶点
操作结果：在图G中增添弧<v,w>，若G是无向的，则还应增添对称弧<w,v>
DeleteArc(&G,v,w)
初始条件：图G存在，v和w