数据结构中的图

1内容简介本教材采用面向对象的观点讨论数据结构技术，并以C++类模板作为算法描述工具。教材在简要回顾C++程序设计概念的基础上，全面系统地介绍了线性表、栈和队列、串、数组和广义表、树和二叉树及图等数据结构，讨论了常用的查找和排序技术，对每一种数据结构，除了详细阐述其逻辑结构、存储结构和相关算法外，还对所有算法进行了C++语言实现和评价，并给出了应用实例。教材附录给出了上机实验内容。2教材目录第0章C++程序设计语言预备知识0.1一个简单C++语言程序0.2指针与引用0.3动态存贮分配0.4函数0.5类与对象0.6运算符重载0.7模板3第1章绪论1.1数据结构的产生和发展1.2数据结构研究的内容1.3基本概念和术语1.4算法第2章线性表2.1线性表的逻辑结构2.2线性表的顺序存储结构2.3线性表的链式存储结构2.4顺序表和链表的比较2.5线性表的应用4第３章栈和队列3.1栈3.2队列3.3栈的应用第4章串4.1串的逻辑结构4.2串的顺序存储结构4.3串的链式存储结构4.4串的应用5第5章数组和广义表5.1数组5.2矩阵的压缩存储5.3广义表5.4多维数组的应用6第6章树和二叉树6.1树的逻辑结构6.2树的顺序存储结构6.3二叉树的逻辑结构6.4二叉树的存储结构6.5线索二叉树6.6树、森林与二叉树的转换6.7树的应用7第7章图7.1图的逻辑结构7.2图的存储结构7.3图的遍历7.4生成树和最小生成树7.5最短路径7.6DAG图及其应用8第8章排序8.1概述8.2插入排序8.3交换排序8.4选择排序8.5归并排序8.6基数排序8.7各种内排序方法的比较和选择9第9章查找9.1概述9.2线性表的查找9.3树表的查找9.4散列表的查找附录实验内容10第7章图117.1图的逻辑结构7.2图的存储结构7.3图的遍历本章主要内容7.4生成树和最小生成树7.5最短路径7.6DAG图及其应用127.1.1图的定义7.1图的逻辑结构图G由结点的有穷非空集合V和边的有穷集合E组成，记为G=(V，E)。在图结构中，将结点称为顶点，以便与树形结构加以区别，边则是顶点的偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。通常，也将图G的顶点集和边集分别记为V(G)和E(G)。E(G)可以是空集，若E(G)为空，则图G只有顶点而没有边。137.1.2图的基本术语1.有向图和无向图如果G中的每条边都是有方向的，则称G为有向图。在有向图中，一条有向边是由两个顶点组成的有序对，通常用尖括号表示。例如，vi,vj表示一条有向边，vi是边的始点，vj是边的终点。14若图G中的每条边都是没有方向的，则称G为无向图。无向图中的边均是顶点的无序对，通常用圆括号表示。无序对(vi,vj)和(vj,vi)表示同一条边。15v1v2v3v4v5无向图G1，在该图中：V(G1)={v1，v2，v3，v4，v5}E(G1)={(v1,v2)，(v1,v4)，(v2,v3)，(v2,v5)，(v3,v4)，(v3,v5)}16v1v2v3v4有向图G2，该图的顶点集和边集分别为：V(G2)={v1，v2，v3，v4，v5}E(G2)＝{v1,v2，v1,v3，v3,v4，v4,v1}172.稠密图和稀疏图3.边和顶点的关系若(vi,vj)是一条无向边，则称顶点vi和vj互为邻接点(adjacent)，或称vi和vj相邻接，并称(vi,vj)依附或关联(incident)于顶点vi和vj或称(vi,vj)与顶点vi和vj相关联。若vi,vj是一条有向边，则称此边是顶点vi的一条出边，同时也是顶点vj的一条入边；称顶点vi邻接到(或邻接于)顶点vj，并称边vi,vj关联于vi和vj，或称vi,vj与顶点vi和vj相关联。184.顶点的度无向图中顶点v的度是关联于该顶点的边的数目，记为D(v)。在有向图中，以顶点v为终点的边的数目称为v的入度，记为ID(v)；以顶点v为始点的边的数目称为v的出度，记为OD(v)。顶点v的度定义为该顶点的入度和出度之和，即D(v)=ID(v)+OD(v)。195.子图设G=(V，E)是一个图，若V´是V的子集，E´是E的子集，且E´的边所关联的顶点均在V´中，则G´=(V´，E´)也是一个图，并称其为G的子图。206.路径设G是图，若存在一个顶点序列vp，v1，v2，…，vq-1，vq使得(vp,v1)，(v1,v2)，…，(vq-1,vq)属于E，则称vp到vq存在一条路径(path)，其中vp为起点，vq为终点。路径的长度是该路径上边的数目。217.有根图和图的根8.无向图的连通图和连通分量9.有向图的强连通图和强连通分量10.网络227.1.3图的基本操作图的基本操作:图的初始化：Create()销毁图：Destory()删除图中所有元素，回收图所占空间。取顶点：GetVex(i)取图中的第i个顶点的数据信息。23插入顶点：InsertVex(v)在图中插入顶点v。删除顶点：DeleteVex(v)删除图中顶点v。插入边或弧：Insert(v,w)在图中插入一条边(v,w)或弧v,w，如是无向图，还应增加对称边(w,v)。删除边或弧：Delete(v,w)247.2图的存储结构图的存储表示方法很多，邻接矩阵表示法和邻接表表示法是两种最常用的方法。7.2.1邻接矩阵邻接矩阵是一种表示顶点之间相邻关系的矩阵。设G=(V，E)是具有n个顶点的图，则G的邻接矩阵A是具有如下性质的n阶方阵：25中的边不是或若中的边是或若)(,),(,0)(,),(,1]][[GEvvvvGEvvvvjiajijijiji对于无向图，若从顶点vi到vj有一条无向边(vi,vj)，则a[i][j]=1，a[j][i]=1;否则a[i][j]=0，a[j][i]=0，故无向图的邻接矩阵是一个对称矩阵。对于有向图，若从顶点vi到vj有一条有向边vi,vj，则a[i][j]=1；否则a[i][j]=0。26(a)图G10v0v3v1v200110011110111101A27(b)图G11v0v1v4v3v201000000010101010001000102A28基于邻接矩阵存储结构的图的类模板定义cx7_1.h29邻接矩阵的基本操作及其实现:1．求顶点在图中的位置2．创建图3．顶点的增删4．弧的增删5．输出邻接矩阵6．销毁有向图307.2.2邻接表邻接表表示法是图的一种链接存储结构，类似于树的孩子链表表示法。对于图G中的每个顶点vi，该方法把所有邻接于vi的顶点链成一个单链表，这个单链表就称为顶点vi的邻接表，邻接表中每个结点有两个域：其一是邻接点域(adjvex)，用以存放与vi相邻接的顶点vj的序号j；其二是链域(next)，用来指示与vi相邻接的下一顶点，从而将邻接表的所有表结点链在一起。邻接点adjvex链域next31为每个顶点vi的邻接表设置一个头结点，头结点中包含两个域，其中一个是顶点域vertex，用来存放顶点vi的数据信息；另一个是指针域firstedge，它指向vi的邻接表的开始结点，相当于vi的邻接表的头指针。为了便于随机访问任一顶点的邻接表，将所有头结点顺序存储在一个一维数组中，称为顶点表，将其中的头结点称为顶点表结点。这样就构成了图的邻接表表示。顶点域vertex指针域firstedge32下标vertexfirstedge边表0123∧v01023∧v1201∧v2301∧v3(a)图G10v0v3v1v233(b)图G11v0v1v4v3v2下标顶点表出边表01∧v0104∧v1213∧v230∧v343∧v434邻接表的基本操作及其实现:求顶点在图中的位置创建有向图顶点的增删弧的增删输出邻接表销毁有向图357.2.3邻接矩阵和邻接表的比较367.3图的遍历图的遍历是指从图中某一顶点出发，对图中所有顶点访问一次且仅访问一次的操作。377.3.1深度优先搜索遍历深度优先搜索(DFS)遍历类似于树的先序遍历。假定给定图G的初态是所有顶点均未曾访问过。则从图中某顶点v出发进行深度优先搜索遍历的基本思想是：(1)访问顶点v；(2)从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先搜索遍历；(3)重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。38从图中某顶点v出发，基于邻接矩阵表示的深度优先搜索的递归过程如程序sf7_13.cpp所示。从图中某顶点v出发，基于邻接表表示的深度优先搜索的递归过程如程序sf7_15.cpp所示。39无向图G12和它的深度优先搜索遍历:(a)v0v1v3v4v5v2v6v7v0v1v3v4v5v2v6v711v71v72v73v74v75v76v714v713v77v712v710v78v79v7(b)得到的顶点访问序列为：v0v1v2v5v4v6v3v7407.3.2广度优先搜索遍历广度优先搜索(breadthfirstserch，BFS)遍历类似于树的层序遍历。从图中某顶点v出发进行广度优先遍历的基本思想是：(1)访问顶点v；(2)依次访问v的各个未被访问的邻接点v1，v2，…，vk；(3)分别从v1，v2，…，vk出发依次访问它们未被访问的邻接点，并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问，直至图中所有与顶点v有路径相通的顶点都被访问到。41无向图G12的广度优先搜索遍历:v0v1v3v4v5v2v6v7a1v7a2v7a3v7b1v7b2v7c1v7c2v7v0v1v3v4v2v6v5v7427.4生成树和最小生成树在图论中，常常将一个无回路的连通图定义为树。没有确定谁是根的图称为自由树。7.4.1生成树与生成森林如果连通图G的一个子图是一棵包含G中所有顶点的树，则该子图称为G的生成树。43由深度优先搜索得到的生成树称为深度优先生成树，简称为DFS生成树；由广度优先搜索得到的生成树称为广度优先生成树，简称为BFS生成树。44(a)图G10v0v3v1v2(a)DFS生成树(b)BFS生成树v0v1v2v3v1v2v3v045图的生成树不唯一。从不同的顶点出发进行遍历，可以得到不同的生成树。467.4.2最小生成树带权的连通图也称连通网，其生成树也是带权的，我们把生成树各边的权值总和称为该生成树的权。图的生成树不唯一，从不同的顶点出发遍历带权的连通图，可以得到不同的带权生成树，其中权值最小的生成树称为最小生成树，简称为MST。47普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法是两个利用MST性质构造最小生成树的算法。1．普里姆算法假设G=(V,E)是连通网络，TE是G上最小生成树中边的集合。算法从V中任取一个顶点作为源点(假定为v0)，此时U={v0}(v0∈V)，TE＝{}开始，重复执行下述操作：在所有u∈U，v∈V-U的边(u，v)∈E中找一条代价最小的边(u，v)并入集合TE，同时u并入U，直至U＝V为止。此时TE中必有n-1条边，则T＝(V，TE)为G的最小生成树。4849505152采用邻接矩阵存储的Prim算法sf7_20.cpp532．克鲁斯卡尔算法假设连通网G＝(V，E)，则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V，{})，图中每个顶点自成一个连通分量。在E中选择权值最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条权值最小的边。依次类推，直至T中所有顶点都在同一连通分量上为止。54555657克鲁斯卡尔算法sf7_21.cpp587.5最短路径7.5.1单源最短路径所谓单源最短路径：是指对已知图G=(V，E)，给定源顶点v，找出v到其余各顶点的最短路径。591.迪杰斯特拉(Djikstra)算法基本思想迪杰斯特拉提出了按路径长度递增的次序逐一产生最短路径的算法：首先求得长度最短的一条最短路径，再求得长度次短的一条最短路径，依此类推