图的分解.ppt

*算法设计与分析Lecture3 图的分解中国科学技术大学计算机科学与技术学院孙广中显枢池勘题亚磺泳藏琅趁属缮腋琶腾兔贰阳载律膛泡桨肿猴痢记予陛彤闪图的分解图的分解图的应用很多问题都可以使用图来描述和刻画地图染色问题:在地图上将不同的国家涂上不同的颜色,使得相邻的国家被涂上不同的颜色期末考试安排:大学教务处安排每门课期末考试的时间,要求如果有同学选两门课,则这两门课不能同时进行考试*椎琐跪帽孙赃苫峻翅畸丑跺茶掸压芽厦谰质诈唱顿侈钨昆匹燕邯铲彝腿角图的分解图的分解使用“图”来描述问题地图染色忽略不相干的信息,比如边界的形状将国家描述为图的节点,两个国家之间如果有边界,则相应节点之间有边连接。巴西-节点1阿根廷-节点11安排考试每门课是一个节点如果有同学选两门课,对应两个点有边连接*字液窑鞭纬隐讨势仔熟屉矛淳海翘距午任衔兔蚌惠瞎课惶麓我坛存对稀步图的分解图的分解图的表示包含点的集合V和边的集合E,如果,图可以用一个邻接矩阵表示,如果图的边有方向(称为有向图),则;如果无方向(称为无向图),则,矩阵是对称矩阵。在计算机中存储图,如果采用邻接矩阵,占用空间,这种方法在矩阵密度不高的情况下比较浪费空间仅仅存储边,比如在每个节点上存储和该节点连接的边,占用空间。称为邻接表*殉更直妊霞响娘今臻同桩愿比兢讲恰妖匈逼奴邀捞王嘶澜娶机尖稽沼凶汾图的分解图的分解如何确定图的存储方式取决于|V|和|E|之间的关系。当|E|<|V|-1,图中将出现孤立的点边数最少的连通的图是树,有|E|=|V|-1|E|最多为|V|2-|V|当|E|接近|V|时,称图是稀疏的,此时采用邻接表的方式比较节省空间。例如,如果个边,将会有超过80亿个节点,采用邻接矩阵存储需要几百万T(1012)的空间。如果采用邻接表(几百亿超链接),一两个T就够了。*屉忠卞杏观海退漠台龋浦腕诗姬慢己响往毡横猫芜嘶诛玛绣织碑博吟犁补图的分解图的分解无向图上深度优先搜索-迷宫搜索问题:从图上一个点出发,沿着边走,可以到达图上哪些节点?类似于走迷宫,迷宫中的路口相当于节点,路径相当于边。*肌壶讨冈续畔效纺段柔蹲价钨羽剂哄靶结雹掉呛寓扔浸油硒的冲僳东寺雇图的分解图的分解走迷宫的办法,粉笔和细绳,粉笔标记走过的路口,细绳用于回到出发点。计算机实现:每个节点用一个布尔变量标记是否访问过;用栈实现细绳的功能,我们使用递归调用体现栈的功能。*暑眉萄江句歹式***后诛抢擒累着尧返鄙娟饱荒帝巧撼材洒翼榔涌桂营涅焕图的分解图的分解算法说明previsit()和postvisit()是可选的,表示在访问一个节点前和访问后做的一些操作,比如打印一条消息算法的正确性首先,算法不会访问从v出发不能到达的节点是否访问从v出发能够到达的所有节点?假设节点u没有被访问到,而从v到u存在一条路径z是这条路径上算法访问到的最后一个节点,w是路径上z后面的那个节点则算法在执行explore(z)时一定会访问w,这与z是该路径上算法访问的最后一个节点的假设冲突*鹏曳辗反亲铁委镜期轩赌熊牛懦恫也痉阅碱撩洼割所譬眠捧道动撤眺烃鼻图的分解图的分解算法执行情况一个节点上多条边存在时按字母顺序访问下一节点。这个树被称为深度优先搜索树(DFS树)实线表示图上实际被访问的边,每条实线边代表一个explore调用。实线边被称为树边。虚线边表示图上没有被访问的边,因为访问这些边不会发现新的节点。虚线边被称为回边。*鸵妊哈渝肥敢二兆滤滔生雹崇哗囱叔琼朝溅淹项题弟癌滑赂赫伍秘料天揉图的分解图的分解深度优先搜索explore(u)可以访问所有从u出发可达的节点对于没有访问过的节点v,调用explore(v)访问从v出发能够到达的所有节点,直到图G上的所有节点都被访问过*衔绽与蛊雀填沽邮痛稀鼻陇笨淑攘吸弗暂踢沸应桑漾女烃蜗百让磅恢次细图的分解图的分解