课程设计报告模板
- 格式:doc
- 大小:39.00 KB
- 文档页数:4
深 圳 大 学 课 程 设 计 报 告
课程名称: 数据结构与算法
项目名称: 图着色问题
任课教师: 张 艳
学 院: 计算机与软件学院
专 业:
组员1 姓名: 黄展洽 学号: 2015150272
组员2 姓名: 陈捷帆 学号: 2015150278
组员3 姓名: 董栩华 学号: 2015150088
教师批阅意见:
成绩评定:
指导教师签字:
年 月 日
一、 问题描述
给定无向连通图G=(V,E),求图G的最小色数K。
设计一个算法,用K种颜色对G中的顶点着色,使任意两个相邻顶点着色不同。
采用的算法:贪心法
要求随机生成连通图,自动绘制连通图,在图上显示着色结果。
二、 算法描述(详细算法过程、复杂度分析等)
图的m色优化算法可用贪心法来解,其思想是:
任选一顶点着色1,在图中尽可能多的用颜色1着色;
当不能用颜色1着色时,转用颜色2将未着色的顶点尽可能多的着色···
直到所有顶点都被着色停止。
三、 算法实现 (数据结构、流程图)
四、 实验结果(效果、功能、以及其他相关图片,数据等)
五、问题分析(碰到什么问题,如何解决)
六、心得与体会
七、任务分工及所完成的状况
八、参考文献(格式如下)
[1] “数据结构(C语言版)”, 严慧敏、吴伟民,清华大学出版社
[2] “数据结构、算法与应用(C++语言描述)”,【美】Sartaj Sahni,机械工业出版社
[3] “算法设计与分析”,张德富,国防工业出版社
九、程序源码(对核心代码和数据变量加注释)
十、诚信承诺(注此项不可分开为两页!)
个人得分权重分配表
排序 姓名 学号 项目个人权重
1 董栩华 2015150088 35 %
2 陈捷帆 2015150278 35 %
3 黄展洽 2015150272 30 %
我组成员总共____3___名,权重总和为: 100 %
本组成员郑重承诺在课程设计完成过程中不发生任何不诚信现象,一切不诚信所导致的后果均由本组成员承担。同时我组成员同意此课程设计的个人得分权重分配表。
签名(手签全部成员):