课程设计报告模板

  • 格式: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 %

本组成员郑重承诺在课程设计完成过程中不发生任何不诚信现象,一切不诚信所导致的后果均由本组成员承担。同时我组成员同意此课程设计的个人得分权重分配表。

签名(手签全部成员):