算法合集之数据关系的简化-ppt课件.ppt

文档介绍：该【算法合集之数据关系的简化-ppt课件 】是由【mkjafow】上传分享，文档一共【47】页，该文档可以免费在线阅读，需要了解更多关于【算法合集之数据关系的简化-ppt课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。数据关系的简化
长沙雅礼中学何林
常用的数据关系:线性序列,树,图
1
2
4
3
6
5
1(1,1)
2(2,1)
4(3,1)
3(4,4)
5(5,4)
6(6,4)
1
2
3
4
5
7
8
1242585272131
坐船问题
雅礼中学有n个学生去公园划船。一条船最多可以坐两个人。如果某两个学生同姓或者同名就可以坐在一条船上。
学校希望每个同学都坐上船,同时学校想要租用最少的船。请问:学校至少要租多少船?
伍昱
伍平
何林
何刚
黄刚
何凡
伍昱
伍平
黄刚
何刚
何林
何凡
伍昱
伍平
黄刚
何刚
何林
何凡
最优解
OR
图-->树
伍昱
伍平
黄刚
何刚
何林
何凡
一个包含n个点的无向图
同名或者同姓的人之间连一条边
图模型
最小边覆盖
任意图最大匹配!
伍昱
伍平
何林
何刚
黄刚
何凡
伍昱
伍平
黄刚
何刚
何林
何凡
树结构
一片森林
每个节点和左孩子同姓
每个节点和右孩子同名
树的构造
首先假设所有人是一个连通图
黄刚
雷锋
雷涛
黄涛
欧阳锋
黄嘎
张嘎
雷震子
黄药师
周涛
张药师
树的构造
首先假设所有人是一个连通图
雷锋
雷涛
黄涛
欧阳锋
黄嘎
张嘎
雷震子
黄药师
周涛
黄刚
张药师
没有左儿子了
树的构造
首先假设所有人是一个连通图
雷锋
雷涛
黄涛
欧阳锋
黄嘎
张嘎
雷震子
黄药师
周涛
黄刚
张药师
树的构造
首先假设所有人是一个连通图
黄刚
雷锋
雷涛
黄涛
欧阳锋
黄嘎
张嘎
雷震子
黄药师
周涛
张药师
欧阳涛
树的构造
首先假设所有人是一个连通图
黄刚
雷锋
雷涛
黄涛
欧阳锋
黄嘎
张嘎
雷震子
黄药师
周涛
张药师
欧阳涛
没有右儿子
树的匹配
黄刚
雷锋
雷涛
黄涛
欧阳锋
黄嘎
张嘎
雷震子
黄药师
周涛
张药师
欧阳涛
分析叶子节点
独子!