算法设计与分析实验报告

1、学院：信息科学与工程学院专业：计算机科学与技术0804班学号： 0909081711 姓名：刘 勇指导老师：郑 瑾2010年 1月 6 日算法分析与设计实验报告目录一、 实验要求二、 实验内容三、 思想设计四、 测试结果五、 实验心得六、 附 ：源程序一、实验要求实验一用 bfs 求最短路径(1)readgraph ( ) 从文件中读入图的信息；(2)printgraph ( ) 以邻接表的形式显示图的信息；(3)shortestpath( ) 输入图的两个顶点，若存在路径，显示路径长度，并顺序输出路径中的顶点。实验二用 dfs 判断图是否连通，图中是否有环(1)connectivity_df

2、s(mgraph m) 判断图是否连通；(2)cycle_dfs(mgraph m)判断图中是否有环存在。实验三两个经典问题(1)n-queens 问题的求解；(2)m-coloring 问题的求解。二、实验内容1、实验一的内容（1）要求用三个函数完成实实验： readgraph(),printgraph(), shortestpath()。图的信息如：可存储其信息在文件中，如下：1 2 1 3 1 4 2 4 （2）输入顶点 s、d，求出两顶点之间的最短路径长度，并顺序输出 s 到 d 之间的路径中的顶点。若无，则不用输出。2、实验二的内容（1）给予一个图，利用dfs 遍历图，测试图是否连通

3、；（2）测试给予的图是否有环存在。3、实验三的内容（1）n 皇后问题，每一行或每一列只能只能放一个皇后，并且斜线上也不能放；否则皇后之间会互相攻击；（2）m着色问题，给定一个无向连通图g和 m种不同的颜色。用这些颜色为图g的各顶点着色， 每个顶点着一种颜色。试问是否有使得g中任何一条边的2 的顶点着不同颜色的着色法 。三、思想设计1、实验一的思想先把图的信息存于文件graph.txt中，用 readgraph( )函数实现从文件读入信息，把图的信息转存与邻接矩阵中。在求最短路径时，用到广度优先搜索遍历。首先访问所以和初始顶点邻接的顶点，然后是离它两条边的所有未访问的顶点，以此类推，直到所有与初

4、始顶点同一个连通分量中的顶点都访问了为止。如果仍然存在未访问的顶点，该算法必须从其他的连通分量中的顶点开始。用 bfs 来求两个顶点间边的数量最少的路径，从一个顶点开始遍历，一旦访问到另一个顶点就结束。便可得到从我们所求的最短路径。2、实验二的思想利用 dfs 求解图的连通问题，可以从任意顶点开始访问图的顶点，然后把该顶点标记为已访问。在每次迭代的时候， 该算法紧接着处理与当前顶点邻接的未访问的顶点。这个过程一直持续， 直到遇到一个死端的时候， 并试着继续从那里访问未访问的顶点，在后退到起始顶点，并且起始顶点也是一个死端，该算法最终停止了。四、测试结果1、实验一测试结果如下图：2、实验二的测试

5、结果3、实验三的测试结果（1）n-queens （2）m-coloring 五、实验心得通过实验课的学习， 从课本的许多经典算法理论中看到他们的实现解决问题是非常有效的，增加了自己的动手能力， 在计算机科学领域，有思想是非常重要的， 并且还要有很强的动手能力，把你的设想实现。每一次对问题的求解总是要思索，思索后便是具体的实现过程，通过多方面的查找，多次实践后，把自己的好的想法证明。 这就是我们技术的一种好的成就。所以，实验课的学习是非常重要的， 在每一个的 debug 中找寻自己的错误，并纠正自己的错误，然而一步步完善。似乎这就是一种人生观的体现，学习就如生活中的事一样。发现问题，解决问题，这

