资源描述：
《图论算法总结及图论建模.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、图论算法总结图的基本概念图的基本概念二元组G(V,E)称为图(graph)。V为结点(node)或顶点(vertex)集。E为图中结点之间的边的集合。点，用数字0…n-1表示点对(u,v)称为边(edge)或称弧(arc)对于边(u,v)∈E-u和v邻接(adjacent)-e和u、v关联(incident)子图(subgraph):边的子集和相关联的点集图的基本概念有向图：边都是单向(unidirectional)的,因此边(u,v)是有序数对.有时用弧(arc)专指有向边带权图：可以给边加权(weight),成为带权图,或加权图(weightedgraph).权通常代表费用、距离等,
2、可以是正数,也可以是负数稠密性：边和V(V-1)/2相比非常少的称为稀疏图(sparsegraph),它的补图为稠密图(densegraph)路径和圈一条路径(path)是一个结点序列,路上的相邻结点在图上是邻接的如果结点和边都不重复出现,则称为简单路径(simplepath).如果除了起点和终点相同外没有重复顶点和边,称为圈(cycle).不相交路(disjointpath)表示没有除了起点和终点没有公共点的路.更严格地-任意点都不相同的叫严格不相交路(vertex-disjointpath)-同理定义边不相交(edge-disjointpath)路注意:汉语中圈和环经常混用(包括一些
3、固定术语).由于一般不讨论自环(self-loop),所以以后假设二者等价而不会引起混淆连通性如果任意两点都有路径,则称图是连通(connected)的,否则称图是非连通的.非连通图有多个连通分量(connectedcomponent,cc),每个连通分量是一个极大连通子图(maximalconnectedsubgraph)完全图和补图完全图:N个顶点的图，有N(N-1)/2个节点对于(u,v),若邻接则改为非邻接,若非邻接则改为邻接,得到的图为原图的补图完全图=原图∪补图团：完全子图生成树树：N个点，N-1条边的连通图（无环连通图）生成树:包含某图G所有点的树一个图G是树当且仅当以下任
4、意一个条件成立G有V-1条边,无圈G有V-1条边,连通任意两点只有唯一的简单路径G连通,但任意删除一条边后不连通图例图的表示方法介绍两种图的表示方法：邻接矩阵与邻接表V*V的二维数组A，A[i][j]=0,若(i,j)不相连，A[i][j]=1,若(i,j)相连图1图1的邻接矩阵表示邻接矩阵无向图的邻接矩阵是对称的优点：查找/删除某条边是O(1)的缺点遍历某一点的邻居是O(V)的空间复杂度很大，O(V*V)每个结点的邻居形成一个链表邻接表图2图2的邻接表表示优点快速遍历某点所有邻居占用存储空间小，是O（边数）的，在稀疏图上的效率远胜邻接表缺点：查找/删除边不是常数时间邻接表一、宽度优先遍
5、历(BFS)二、深度优先遍历(DFS)图的遍历算法给定图G和一个源点s,宽度优先遍历按照从近到远的顺序考虑各条边.算法求出从s到各点的距离宽度优先的过程对结点着色.白色:没有考虑过的点黑色:已经完全考虑过的点灰色:发现过,但没有处理过,是遍历边界依次处理每个灰色结点u,对于邻接边(u,v),把v着成灰色并加入树中,在树中u是v的父亲(parent)或称前驱(predecessor).距离d[v]=d[u]+1整棵树的根为s宽度优先遍历(BFS)题目大意：给出N*M个格子，给出K个已经被淹没的格子，其他格子都是干的，求最大的湖的面积（一个格子的面积视为1），如果两个湿的格子四联通（上下左右
6、），则视为这两个格子同属于一个湖输入格式：第一行N，M，K接下来K个格子的坐标AvoidTheLakes（NOI题库2405）Input3453222312311Output4样例解释#....##.##..新发现的结点先扩展得到的可能不是一棵树而是森林,即深度优先森林(Depth-firstforest)特别之处:引入时间戳(timestamp)发现时间d[v]:变灰的时间结束时间f[v]:变黑的时间1<=d[v]7、V
8、深度优先遍历(DFS)初始化:time为0,所有点为白色,dfs森林为空对每个白色点u执行一次DFS-VISIT(u)时间复杂度为O(n+m)深度优先遍
9、历(DFS)括号结构性质对于任意结点对(u,v),考虑区间[d[u],f[u]]和[d[v],f[v]],以下三个性质恰有一个成立:完全分离u的区间完全包含在v的区间内,则在dfs树上u是v的后代v的区间完全包含在u的区间内,则在dfs树上v是u的后代DFS树的性质定理(嵌套区间定理):在DFS森林中v是u的后代当且仅当d[u]
