L10(数据结构：图形结构).ppt

Part 2: Data Structures 第10讲: 图形结构 第1节 图的定义及基本术语 一、图的定义 二、基本术语 三、抽象数据类型（略） 1.1 图的定义 无向图:图中顶点关系为无序对。(边) 有向图:图中顶点关系为有序对。(弧) 网：图中每一条边附有一个对应的数。(权) 有向网：弧上带权的有向图。 1.1 图的定义 1.2 基本术语 子图：简单地说，子图就是原图的一部分 度：无向图中顶点的度就是关联于该顶点的边的数目 入度：顶点v的入度即是以该顶点为终点的边的数目 出度：顶点v的出度即是以该顶点为始点的边的数目 权：与边相关的数值称为权 网：带权的图称为网 有向网：弧上带权的有向图称为有向网 1.2 基本术语 路径：从顶点Vp到Vq的顶点序列 简单路径：除起点和终点可以相同外，路径上其余顶点均不相同 回路：起点和终点相同的简单路径 连通：两个不同顶点之间有路径,该两点连通 连通图：图中的任意两个不同顶点之间都连通(即有路径)，则此图为连通图 连通分量：无向图的极大连通子图称为它的连通分量 强连通分量：有向图的极大强连通子图称为强连通分量 强连通图：有向图中，若图中任意两个不同顶点都存在双向的路径，则称该图为强连通图 例 例 第2节 图的存储结构 一、邻接矩阵 二、邻接表 2.1 邻接矩阵 １. 图的邻接矩阵表示 用一个n(n为顶点数)阶方阵来表示图的结构。以第i行第j列上的数来表示顶点vi和vj之间是否有边或边的权值。 2. 邻接矩阵存储的特点 对于无向图而言，邻接矩阵是对称的，用邻接矩阵表示的空间复杂度为S(n)=O(n^2).(方阶) 建立邻接矩阵算法的时间是O(n+n^2+e),所以其时间复杂度为O(n^2) 3.邻接矩阵存储的定义 const int n=maxn; //图中顶点数 struct graph { int v[n+1]; //存放顶点信息v1,v2…… int arcs[n+1][n+1]; //邻接矩阵 }; 2.2 邻接表 1.图的邻接表表示 这种表示法类似于树的孩子链表表示法，它首先对每个顶点vi建立一个单链表(即邻接表)，这个单链表由邻接于vi的所有顶点的结点构成。 第i个单链表中的结点表示依附于顶点vi的的边（在有向图中是以vi为尾的弧－－出边表，否则为入边表） 　给每个单链表设一头结点，头结点存放顶点vi的信息 把这些头结点顺序存于一个向量中构成顶点表. 2. 图的邻接表表示的定义 struct link //定义链表类型(表结点) { int Adjvex; //邻接域 elemtype data; //数据域，elemtype：//结点数据类型 link *nextarc; //链域 }; struct node //定义邻接表的表头类型(头结点) { elemtype vexdata; //数据域，elemtype：//顶点信息数据类型 link *firarc; //链域 } a[n+1]; 3. 邻接矩阵与邻接表 建立邻接矩阵算法的时间是O(n+n^2+e),所以其时间复杂度为O(n^2)。 建立邻接表的算法时间复杂度为O(n+e)。邻接表的空间复杂度为O(n+e)。 从存储空间角度看，邻接表更适合于表示稀疏图而邻接矩阵适合于表示稠密图。 从求解相应问题来看，在有向图中求顶点的度，采用邻接矩阵比邻接表表示更方便。 第3节 图的遍历 一、深度优先遍历 二、广度优先遍历 图的遍历：是指从图中任意一个顶点出发，对途中所有顶点访问一次且仅访问一次。 深度优先遍历（DFS depth-first search） 广度优先遍历（BFS breadth-first search） 3.1 深度优先遍历 类似于树的先根遍历 从图的某一顶点V0出发，首先访问起始点V0，然后选择V0的一个尚未访问过的邻接点W，从W出发继续进行深度优先遍历，即选择W的一个尚未访问过的邻接点出发继续进行深度优先遍历，直到被访问的顶点及其邻接点均被访问过为止， 回溯到该顶点访问前的顶点，继续访问其它尚未访问过的邻接点 不断回溯，直到起始点V0 深度优先遍历算法 在深度优先遍历中要使用到栈来保存已访问的结点，或保存已访问顶点的所有尚未访问过的邻接点。 例：基于邻接表的