计算机软件基础ppt课件.ppt

《计算机软件基础ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机软件基础Thesoftwarebasicofcomputer主讲：刘志强西安交通大学计算机教学实验中心第5单元非线性数据结构图7/27/20211教学目标了解有关图的基本概念存储结构及实现遍历算法2教学要求通过本单元学习，了解、掌握有关图:基本概念有向图、无向图、连通图、网存储结构及实现邻接矩阵、邻接表遍历及其它操作深度优先、广度优先遍历应用3本单元涉及的内容第2章2.5图的逻辑结构及其运算2.6图类2.7图的遍历2.8树和图的基本应用P73~P904一、图及其基本概念图是一种较之线性表和树形结构更为复杂的非线性数据结构

2、。图中各数据元素之间的关系可以是任意的，描述的是“多对多”的关系。图的定义有向图、无向图图的基本概念邻接点、顶点、边、弧、顶点的度连通图、强连通图、连通分量网、权5图结构图是对结点的前趋和后继个数不加限制的数据结构。有关图的理论，在“离散数学”的图论中有详细论述和证明。在DS中，只讨论图在计算机中的实现和操作。现实生活中，图的应用范围很广泛，涉及：电讯工程、电网调度、集成电路设计交通管理、工程管理、系统工程等领域6图（Graph）的定义图G=（V，E）其中：V={v1，v2，……,vn}是非空有穷的结点集合;E是顶点偶对的集合

3、。例，图G1=（V，E）V={v1，v2，v3，v4}E={（v1，v2），（v1，v3），（v2，v1），（v2，v3），（v2，v4），（v3，v1），（v3，v2），（v4，v2）}oooov1v2v3v4G17有向图、无向图有向图（Digraph）图G中顶点的偶对若是有向的，形成的图称有向图。如图G2所示。为示区别，其偶对用表示。无向图（Undigraph）图G中顶点的偶对若是无向的，形成的图称为无向图，其偶对用（vx，vy）表示，如图G1所示。G2=（V，E）V={1，2，3，4}E={〈1，2〉，〈1

4、，3〉，〈3，4〉，〈4，1〉}1324G28边、弧边（Edge）顶点间的关系可描述为顶点的偶对，也称为顶点的边。记为：（Vx，Vy）。边是无序的，可以看成是（Vx，Vy），也可以看成是（Vy，Vx）。弧（Arc）若顶点间的边是有方向性（有序）的，则称该偶对为弧。记为：〈Vx，Vy〉。弧是有序的，〈Vx，Vy〉表示从Vx到Vy。弧头（Head）弧的终点（TerminaLNode）称为弧头（方向前方）。弧尾（Tail）弧的起始点（InitialNode）称为弧尾（方向后方）。弧〈Vx，Vy〉表示为，VxVy弧尾弧头9顶点、邻接点

5、顶点（Vertex）图中的数据元素（结点）称为顶点。如图G1、G2中的Ｖ1、Ｖ2，1，2。邻接点（Adjacent）无向图中，若边（Ｖx，Ｖy）E，则Ｖx、Ｖy互为邻接点。有向图中，若弧〈Ｖx，Ｖy〉E，则Ｖy是Ｖx的邻接点，反之，不是。VxVyＶx、Ｖy互为邻接点VxVyＶy是Ｖx的邻接点1324G2oooov1v2v3v4G110顶点的度（Degree）无向图中，顶点的度是以该顶点为一个端点的边的条数。例如，G1中V2的度为3，V4的度为1。有向图中，以某顶点为弧头的弧的数目称为该顶点的入度（Indegree）。例如G

6、2中顶点1的入度为1。以某顶点为弧尾的弧的数目称为该顶点的出度（Outdegree）。例如G2中顶点1的出度为2。该顶点的度=入度+出度。例如，G2中顶点1的度=2+1=3。oooov1v2v3v4G11324G211路径、长度路径（Path）在图中，从顶点Vx到顶点Vy的顶点序列（Vx，V1，V2，…,Vn,Vy)称为从Vx到Vy的路径。路径可能是不唯一的。例如，G1中，V1到V3的路径为：（V1V2V3）或（V1V3）；而G2中，1到4的路径为<134>。长度（Length）路径的长度是该路径上边或弧的数目。例如，G1中V

7、1到V3的长度为1或2；而G2中1到4的长度为2。1324G2oooov1v2v3v4G112连通图、强连通图、连通分量12连通图（ConnectedGraph）在无向图中，若每一对顶点间都有路径，称此图是连通图。如图G3所示。连通分量（ConnectedComponent）无向图中的极大连通子图称为连通分量。强连通图（StronglyConnectedGraph）在有向图中，若每对顶点Vx到Vy间都存在Vx到Vy，及从Vy到Vx的路径，则称此图是强连通图。如图G4所示。345G321345G413子图、生成树子图有两个图G和

8、G1，若V1V，E1E，即V1中的顶点G=（V，E）都属于V中的顶点，E1中的关系都G1=（V1，E1）属于E中的关系，则称G1是G的子图。生成树设G是一个连通图，G中任一包含G的所有顶点的子图称为生成子图。如果该子图是树，则称为G的生成树。G的生成树不是唯一的。一棵有n