6、个过程会有很多收获。六、附：源程序1、实验一源程序/*/ /* 算法设计一/*实 现 ： 从 文 件 中 读 取 图 信 息 ， 然 后 用bfs 求 两 节 点 之 间 的 路 径*/ /*author ：刘勇/* 完成时间： 2010-01-3 /*/ #include stdafx.h #include #include #include #include using namespace std; #define max_vertex_num 50 /定义最大顶点数#define maxqsize 100 /定义最大队列长度typedef int vertextype; int adjm

7、atrixmax_vertex_nummax_vertex_num; typedef struct sqqueue / 定义辅助队列 vertextype *base; int front; /定义首尾指针int rear; sqqueue; /*/ /* 函数声明部分*/ /*/ void creategraph(int &max); void printgraph(int max); void shortpath(vertextype s,vertextype d,int maxvertex); /*/ /* 建图：从 文件中读 入 图的信息 。图 存于graph.txt文档中*/

8、 /*/ void creategraph(int &max) int i = 0; file *fp; char buffmax_vertex_num; if (fp= fopen(f:graph.txt,r) = null) printf(connot open the file !n); exit(0); do buffi = fgetc(fp); /从文件读取存入字符数组 buff中； while (buffi+ != eof); fclose(fp); for (int h=0;hmax_vertex_num;h+) /初始化邻接矩阵； for (int l=0;lmax_v

9、ertex_num;l+) adjmatrixhl = 0; for (int j=0;ji;j=j+4) if (isdigit(buffj)&isdigit(buffj+2) int temp1 = buffj-48; int temp2 = buffj+2-48; int ma; if (maxtemp2?temp1:temp2) max = ma; /couttemp1-temp2endl; adjmatrixtemp1temp2 = 1; adjmatrixtemp2temp1 = 1; cout 邻接矩阵： endl; for (int k=1;k=max;k+) for

10、(int n=1;n=max;n+) coutadjmatrixkn ; coutendl; /*/ /* 输出图：以邻接表形式输出图信息*/ /*/ void printgraph(int max) cout 邻接表： endl; for (int i=1;i=max;i+) coutvertex i-; for (int j=1;j=max;j+) if (adjmatrixij = 1) coutj,; coutd 的 最 短 路 径 并 且 顺 序 输 出 顶 点*/ /*/ int initqueue(sqqueue &q) / 初始化队 q.base=(vertextype

11、 *)malloc(maxqsize*sizeof(vertextype); if(!q.base) / 申请空间 printf(申请失败 !); return 0; q.front=q.rear=0; / 初始化队指针return 1; /initqueue() end int enqueue(sqqueue &q,vertextype e) / 进队 if(q.rear+1)%maxqsize=q.front) / 队头等于队尾时, 队满 printf(errer ! the sqqeueu is full ! ); return 0; q.baseq.rear=e; q.rear

12、=(q.rear+1)%maxqsize; return 1; /enqueue() end int queueempty(sqqueue q) / 队空 if(q.front=q.rear) return 1; else return 0; /queueempty() end int dequeue(sqqueue &q,vertextype &e) / 出队 if(q.front=q.rear) / 队空 printf(errer ! its empty!); return 0; e=q.baseq.front; q.front=(q.front+1)%maxqsize;

13、return e; /dequeue() end /int firstadjver(int adjmatrix,vertextype v) / / / void shortpath(vertextype s,vertextype d,int maxvertex) int v,u,w; int visitedmax_vertex_num; int pathlen =0; int pathmax_vertex_num; sqqueue q; sqqueue p; for(v=1;v=maxvertex;v+) visitedv=0; / 初始化访问标记 initqueue(q); /初始化辅助队列

14、 for (v=s;v ,v); pathlen +; enqueue(q,v); /enqueue(p,v); / int i = 1; while (!queueempty(q) dequeue(q,u); for (int i=1;i,w); /*if (w=d) return; */ enqueue(q,w); pathlen +; cout3 路径长度 :pathlen-1endl; /*/ /* 主函数*/ /*/ int main() int tempmax; creategraph(tempmax); /couttempmax :tempmaxendl; printgraph(

15、tempmax); shortpath(2,3,tempmax); return 0; 2、实验二源程序#include stdafx.h #include #include using namespace std; #define max_vertex_num 20 typedef struct int weight; adj,adjmatrixmax_vertex_nummax_vertex_num; typedef struct adjmatrix arc; int vexnum; mgraph; /*/ /*创建图，以邻接矩阵存储*/ /*/ void createmgraph(mgr

16、aph &m) coutm.vexnum; cout 请输入该图的邻接矩阵:endl; for(int i=1;i=m.vexnum;i+) for(int j=1;jm.arcij.weight; void print(mgraph m) for(int i=1;i=m.vexnum;i+) for(int j=1;j=m.vexnum;j+) coutm.arcij.weight ; coutendl; /*/ /* 应用dfs 思想判断图是否连通*/ /*/ bool connectivity_dfs(mgraph m) queue q; bool visamax_vertex_

17、num;/之前先初始化为false ；int count=0; memset(visa,0,sizeof(visa); q.push(1); while(!q.empty() int v=q.front(); visav=true; q.pop(); count+; for(int i=1;i=m.vexnum;i+)/把与 v 连通并且没有被访问过的结点压进队列面 if(m.arcvi.weight) if(!visai) q.push(i); visai=true;/标志被访问过。 if(count=m.vexnum)/如果压进栈的结点个数刚好等于总结点的个数，则连通；return tru

18、e; return false; /*/ /* 判断一个图是否有环*/ /*/ bool cycle_dfs(mgraph m) mgraph judgemat; judgemat.vexnum=m.vexnum; int i,j; for(i=1;i=m.vexnum;i+) for(j=1;j=m.vexnum;j+) if(m.arcij.weight) judgemat.arcij.weight=1; /初始化判断矩阵else judgemat.arcij.weight=0; judgemat.arcii.weight=1; for(int x=1;x=judgemat.vexnum;

19、x+) /采用 warshall算法判断图的连通性。注意下标。 for(int y=1;y=judgemat.vexnum;y+) if(judgemat.arcxy.weight) for(int z=1;z=judgemat.vexnum;z+) if(judgemat.arczx.weight) judgemat.arczy.weight=1; /print(judgemat); for(i=1;i=judgemat.vexnum;i+) for(j=1;j=judgemat.vexnum;j+) if(!judgemat.arcij.weight)/只要还没全为1 就不连通；retur

20、n false; return true; /*/ /* 主程序部分，入口*/ /*/ int main() mgraph map; createmgraph(map); coutuse dfs:endl; if(connectivity_dfs(map) coutconnectivity!endl; else coutnot connectivity!endl; if(!cycle_dfs(map) coutcycle endl; else coutno cycleendl; return 0; 3、实验三源程序（1）n-queens #include #include bool place

21、(int x,int k) /考察皇后k 放置在 xk 列是否发生冲突 int i; for (i=1; ik; i+) if (xk=xi|abs(k-i)=abs(xk-xi) return 0; return 1; void output(int n,int x) cout; for(int i=1;in;i+) coutxi,; coutxnendl; return; void queue(int n,int x) int i; for (i=1;i=1) xk=xk+1; /在下一列放置第k 个皇后while (xk=n & !place(x,k) xk=xk+1; /搜索下

22、一列if (xk=n & k=n) /得到一个解，输出output(n,x); num+; else if (xk=n & kn) k=k+1; /放置下一个皇后else xk=0; /重置 xk ，回溯k=k-1; int main(int argc, char *argv) coutn; int *x=new intn; x0=0; queue(n,x); return 0; （2）m-coloring #include using namespace std; / 判断对顶点k 着色以后是否合法着色bool ok(int x, int k, bool c55, int n) int i; for(i = 0; i k; i+) if(cki & xk = xi) / 第 k 个顶点与某个相邻的顶点有颜色冲突 return false; re