资源描述：
《数据结构第05章_图》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、制定教学计划时，需考虑各门课的开设顺序。有些课需要先导课，有些课不需要，有些又是其他课的先导课。如，计算机专业课程的开设情况如下表所示：课程编号课程名称先导课程编号C1程序设计基础无C2离散数学C1C3数据结构C1，C2C4汇编语言C1C5算法分析与设计C3，C4C6计算机组成原理C11C7编译原理C5，C3C8操作系统C3，C6C9高等数学无C10线性代数C9C11普通物理C9C12数值分析C9，C10，C1课程先后关系如图：c1c9c4c2c12c10c11c5c3c6c7c8c1c9c4c2c12c10c5c3c6c7c8c11第7章图7.1图的定义和
2、术语7.2图的存储结构7.3图的遍历7.4图的连通性问题7.5有向无环图及其应用7.6最短路径7.1图的定义和术语1.基本术语(1)顶点图中的数据元素通常称为顶点。V是顶点的有穷非空集合；VR是两个顶点之间的关系的集合。(2)有向图若称∈VR表示从v到w的一条弧，且称v为弧尾或初始点，称w为弧头或终端结点，则该图称为有向图。(3)无向图若∈VR，必有∈VR，即VR是对称的，则以无序对（v,w)代替这两个有序对，表示v和w之间的一条边，则该图称为无向图。(4)权/网有时图的边或弧具有与它相关的数，这些数称为权值（通常表示顶点间的距
3、离或耗费），则带权值的图称为网。(5)子图假设有两个图G=（V，{VR}）和G’=（V’，{VR’}），若V’是V的子集，且VR’是VR的子集，则称G’为G的子图。G1的子图G2的子图(6)完全图假设用n表示图中顶点的数目，用e表示边或弧的数目。忽略自身弧/边，即若﹤vi,vj﹥∈VR，则vi≠vj。对于无向图，有(n(n-1))/2条边的无向图称为完全图。对于有向图，有n(n-1)条弧的有向图称为有向完全图。(7)稀疏图/稠密图边或弧很少（如e＜nlogn）的图称稀疏图，反之称稠密图。(8)邻接点对于无向图G=(V,{E})，若边(v,v’)∈E，则称顶点
4、v和v’互为邻接点，即v和v’相邻接。或称边（v,v’）依附于顶点v和v’，或称（v,v’）和顶点v和v’相关联。对于有向图G=(V，{E})，若弧∈E，则称顶点v邻接到顶点v’，或称顶点v’邻接自顶点v，或弧和顶点v，v’相关联。(a)(b)顶点的入度/出度以顶点v为头的弧的数目称v的入度，记为ID(v)；以顶点v为尾的弧的数目称v的出度，记为OD(v)。顶点v的度TD（v）=ID（v）＋OD（v）(9)顶点v的度(Degree)是和v相关联的边的数目，记为TD（v）。(a)(b)(10)路径(Path)无向图G=(V,{E})中，
5、从顶点v到v’的路径是顶点序列(v=vi0,vi1,…,vim=v’)，其中(vij-1,vij)∈E，1≤j≤m。若G是有向图，则路径也是有向的，顶点序列应满足：∈E，1≤j≤m。路径的长度是路径上的边或弧的数目。(11)回路/环/简单路径第一个顶点和最后一个顶点相同的路径称为回路/环。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。(12)连通图/连通分量在无向图G中，如果从顶点V到顶点V’有路径，则称V和V’是连通的。若图中任意两个顶点vi、vj∈V，vi和
6、vj都是连通的，则称G是连通图。无向图中的极大连通子图称之为连通分量。左图：连通图下图：非连通图，但有三个连通分量(13)强连通图/强连通分量在有向图G中，若对于每一对vi、vj∈V，vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。有向图中的极大强连通子图称作有向图的强连通分量。非强连通图④①②③④①②③两个强连通分量一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边。如果在一棵生成树上添加一条边，必定构成一个环，因为这条边使得它依附的那两个顶点之间有了第二条路径。(14)生成树如果一个有向图恰有一
7、个顶点的入度为0，其余顶点的入度均为1，则是一棵有向树。一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。(15)生成森林2.图的抽象类型定义ADTGraph{数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R={VR}VR={
8、v,w∈V且P(v,w)，表示从v到w的弧，谓词P(v,w)定义了弧的意义或信息}基本操作P：}ADTGraph基本操作CreateGraph(&G,V,VR);//按V和VR的定义构造图GDestroyGraph(&G);//销毁图
9、GLocateVex(G,u);//若G中存在顶点u
