数据结构课件PPT110章全 第七章 图.ppt

《数据结构课件PPT110章全 第七章 图.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1、图的定义和术语2、图的存储结构3、图的遍历4、图的连通性问题5、有向无环图及其应用6、最短路径第七章图图的定义和术语ABCDABCDE有向图G1无向图G2结点或顶点：有向边（弧）、弧尾或初始结点、弧头或终止结点ABAB有向图：G1=（V1，{A1}）V1={A,B,C,D}A1={,,,}结点或顶点：无向边或边AB无向图：G2=（V2，{A2}）V2={A,B,C,D,E}A2={(A,B),(A,C>,(B,D),(B,E>,(C,E),(D,E)}AB图的定义和术语ABCD无向图G2ABCDA

2、CABCD有向图G1的子图ABCDEABDEAABCDABCDE无向图G2的子图有向图G1图的定义和术语无向图的连通性ABCDE路径：在无向图G=(V,{E})中由顶点v至v‘’的顶点序列。回路或环：第一个顶点和最后一个顶点相同的路径。简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。连通：顶点v至v‘’之间有路径存在连通图：无向图图G的任意两点之间都是连通的，则称G是连通图。连通分量：极大连通子图FGIJLHMKABCDEHMFGIJLK无向图G无向图G的三个连通分量图的定义和术语有向图的连通性路径：在有向图G=

3、(V,{E})中由顶点v经有向边至v‘’的顶点序列。回路或环：第一个顶点和最后一个顶点相同的路径。简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。连通：顶点v至v‘’之间有路径存在强连通图：有向图图G的任意两点之间都是连通的，则称G是强连通图。强连通分量：极大连通子图有向图G有向图G的两个强连通分量ABCDABCD图的定义和术语生成树：极小连通子图。包含图的所有n个结点，但只含图的n-1条边。在生成树中添加一条边之后，必定会形成回路或环。ABCDEHMABCDEHM无向图G无向图G的生成树图的定义和术语完全图：有

4、n(n-1)/2条边的无向图。其中n是结点个数。有向完全图：有n(n-1)条边的有向图。其中n是结点个数。边的权值，边有权的图称之为网络。邻接点：无向图结点的度有向图结点的出度和入度ABCDEHM无向图G1图的其它术语有向图G2ABCD图的存储结构图的四种常用的存储形式：邻接矩阵和加权邻接矩阵（labeledadjacencymatrix）邻接表十字链表邻接多重表1、邻接矩阵和加权邻接矩阵（labeledadjacencymatrix）ABCD无权值的有向图的邻接矩阵设有向图具有n个结点，则用n行n列的布尔矩阵A表示该有向图；并且A[i,j

5、]=1,如果i至j有一条有向边；A[I,j]=0如果i至j没有一条有向边注意：A[i,i]=0。出度:i行之和。入度:j列之和。表示成右图矩阵0110000000011000图的存储结构1、邻接矩阵和加权邻接矩阵（labeledadjacencymatrix）（续）无权值的无向图的邻接矩阵设无向图具有n个结点，则用n行n列的布尔矩阵A表示该无向图；并且A[i,j]=1,如果i至j有一条无向边；A[I,j]=0如果i至j没有一条无向边注意：A[i,i]=0。i结点的度:i行或i列之和。上三角矩阵或下三角矩阵。表示成右图矩阵0110010011

6、100010100101110ABCDE图的存储结构1、邻接矩阵和加权邻接矩阵（labeledadjacencymatrix）（续）有向图的加权邻接矩阵设有向图具有n个结点，则用n行n列的矩阵A表示该有向图；并且A[i,j]=a,如果i至j有一条有向边且它的权值为a。A[i,j]=‘空或其它标志；如果i至j没有一条有向边。ABCD表示成右图矩阵abbbaaaaabbb优点：判断任意两点之间是否有边方便，仅耗费O(1)时间。缺点：即使<

7、ncylist）设有向图或无向图具有n个结点，则用结点表、边表表示该有向图或无向图。结点表：用数组或单链表的形式存放所有的结点。如果结点数n已知，则采用数组形式，否则采用单链表的形式更好。边表（边结点表）：每条边用一个结点进行表示。同一个结点的所有的边形成它的边结点单链表。优点：内存＝结点数＋边数缺点：确定i-->j是否有边，最坏需耗费O(n)时间。无向图同一条边表示两次边表空间浪费一倍。有向图中寻找进入某结点的边，非常困难。datafirstarc结点表中的结点的表示：用数组data:结点的数据场，保存结点的数据值。firstarc:结点

8、的指针场，给出自该结点出发的的第一条边的边结点的地址。图的存储结构2、邻接表（adjacencylist）datafirstarc结点表中的结点的表示：续用单链表data:结点的