资源描述：
《《数据结构图》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构与算法第七讲：图开场白10/08/20212内容提要图的定义图的存储结构图的遍历最小生成树最短路径拓扑排序关键路径10/08/20213图的定义10/08/20214图(Graph)是由顶点的有穷集合和顶点之间的边的集合组成，通常表示为：G(V,E)，其中G表示一个图，V是图G中顶点的集合，E是图G中边的集合。123576984图的术语（一）图按有无方向分为无向图和有向图。无向图由顶点和边构成，有向图由顶点和弧构成。弧有弧头和弧尾之分。图按照边或弧的多少分稀疏图和稠密图。如果任意两个顶点之间
2、都存在边叫完全图，有向的叫有向完全图。若无重复的边或顶点到自身的边则叫简单图。图中顶点之间有邻接点、依附的概念。无向图顶点的边数叫做度，有向图顶点分为入度和出度。图上的边或弧上带权则称为网。10/08/20215ABDCABDCABDC北京香港上海台北1463168012008087002160图a图b图c图d图的术语（二）10/08/20216图中顶点存在路径，两顶点存在路径则说明是连通的，如果路径最终回到起始点则称为回路或环，当中不重复叫简单路径。若任意两顶点都是连通的，则图就是连通图，有向则称
3、强连通图。图中有子图，若子图极大连通则就是连通分量，有向则称强连通分量。ABDCABDC图a图b图c思考1：图b是强连通图吗?图c呢？ADCABDC图fEFABC图dEF图e思考2：图d是图f的连通分量吗？图的术语（三）10/08/20217无向图中连通且n个顶点n-1条边叫生成树。有向图中一顶点入度为0其余顶点入度为1的叫有向树。一个有向图由若干棵有向树构成生成森林。ABDC图aFEGHABDC图bFEGHABDC图cFEGHABDC图dGEFABDC图eGEF图f图的抽象数据类型10/08/20
4、218ADT图（Graph）Data顶点的有穷集合和边的集合。OperationCreateGraph(&G,V,E)：按照顶点集V和边弧集E的定义构造图G。DestroyGraph(&G)：图G存在则销毁。LocateVex(G,u)：若图G中存在顶点u，则返回图中的位置。GetVex(G,v)：返回图G中顶点v的值。PutVex(G,v,value)：将图G中顶点v赋值为value。FirstAdjVex(G,&v)：返回顶点v的一个邻接顶点，若顶点在G中无邻接顶点返回空。NextAdjVex(
5、G,v,&w)：返回顶点v相对于顶点w的下一个邻接顶点，若w是v的最后一个邻接点则返回空。InsertVex(&G,v)：在图G中增添新顶点v。DeleteVex(&G,v)：删除图G中顶点v及其相关的弧。InsertArc(&G,v,w)：在图G中增添弧，若G是无向图，还需要增添对称弧DeleteArc(&G,v,w)：在图G中删除弧，若G是无向图，还需要删除对称弧DFSTraverse(G)：对图G进行深度优先遍历。HFSTraverse(G)：对图G进行
6、广度优先遍历。endADT内容提要图的定义图的存储结构图的遍历最小生成树最短路径拓扑排序关键路径10/08/20219图的存储结构相较于线性表和树，图的存储结构更加复杂下面4个图是一样的吗？10/08/202110ABDCFEGHFGEHADBCGFHEADBCFGEHADBC顺序存储的问题：物理位置无法表示元素间关系。多重链表的问题：每个顶点的指针域个数难以选择。图的存储结构：邻接矩阵（一）邻接矩阵：一维数组存顶点信息，二维数组存边信息10/08/202111V1的度为2主对角线V1的出度为2V1
7、的入度为1V0V3V2V1V0V1V2V3V0V1V2V3V0V1V2V3顶点数组边数组无向图V0V3V2V1V0V1V2V3V0V1V2V3V0V1V2V3顶点数组边数组有向图图的存储结构：邻接矩阵（二）10/08/202112V0V4V1V3V2962351V0V1V2V3顶点数组V4V0V1V2V3V4V0V1V2V3V4边数组有向网图/*无向网图的邻接矩阵表示*/typedefcharVertexType;typedefintEdgeType;#defineMAXVEX100#defineI
8、NFINITY65535typedefstruct{VertexTypevexs[MAXVEX];EdgeTypearc[MAXVEX][MAXVEX];intnumVertexes,numEdges;}MGraph;voidCreateMGraph(MGraphG){inti,j,k,w;printf("输入顶点数和边数：");scanf("%d,%d",&G.numVertexes,&G.numEdges);for(i=0;i
