715-数据结构实用教程.pptVIP

数据结构实用教程 （C/C++描述） 徐孝凯 编著 第七章 图 §7.1 图的概念 §7.2 图的存储结构 §7.3 图的遍历 §7.1 图的概念 7.1.1 图的定义 1、逻辑定义 二元组定义： G=(V,E) V：图的顶点集 E：图的关系集（边集） 图的边： ①(x,y):无向边 ②x,y:有向边（弧） 2、相关概念 P.207. 有向图： 无向图： §7.1 图的概念 7.1.2 图中的基本术语（P.208~210.） 1、端点和邻接点 2、顶点的度、入度、出度 D（V）=ID（V）+OD（V） 3、完全图、稠密图、稀疏图 4、子图 5、路径和回路（路径、路径长度、简单路径及回路） 6、连通和连通分量（连通、连通图、非连通图、连通分量） 7、强连通图和强连通分量 8、权和网 §7.2 图的存储结构 有三种常用的方法：邻接矩阵、邻接表和边集数组 7.2.1 邻接矩阵 邻接矩阵：表示图形中顶点之间的相邻关系的矩阵。 1 vi和vj有边 A[i,j]= 0 无边 例：P.211. 图的邻接矩阵表示： 1、一维数组：存储顶点信息。 2、二维数组：顶点之间的相邻关系。 用C++描述：P.212. 7.2.2 邻接表 邻接表：图中的每个顶点建立一个邻接关系的单链表，并把它们的表头指针用向量存储的一种图的表示方法。 §7.2 图的存储结构 边结点： 1、无权： 2、带权： 表头指针数组：n个元素（n个顶点）。 图示： P.213. 图6-6 用C++描述：P.213. 注：有向图分为邻接表（出边表）和逆邻接表（入边表）。（合在一起，构成十字邻接表:图6-8） 7.2.3 边集数组 边集数组：利用一维数组存储图中所有边的一种图的表示方法。 P.215~216. §7.3 图的遍历 图的遍历：从指定的某个顶点（称此为初始点）出发，按照一定的有哪些信誉好的足球投注网站方法对图中的所有顶点各做一次访问的过程。 7.3.1 深度优先有哪些信誉好的足球投注网站遍历 深度优先有哪些信誉好的足球投注网站（Depth-First Search）：首先访问一个顶点Vi(一开始为初始点)，并将其标记为已访问过，然后从Vi 的任一个未访问过的邻接点（有向图的入边邻接点除外）出发进行深度优先有哪些信誉好的足球投注网站遍历，当Vi 的所有邻接点均被访问过时，则退回到上一个顶点Vk ，从Vk 的另一个未被访问过的邻接点出发进行深度优行遍历，直到退到初始点并且没有未被访问过的邻接点为止。 P.217~219. 7.3.2 广度优先有哪些信誉好的足球投注网站遍历 广度优先有哪些信誉好的足球投注网站（Breadth-First Search）：首先访问初始点Vi ，并将其标记为已访问过，接着访问Vi 所有未被访问过的邻接点，其访问次序可以任意。按该方法递归进行，直到图中所有和初始点Vi 有路径相通的顶点都被访问过为止。P.219~221. 7.3.2 非连通图的遍历 P.222. * * adjvex next adjvex weight next adjvex:邻接点的序号