图的定义和术语及存储结构.ppt

数据结构课程的内容：7.1基本术语7.2存储结构7.3图的遍历7.4图的连通性7.5图的应用7.1图的基本术语EB证明：从①可以直接推论出无向完全图的边数——因为无方向，两弧合并为一边，所以边数减半，总边数为n(n-1)/2。稀疏图：稠密图：A路径:设图G=(V,VR)中的一个顶点序列:v=vi,0,vi,1,…,vi,m=w中，(vi,j-1,vi,j)（或〈vi,j-1,vi,j〉）VR1≤j≤m,则称从顶点v到顶点w之间存在一条路径。路径长度：路径上边（或弧）的数目。连通图：无向图G中任意两个顶点之间都有路径相连通。生成树：CreatGraph(&G,V,VR)//按定义(V,VR)构造图对邻接点的操作插入和删除弧7.2图的存储结构①建立一个顶点表和一个邻接矩阵。分析1：无向图的邻接矩阵是对称的；分析2：顶点i的度＝第i行(列)中1的个数；特别：完全图的邻接矩阵中，对角元素为0，其余全1。例2：有向图的邻接矩阵如何表示？例3：有权图（即网络）的邻接矩阵如何表示？容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。typedefstructArcCell{//弧的定义VRTypeadj;//VRType是顶点关系类型。//对无权图,用1或0表示相邻否；对带权图，则为权值类型。InfoType*info;//该弧相关信息的指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];2.邻接表（链式）表示法例1：无向图的邻接表如何表示？例2：有向图的邻接表如何表示？例3：已知某网的邻接（出边）表，请画出该网络。分析1：对于n个顶点e条边的无向图，邻接表中除了n个头结点外，只有2e个表结点,空间效率为O(n+2e)。若是稀疏图(e<<n2)，则比邻接矩阵表示法O(n2)省空间。讨论：邻接表与邻接矩阵有什么异同之处？图的邻接表在机内如何表示？（参见教材P163）Typedefstruct{//图结构AdjListvertics;//应包含邻接表intvexnum,arcnum;//应包含顶点总数和弧总数intkind;//还应说明图的种类（用标志）}ALGraph;它是有向图的另一种链式存储结构。思路：将邻接矩阵用链表存储，是邻接表、逆邻接表的结合。(1)开设弧结点，设5个域（每段弧是一个数据元素）(2)开设顶点结点，设3个域（每个顶点也是一个数据元素）data:顶点信息firstin:以顶点为弧头的第一条弧结点firstout:以顶点为弧尾的第一条弧结点A这是无向图的另一种链式存储结构，当对边操作时建议采用此种结构存储。（1）设立边结点，6个域（每条边是一个数据元素）（2）设立顶点结点，2个域（每个顶点也是一个数据元素）data:存储顶点信息firstedge:依附顶点的第一条边结点v1