通信原理大综合课件软件.pptx

在此幻灯片插入公司的徽标从“插入”菜单选择图片找到徽标文件单击“确定”重新设置徽标大小单击徽标内任意位置。徽标外部出现的方框是“调整控点”使用这些重新设置对象大小如果在使用尺寸调整控点前按下shift键，则对象改变大小但维持原比例。DATA1065865姓名学号成绩班级李红976105995机97.6ABCDEFG数据结构

2024/8/2822.6图图是一种非线性的数据结构，结点之间的关系可以是任意的。图中任意两个元素之间都可能相关。2.6.1图的基本概念2.6.2图的存储结构（1）图的邻接矩阵表示法（2）图的邻接表表示法2.6.3图的遍历

2024/8/283图定义图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构：Graph＝(V,E)其中V={x|x?某个数据对象}是顶点的有穷非空集合；E={(x,y)|x,y?V}是顶点之间关系的有穷集合，也叫做边(edge)集合。

2024/8/284若v,w∈VR,则v,w表示从v到w的一条弧，且称v为弧尾或初始点,称w为弧头或终端点,此时的图称为有向图.V1V3V2V4V1V3V2V4弧的集合G={V1，V3,V3，V4,V2，V4,V4，V1}若v,w∈VR，必有w,v∈VR，即VR是对称的，则以无序对（v,w）代替这两个有序对，表示v和w之间的一条边，此时的图称为无向图。边的集合E={(V1,V3),(V1,V2),(V1,V4),(V2,V4)}具有边的图，称做无向图，而具有弧的图，称做有向图。注意：在无向图中，(x,y)与(y,x)表示同一条边在有向图中，x,y与y,x表示不同的弧

2024/8/285假定图的顶点数为n,那么具有n(n-1)/2条边的图为无向完全图具有n(n-1)条弧的图为有向完全图V3V1V2V4V1V2V3V4

2024/8/286图的一部分或自身都可称为图的子图(Subgraph)。V3V4V1V3V1V2V4V1V2V4V1V2V4V1V2V3V4V1V1V3V1V3V2V4V1V3V2V4

2024/8/287V1V3V2V4V1V3V2V4度:依附于该顶点的边数或弧数。出度和入度仅对有向图而言，出度是指以该顶点为尾的弧数，入度是指以该顶点为头的弧数。

2024/8/288在无向图G=(V,E)中,如果存在顶点序列(Vp,Vi1,Vi2,...,Vin,Vq）使得(VP,Vi1),(Vi1,Vi2)，…，(Vin,Vq)都在E中，则称从顶点VP到Vq存在一条路径。若G是有向图，则路径也是有向的,即VP,Vi1,Vi1，,Vi2,…,Vin,Vq都在E中,VP为路径的起点，Vq为路径的终点。路径上边或弧的数目称为该路径的路径长度起点和终点相同的路径称为回路或环顶点不重复出现的路径称为简单路径。除了起点和终点相同外,其他顶点不重复出现的回路称为简单回路。V1V3V2V4V1V3V2V4

2024/8/289连通图：对无向图G而言,如果从Vi到Vj有路径，则称Vi到Vj是连通的。若图中任意两个顶点Vi和Vj(Vi≠Vj)都连通，则称G是连通图。一个无向图的各连通分量定义为该图的各个最大连通子图。V1V2V3V4V5V6V1V2V3V4V5V6(a)无向图G3(b)G3的两个连通分量对有向图G而言，若任意两个顶点Vi和Vj(Vi≠Vj)，都有一条从Vi至Vj的路径，同时还有一条从Vj到Vi的路径,则称该有向图为强连通图，有向图的各个极大强连通子图称作该有向图的各个强连通分量。V2V3V1V4V1V3V2V4

2024/8/2810如果一个图有n个顶点和小于n-1条边，则是非连通图。如果一个图多于n-1条边，则一定有环。

2024/8/2811V1V3V2V4V1V3V2V4V1V2V3V4V10010V20001V30001V41000V1V2