数据结构教学课件作者C语言PPT 第8章1.ppt

《数据结构教学课件作者C语言PPT 第8章1.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第八章图图的基本概念图的存储结构图的遍历最小生成树最短路径拓扑排序关键路径一、图的基本概念图定义图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构：Graph＝(V,E)其中V={x

2、x某个数据对象}是顶点的有穷非空集合；E={(x,y)

3、x,yV}是顶点之间关系的有穷集合，也叫做边(edge)集合。有向图与无向图若图G中的每条边都是有方向的，则称G为有向图。有向边也称为弧。若图G中的每条边都是没有方向的，则称G为无向图。完全图对有n个顶点的图，若为无向图且边数为n(n-1)/2，则称其为无向完全图；若为有向图且边数为n(n-1

4、)，则称其为有向完全图。邻接顶点若（vi,vj）是一条无向边，则称顶点vi和vj互为邻接点，或称vi和vj相邻接，并称边（vi,vj）关联于顶点vi和vj，或称（vi,vj）与顶点vi和vj相关联。顶点的度一个顶点v的度是与它相关联的边的条数。记作TD(v)。顶点v的入度是以v为终点的有向边的条数,记作ID(v);顶点v的出度是以v为始点的有向边的条数,记作OD(v)。子图设有两个图G＝(V,E)和G‘＝(V’,E‘)。若V’V且E‘E,则称图G’是图G的子图。路径在图G＝(V,E)中,若存在一个顶点序列vp1,vp2,…,vpm，使得(vi,

5、vp1)、(vp1,vp2)、...、(vpm,vj)均属于E，则称顶点vi到vj存在一条路径。若一条路径上除了vi和vj可以相同外，其余顶点均不相同，则称此路径为一条简单路径。起点和终点相同的路径称为简单回路或简单环。图的连通在无向图G中，若两个顶点vi和vj之间有路径存在，则称vi和vj是连通的。若G中任意两个顶点都是连通的，则称G为连通图。非连通图的极大连通子图叫做连通分量。强连通图与强连通分量在有向图中,若对于每一对顶点vi和vj,都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。权某

6、些图的边具有与它相关的数,称之为权。这种带权图叫做网络。12356874ABDCE1079667123151660304535804075生成树一个连通图的生成树是它的极小连通子图，在n个顶点的情形下，有n-1条边。不予讨论的图包含顶点到其自身的边；一条边在图中重复出现二、图的存储结构在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表，还有一个表示各个顶点之间关系的邻接矩阵。设图A=(V,E)是一个有n个顶点的图，则图的邻接矩阵是一个二维数组A.Edge[n][n]，定义：无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。邻接矩阵(Adj

7、acencyMatrix)在有向图中,统计第i行1的个数可得顶点i的出度，统计第j列1的个数可得顶点j的入度。在无向图中,统计第i行(列)1的个数可得顶点i的度。网络的邻接矩阵邻接矩阵表示法中图的描述#definen6/*图的顶点数*/#definee8/*图的边数*/typedefcharvextype;/*顶点的数据类型*/typedeffloatadjtype;/*权值类型*/typedefstruct{vextypevexs[n];adjtypearcs[n][n];}graph;21435BADCE215346203050407080邻接

8、矩阵表示法中无向网络的建立算法CREATEGRAPH(graph*ga){inti,j,k;floatw;for(i=0;ivexs[i]＝getchar();/*读入顶点信息，建立顶点表*/for(i=0;iarcs[i][j]＝0;/*邻接矩阵初始化*/for(k=0;karcs[i][j]＝w;ga->arcs[j][i]＝w;}}邻接表(AdjacencyList)无向

9、图的邻接表把同一个顶点发出的边链接在同一个边链表中，链表的每一个结点代表一条边，叫做边结点，结点中保存有与该边相关联的另一顶点的顶点下标dest和指向同一链表中下一个边结点的指针link。有向图的邻接表和逆邻接表在有向图的邻接表中，第i个边链表链接的边都是顶点i发出的边。也叫做出边表。在有向图的逆邻接表中，第i个边链表链接的边都是进入顶点i的边。也叫做入边表。带权图的边结点中保存该边上的权值cost。顶点i的边链表的表头指针adj在顶点表的下标为i的顶点记录中，该记录还保存了该顶点的其它信息。在邻接表的边链表中，各个边结点的链入顺序任意，视边结点输

10、入次序而定。设图中有n个顶点，e条边，则用邻接表表示无向图时，需要n个顶点结点，2e个边结点；用邻接表表示有向图时，若不考