西交《数据结构》faq（七）

西交《数据结构》FAQ（七）
第七章 图
1、图的相关术语介绍。
1）完全图(稀疏图／刷密图)
稠密图：接近完全图，称为稠密图；
稀疏图：称边数很少的图为稀疏图。
2）顶点、边、弧、弧头、弧尾
图中数据元素VI称为项点(vertex l；
P(vi，vj)表示在项点vi和顶点vj之间有一条直接连线。
如果是在无向图中，则称这条连线为边；
如果是在有向图中，一般称这条连线为弧。
边用顶点的无序偶对(vi，vj)来表示，称顶点vi和顶点vj互为邻接点，边(vi，vj)依附于项点vi与顶点vj；
弧用顶点的有序偶对(vi，vj)来表示，有序偶对的第1个结点vi被称为始点（或弧尾），在图中就是不带箭头的一端；有序偶对的第2个结点Vj称为终点或弧头），在图中鹉是带箭头的一端。
3）顶点的度、入度、出度：
顶点的度(degree)是指依附于某项点V的边数，通常记为TD (v)。
在有向图中，要区别顶点的入度与出度的概念。
项点v的入度是指以项点为终点的弧的数目，记为lD(v)；
顶点v出度是指以项点v为始点的弧的数目，记为OD(v)。
4）边的权、网图。与边有关的数据信息称为权(weight)。
在实际应用中，权值可以有某种含义。比如，在一个反映城市交通线路的图中，边上的数值可以表示该条线路的长度或者等级；
对于一个电子线路图，边上的权值可以表示两个端点之间的电阻、电流或电压值；对于反映工程进度的图而言，边上的权值可以表示从前一个工程到后一个工程所需要的时间等等。边上带权的图称为网图或网络( network)。
如果边是有方向的带权图，则就是一个有向网图。
5）路径、路径长度。顶点vp到顶点vq之间的路径(path)是指顶点序列vp，vi1，vi2，…，vim，vq。其中，(vp，vi1)，(vi1，vi2)，…，(vim，vq)分别为图中的边。
路径上边的数目称为路径长度。
所示的无向图中，vl-v4-v3-v5与vl-v2-v5是从顶点vl到顶点v5的两条路径，路径长度分别为3和2。


6）回路、简单路径、简单回路。
称vi的路径为回路或者环( cycle)。序列中顶点不重复出现的路径称为简单路径。
除第一个顶点与最后一个顶点之外，其他顶点不重复出现的回路称为简单回路，或者简单环。
7）子图
对于图G= (V，E)，G’=(V’，E,)，若存在V’是V的子集，E’是E的子集，则称图G’是G的一个子图。
2、图的ADT定义
G=（V,E）~（点集，边集_关系集）




ADT Grahp{
数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。
数据关系R：R={VR)
VR={<V，W>｜v,w∈V且P(v，w)，<v，w>表示从v到w的弧。
谓词P(V，W)定义了弧<V，W>的意义或信息}
基本操作13个P156
3、图的数组表示法
用两个数组分别存放数据和关系。
有关系则有边信息，无关系则无边信息。
G．arcs、aij=1/0(Vi，Vj)∈E  图的最简表现形式，使用亦由数组下标方便实现。
形式描述：

4、邻接矩阵存储的定义及特点？
所谓邻接矩阵(Adjacency Matrix)的存储结构，就是用一维数组存储图中顶点的信息，用矩阵表示图中各顶点之间的邻接关系。假设图G=(V，E)有n个确定的顶点，即V={Vo，V1，…Vn-1}，则表示G中各顶点相邻关系为一个n×n的矩阵，矩阵的元素为：
A[i][j]=

若G是网图，则邻接矩阵可定义为：
A[i][j]=

其中，Wij表示边(ViVj)或<ViVj>上的权值：∞表示一个计算机允许的、大于所有边上权值的数。
邻接矩阵存储的特点
从图的邻接矩阵存储方法容易看出这种表示具有以下特点：
①无向图的邻接矩阵一定是一个对称矩阵。因此，在具体存放邻接矩阵时只需存放上(或下)三角矩阵的元素即可。
②对于无向图，邻接矩阵的第i行(或第i列)非零元素(或非∞元素)的个数正好是第i个顶点的度TD(Vi)。
③对于有向图，邻接矩阵的第i行(或第i列)非零元素(或非∞元素)的个数正好是第i个顶点的出度OD(Vi)(或入度ID(Vi))。
④用邻接矩阵方法存储图，很容易确定图中任意两个顶点之问是否有边相连；但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时问代价很大。这是用邻接矩阵存储图的局限性。本内容由易百网整理发布
网址 www.openhelp100.com
QQ 515224986