《10月25日上午曹文《图的相关算法》ppt课件》由会员分享，可在线阅读，更多相关《10月25日上午曹文《图的相关算法》ppt课件（118页珍藏版）》请在金锄头文库上搜索。
1、为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益图论为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益图的基本概念为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益图的基本概念二元组二元组 G(V,E) 称为图称为图(graph)。 V为结点为结点(node)或顶点或顶点(vertex)集。集。 E为图中结点之间的边的集合。为图中结点之间的边的集合。点，用数字点，用数字0n-1表示表示点对点对 (
2、u,v) 称为边称为边(edge)或称弧或称弧(arc)对于边对于边 (u,v)E-u和和v邻接邻接(adjacent)-e和和u、v关联关联(incident)子图子图(subgraph): 边的子集和相关联的点集边的子集和相关联的点集为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益图的基本概念有向图：边都是单向有向图：边都是单向(unidirectional)的的, 因此边因此边(u,v)是有序数是有序数对对. 有时用弧有时用弧(arc)专指有向边专指有向边带权图：可以给边加权带权图：可以给边加权(weight), 成为带
3、权图成为带权图, 或加权图或加权图(weighted graph). 权通常代表费用、距离等权通常代表费用、距离等, 可以是正数可以是正数, 也可也可以是负数以是负数稠密性：边和稠密性：边和V(V-1)/2相比非常少的称为稀疏图相比非常少的称为稀疏图(sparse graph), 它的补图为稠密图它的补图为稠密图(dense graph)为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益路径和圈一条路径一条路径(path)是一个结点序列是一个结点序列, 路上的相邻结点在图上是邻接路上的相邻结点在图上是邻接的的如果结点和边都不重复
4、出现如果结点和边都不重复出现, 则称为简单路径则称为简单路径(simple path). 如果如果除了起点和终点相同外没有重复顶点和边除了起点和终点相同外没有重复顶点和边, 称为圈称为圈(cycle). 不相交路不相交路(disjoint path)表示除了起点和终点没有公共点的路径表示除了起点和终点没有公共点的路径. 更严格地更严格地-任意点都不相同的叫严格不相交路任意点都不相同的叫严格不相交路(vertex-disjoint path)-同理定义边不相交同理定义边不相交(edge-disjoint path)路路注意注意: 汉语中圈和环经常混用汉语中圈和环经常混用(包括一些固定术语包括一些
5、固定术语). 由于一般不讨由于一般不讨论自环论自环(self-loop), 所以以后假设二者等价而不会引起混淆所以以后假设二者等价而不会引起混淆为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益连通性如果任意两点都有路径如果任意两点都有路径, 则称图是连通则称图是连通(connected)的的, 否则称图否则称图是非连通的是非连通的. 非连通图有多个连通分量非连通图有多个连通分量(connected component, cc), 每个连通分每个连通分量是一个极大连通子图量是一个极大连通子图(maximal connected
6、subgraph)为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益完全图和补图完全图完全图:N个顶点的无向图，有个顶点的无向图，有N(N-1)/2条条边边对于对于(u,v), 若邻接则改为非邻接若邻接则改为非邻接, 若非邻接则改为邻接若非邻接则改为邻接, 得到的得到的图为原图的补图图为原图的补图完全图完全图=原图原图补图补图团：完全子图团：完全子图为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益生成树树：树：N个点，个点，N-1条边的连通图（无环连通图）条边的
7、连通图（无环连通图）生成树生成树: 包含某图包含某图G所有点的树所有点的树一个图一个图G是树当且仅当以下任意一个条件成立是树当且仅当以下任意一个条件成立G有有V-1条边条边, 无圈无圈G有有V-1条边条边, 连通连通任意两点只有唯一的简单路径任意两点只有唯一的简单路径G连通连通, 但任意删除一条边后不连通但任意删除一条边后不连通为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益图例为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益图的表示方法介绍两种图的表示方法：
8、邻接矩阵与邻接表介绍两种图的表示方法：邻接矩阵与邻接表V*V的二维数组的二维数组A，Aij=0,若若(i,j)不相连，不相连，Aij=1,若若(i,j)相连相连图图1图图1的邻接矩阵表示的邻接矩阵表示为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益邻接矩阵无向图的邻接矩阵是对称的无向图的邻接矩阵是对称的优点：查找优点：查找/删除某条边是删除某条边是O(1)的的缺点缺点遍历某一点的邻居是遍历某一点的邻居是O(V)的的空间复杂度很大，空间复杂度很大，O(V*V)为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位
9、工作人员聘用制度，保障用人单位和职工的合法权益每个结点的邻居形成一个链表每个结点的邻居形成一个链表邻接表图图2图图2的邻接表表示的邻接表表示为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益优点优点快速遍历某点所有邻居快速遍历某点所有邻居占用存储空间小，是占用存储空间小，是O（边数）的，在稀疏图上的效率远胜邻（边数）的，在稀疏图上的效率远胜邻接矩阵接矩阵缺点：查找缺点：查找/删除边不是常数时间删除边不是常数时间邻接表为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权
10、益前向星是一种特殊的边集数组前向星是一种特殊的边集数组, ,我们把边集数组中的每一条边按我们把边集数组中的每一条边按照起点从小到大排序照起点从小到大排序, ,如果起点相同就按照终点从小到大排序如果起点相同就按照终点从小到大排序, ,并记录下以某个点为起点的所有边在数组中的起始位置和存储长并记录下以某个点为起点的所有边在数组中的起始位置和存储长度度, ,那么前向星就构造好了那么前向星就构造好了. .用用lenileni来记录所有以来记录所有以i i为起点的边在数组中的存储长度为起点的边在数组中的存储长度. .用用headiheadi记录以记录以i i为边集在数组中的第一个存储位置为边集在数组中的
11、第一个存储位置. .链式前向星为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益那么排完序后就得到那么排完序后就得到: :编号编号: 1 2 3 4 5 6 7: 1 2 3 4 5 6 7起点起点u: 1 1 1 2 3 4 4u: 1 1 1 2 3 4 4终点终点v: 2 3 5 3 4 1 5v: 2 3 5 3 4 1 5head1 = 1 len1 = 3head1 = 1 len1 = 3head2 = 4 len2 = 1head2 = 4 len2 = 1head3 = 5 len3 = 1head3 = 5
12、len3 = 1head4 = 6 len4 = 2head4 = 6 len4 = 2链式前向星为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益但是利用前向星会有排序操作但是利用前向星会有排序操作, ,如果用快排时间至少为如果用快排时间至少为O(nlog(n)O(nlog(n)如果用链式前向星如果用链式前向星, ,就可以避免排序就可以避免排序. .我们建立边结构体为：我们建立边结构体为：struct edgeint next,to,w;struct edgeint next,to,w;其中其中edgei.toedgei.to
13、表示第表示第i i条边的终点条边的终点,edgei.next,edgei.next表示与第表示与第i i条边同起点的条边同起点的下一条边的存储位置下一条边的存储位置,edgei.w,edgei.w为边权值。为边权值。另外还有一个数组另外还有一个数组headi,headi,它是用来表示以它是用来表示以i i为起点的第一条边存储的位置，为起点的第一条边存储的位置，实际上你会发现它是以实际上你会发现它是以i i为起点的所有边的最后输入的那个编号。为起点的所有边的最后输入的那个编号。headhead数组一般初始化为数组一般初始化为-1-1。链式前向星为了规范事业单位聘用关系，建立和完善适应社会主义市场
14、经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益void add(int u,int v,int w) void add(int u,int v,int w) edgecnt.w = w; edgecnt.w = w; edgecnt.to = v; edgecnt.to = v; edgecnt.next = headu; edgecnt.next = headu; headu = cnt+; headu = cnt+; 我们在遍历以我们在遍历以u u节点为起始位置的所有边的时候是这样的节点为起始位置的所有边的时候是这样的: : for(int i=headu;i;i=edg
15、ei.next) for(int i=headu;i;i=edgei.next)链式前向星为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益一、宽度优先遍历一、宽度优先遍历(BFS)(BFS)二、深度优先遍历二、深度优先遍历(DFS)(DFS)图的遍历算法为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益给定图给定图G和一个源点和一个源点s, 宽度优先遍历按照从近到远的顺序考虑各条宽度优先遍历按照从近到远的顺序考虑各条边边. 算法求出从算法求出从s到各点的距离到各
16、点的距离宽度优先的过程对结点着色宽度优先的过程对结点着色. 白色白色: 没有考虑过的点没有考虑过的点黑色黑色: 已经完全考虑过的点已经完全考虑过的点灰色灰色: 发现过发现过, 但没有处理过但没有处理过, 是遍历边界是遍历边界依次处理每个灰色结点依次处理每个灰色结点u, 对于邻接边对于邻接边(u, v), 把把v着成灰色并加入树着成灰色并加入树中中, 在树中在树中u是是v的父亲的父亲(parent)或称前驱或称前驱(predecessor). 距离距离dv = du + 1整棵树的根为整棵树的根为s宽度优先遍历(BFS)为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益为了规范事业单位聘用关系，建立和完善适应社会主义市场经济体制的事业单位工作人员聘用制度，保障用人单位和职工的合法权益题目大意：题目大意： 给出给出N*M个格子，给出个格子，给出K个已经被淹没的格子，其他格子都是个已经被淹没的格子，其他格子都是干的，求最大的湖的面积（一个格子的面积视为干的，求最大的湖的面积（一个格子的面积视为1），如果两个），如果两个湿的格子
