算法设计与分析实验报告

1、算法设计与分析实验报告指导老师：沙莎学院：信息科学与工程学院班 级：计科0508姓名：戚婕学号：10完成日期：2007 年 12月实验一分治法 21.1 实验要求 21.2 实验内容 21.3 核心算法 21.4 程序代码 41.5 实验结果 8实验二贪心法 102.1 实验要求 102.2 实验内容 102.3 核心算法 102.4 程序代码 122.5 实验结果 18实验三动态规划 203.1 实验要求 203.2 实验内容 203.3 核心算法 203.4 程序代码 213.5 实验结果 24实验四深度优先搜索 264.1 实验要求 264.2 实验内容 264.3 核心算法 264.4

2、 程序代码 274.5 实验结果 28实验五回溯法 305.1 实验要求 305.2 实验内容 305.3 核心算法 305.4 程序代码 315.5 实验结果 3335实验一 分治法. 实验要求1. 了解用分治法求解的问题：当要求解一个输入规模为n,且n的取值相当大的问题时，如果问题可以分成k个不同子集合，得到k个不同的可独立求解的子问题，其中 1<kwn,而 且子问题与原问题性质相同，原问题的解可由这些子问题的解合并得出。那末，对于这类问题分治法是十分有效的。2. 掌握分治法的一般控制流程。DanC(p,q)global n ， A1:n; integer m,p,q; / 1 p

3、q nif Small(p,q) then return G(p,q);else m=Divide(p,q); / p m<qreturn Combine(DanC(p,m),DanC(m+1,q); endifend DanC3实现典型的分治算法的编程与上机实验，验证算法的时间复杂性函数。. 实验内容1. 编程实现归并排序算法和快速排序算法，程序中加入比较次数的计数功能，输出排序结果和比较次数。2. 输入10组相同的数据，验证排序结果和完成排序的比较次数。3. 与复杂性函数所计算的比较次数比较。4. 用表格列出比较结果。5. 给出文字分析。. 程序算法1. 归并排序算法procedur

4、e MERGESORT(low， high)/A(low ； high) 是一个全程数组，它含有high-low+1 R0个待排序的元素/integer low ， high ；if low<high ；then mid ,call MERGESORT(low，call MERGESORT(mid+1 call MERGE(low ， mid，/ 求这个集合的分割点/mid) / 将一个子集合排序/， high) / 将另一个子集合排序high) / 归并两个已排序的子集合/endifend MERGESORT归并两个已排序的集合procedure MERGE(low ， mid， hi

5、gh)/A(low ： high) 是一个全程数组/ 辅助数组B(low ； high)/integer h ， i ， j ， k；h low ; i low ; j mid+1 ;while h < mid and j < high do /当两个集合都没取尽时 /if A(h) < A(j) then B(i) - A(h) ； h-h+1else B(i)-A(j) ; j -j+1endifi -i+1repeatif h>mid thenfor k j to high do /处理剩余的元素 B(i)-A(k) ; i -i+1repeatelse for

6、k h to mid doB(i)-A(k) ; i -i+1repeatendif将已归并的集合复制到Aend MERGE2. 快速排序算法QuickSort(p,q)/ 将数组A1:n 中的元素Ap, Ap+1, Aq 按不降次序排列，并假定An+1 是一个确定的、且大于 一个确定的、且大于A1:n 中所有的数。/int p,q; global n, A1:n;if p<q thenj=Partition(p, q+1); /划分后 j 成为划分元素的位置QuickSort(p,j-1);QuickSort(j+1,q);endifend QuickSortprocedure PAR

7、TITION(m ， p)/ 退出过程时，p带着划分元素所在的下标位置。/integer m ， p， i ； global A(m ： p-1)v A(m); i m /A(m)是划分元素 /loop由左向右移/和 A(p) 换位 /loop i i+1 until A(i) > v repeat /iloop p p-1 until A(p) < v repeat p if i<pthen call INTERCHANGE(A(i) ， A(p) /A(i) else exitendifrepeatA(m) -A(p) ； A(p) -v / 划分元素在位置 p/ End

8、 PARTITION. 程序代码1. 归并排序#include<iostream.h>#include<iomanip.h>#include<stdlib.h>#include<time.h>#define M 11typedef int KeyType;typedef int ElemType;struct recKeyType key;ElemType data;typedef rec sqlistM;class guibingpublic:guibing(sqlist b)for(int i=0;i<M;i+)ri=bi;void o

9、utput(sqlist r,int n)for(int i=0;i<n;i+)cout<<setw(4)<<ri.key;cout<<endl;void xuanze(sqlist b,int m,int n)int i,j,k;for(i=m;i<n-1;i+)k=i;for(j=i;j<n;j+)if(bk.key>bj.key) k=j; if(k!=i)rec temp=bk;bk=bi;bi=temp;void merge(int l,int m,int h,sqlist r2)xuanze(r,l,m);xuanze(r

10、,m,h);output(r,M);int i,j,k;k=i=l;for(j=m;i<m&&j<h;k+)if(ri.key<=rj.key)r2k=ri;i+;elser2k=rj;j+;output(r2,M);while(j<h)r2k=rj;j+;k+;while(i<=m)r2k=ri;i+;k+;output(r2,M);private:sqlist r;void main()cout<<"guibingfa1 运行结果:n"sqlist a,b;int i,j=0,k=M/2,n=M;srand(ti

11、me(0);for(i=0;i<M;i+)ai.key=rand()%80;bi.key=0;guibing gx(a);cout<<" 排序前数组:n"gx.output(a,M);cout<<" 数组排序过程演示:n"gx.merge(j,k,n,b);cout<<" 排序后数组:n"gx.output(b,M);cin.get();2. 快速排序#include<iostream.h>#include<iomanip.h>#include<stdlib.h&

12、gt;#include<time.h>#define MAXI 10 typedef int KeyType; typedef int ElemType; struct recKeyType key;ElemType data;typedef rec sqlistMAXI; class kuaisupublic:kuaisu(sqlist a,int m):n(m)for(int i=0;i<n;i+) bi=ai;void quicksort(int s,int t) int i;if(s<t)i=part(s,t);quicksort(s,i-1);quicksor

13、t(i+1,t);else return;int part(int s,int t)int i,j;rec p;i=s;j=t;p=bs;while(i<j)while(i<j&&bj.key>=p.key)j-; bi=bj;while(i<j&&bi.key<=p.key)i+;bj=bi;bi=p;output();return i;void output()for(int i=0;i<n;i+)cout<<setw(4)<<bi.key;cout<<endl;private:sqli

14、st b;int n;void main()cout<<"kuaisu1.cpp 运行结果:n"sqlist a1;int i,n=MAXI,low=0,high=9;srand(time(0);for(i=0;i<n;i+)a1i.key=rand()%80;kuaisu px(a1,n);cout<<" 数组排序过程演示:n"px.quicksort(low,high);cout<<" 排序后数组:n"px.output();cin.get();五 . 实验结果1. 归并排序2.快速排序7

15、:1算法实验'分治法11）已1111£：。11£¥11£&1. exe22 2239 41 EEuaisul _ c: 口口贬仃名言果二 晅排.弱密寅示二39 22 22 41 6339393922 2222 22E序后数咀414141417777636363635656三6777777777?实验二贪心法一 . 实验要求1. 优化问题有n输入，而它的解就由这n个输入满足某些事先给定的约束条件的某个子集组成，而把满足约束条件的子集称为该问题的可行解。可行解一般来说是不唯一的。那些 使目标函数取极值( 极大或极小) 的可行解，称为最优解。2

16、. 贪心法求优化问题算法思想：在贪心算法中采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策(在一定的标准下)。决策一旦作出，就不可再更改。作出贪心决策的依据称为贪心准则(greedy criterion )。3. 一般方法1)根据题意，选取一种量度标准。2)按这种量度标准对这n个输入排序3)依次选择输入量加入部分解中。如果当前这个输入量的加入，不满足约束条件，则 不把此输入加到这部分解中。procedure GREEDY(A， n) /* 贪心法一般控制流程*/A(1: n)包含n个输入/solutions -()/ 将解向量solution 初始化为空/ for i 1 to

17、 n do x SELECT(A) if FEASIBLE(solution ， x) then solutions UNION(solution , x) endif repeat return(solution) end GREEDY 4. 实现典型的贪心算法的编程与上机实验，验证算法的时间复杂性函数。二 . 实验内容1. 编程实现背包问题贪心算法和最小生成树prim 算法。 通过具体算法理解如何通过局部最优实现全局最优，并验证算法的时间复杂性。2. 输入5个的图的邻接矩阵，程序加入统计prim 算法访问图的节点数和边数的语句。3. 将统计数与复杂性函数所计算的比较次数比较，用表格列出比较

18、结果，给出文字分析。三 . 程序算法1. 背包问题的贪心算法procedure KNAPSACK(P ， W， M， X， n)/P(1： n) 和 W(1； n) 分别含有按P(i)/W(i) RP(i+1)/W(i+1) 排序的n件物品的效益值和重量。M是背包的容量大小，而 x(1 ： n)是解向量real P(1： n) ， W(1： n) ， X(1 ： n)， M， cu；integer i ， n；X- 0 /将解向量初始化为零cu M /cu是背包剩余容量for i 1 to n doif W(i)>cu then exit endifX(i) - 1cu cu-W(i)r

19、epeatif i < n then X(i) - cu/ W(i)endifend GREEDY-KNAPSACKprocedure prim(G,)status unseen"/ Tstatus1 tree node ” for each edge(1,w) do statusw fringe ” dadw -1;wdistw weight(1,w) repeatwhile statust 丰 tree node ” pick a fringe u with min distw / statusu tree node ” for each edge(u,w) do修改林口T

20、的关系 repeatrepeat为空/将 1 放入 T/找到T的邻接点通过1与Tt立联系/w到T勺距离do选取到T最近的节点2. Prim 算法PrimMST(G， T， r)/求图G勺以r为根的MST结果放在T=(U, TE)中InitCandidateSet( )；初始化：设置初始的轻边候选集，并置 T=(r , 0) for(k=0 ; k<n-1 ; k+)/ 求 T白n-1 条树边(u , v尸SelectLiShtEdge()；/ 选取车5边(u , v);T-TU (u , v) ; /扩充T,即(u, v)涂红加入TE,蓝点v并人红点集UModifyCandidateSe

21、t( )；/根据新红点v调整候选轻边集 . 程序代码1. 背包问题贪心算法#include <iostream.h>struct goodinfofloat p; /物品效益float w; /物品重量float X; /物品该放的数量int flag; / 物品编号;/ 物品信息结构体void Insertionsort(goodinfo goods,int n)int j,i;for(j=2;j<=n;j+)goods0=goodsj;i=j-1;while (goods0.p>goodsi.p)goodsi+1=goodsi;i-;goodsi+1=goods0;

22、/ 按物品效益，重量比值做升序排列void bag(goodinfo goods,float M,int n)float cu;int i,j;for(i=1;i<=n;i+)goodsi.X=0;cu=M; / 背包剩余容量for(i=1;i<n;i+)当该物品重量大与剩余容量跳出if(goodsi.w>cu)/break;goodsi.X=1;cu=cu-goodsi.w;/ 确定背包新的剩余容量if(i<=n)goodsi.X=cu/goodsi.w;/ 该物品所要放的量for(j=2;j<=n;j+)goods0=goodsj;i=j-1;while (g

23、oods0.flag<goodsi.flag)goodsi+1=goodsi;i-;goodsi+1=goods0;cout<<" 最优解为:"<<endl;for(i=1;i<=n;i+)cout<<" 第 "<<i<<" 件物品要放:"cout<<goodsi.X<<endl;void main()cout<<"| 运用贪心法解背包问题|"<<endl;cout<<"|&

24、quot;<<endl;int j;int n;float M;goodinfo *goods;/ 定义一个指针while(j) cout<<" 请输入物品的总数量： cin>>n;goods=new struct goodinfo n+1;/cout<<" 请输入背包的最大容量："cin>>M;cout<<endl;int i;for(i=1;i<=n;i+) goodsi.flag=i;cout<<" 请输入第"<<i<<&qu

25、ot; 件物品的重量:"cin>>goodsi.w;cout<<" 请输入第"<<i<<" 件物品的效益:"cin>>goodsi.p;goodsi.p=goodsi.p/goodsi.w;/得出物品的效益，重量比cout<<endl;Insertionsort(goods,n);bag(goods,M,n);cout<<"press <1> to run agian"<<endl;cout<<"

26、press <0> to exit"<<endl;cin>>j;2. Prim 算法#include <stdio.h>#include <stdlib.h>#include <iostream.h>#define INFINITY INT_MAX#define MAX_VERTEX_NUM 20typedef int VRType;typedef int InfoType;typedef char VerTexType;typedef struct ArcCellVRType adj;InfoType *inf

27、o;ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef structVerTexType vexsMAX_VERTEX_NUM;AdjMatrix arcs;int vexnum, arcnum;MGraph;typedef structVerTexType adjvex;VRType lowcost;closedgeMAX_VERTEX_NUM;void CreateGraph(MGraph &G);void MiniSpanTree_PRIM(MGraph G, VerTexType u);int LocateVex(MGr

28、aph G, VerTexType u);int minimum(closedge close);void main( void )int i, j;MGraph G;CreateGraph(G);for(i = 0; i < G.vexnum; i+)for(j = 0; j < G.vexnum; j+)cout<<G.arcsij.adj;cout<<" "cout<<endl;MiniSpanTree_PRIM(G, 'a');void CreateGraph(MGraph &G)int wei

29、gh;int i, j = 0, k = 0;char hand, tide;cout<<"input the number for vexnum and arcnum:"cin>>G.vexnum>>G.arcnum;for(i = 0; i < G.vexnum; i+)for(j = 0; j < G.vexnum; j+)G.arcsij.adj = 88;cout<<endl;cout<<"input"<<G.vexnum<<"char f

30、or vexs:"for(i=0; i < G.vexnum; i+)cin>>G.vexsi;cout<<endl;cout<<"input"<<G.arcnum<<"arc(char,char,weigh):"<<endl;j = 0;k = 0;for(i=0; i < G.arcnum; i+)cout<<i<<":"cin>>hand;cin>>tide;cin>>weig

31、h;while (hand != G.vexsj) j+;while (tide != G.vexsk) k+;G.arcsjk.adj = weigh;G.arcskj.adj = weigh;j = 0;k = 0;cout<<endl;void MiniSpanTree_PRIM(MGraph G,VerTexType u) int i, j, k = 0;closedge close;k = LocateVex ( G, u );for ( j = 0; j < G.vexnum; j+ )if (j != k)closej.adjvex = G.vexsk;clos

32、ej.lowcost = G.arcskj.adj;closej.lowcost = 88;closej.adjvex = '0'closek.lowcost = 0;closek.adjvex = u;for (i = 1; i < G.vexnum; i+)k = minimum(close);cout<<closek.adjvex;cout<<">"cout<<G.vexsk<<" "cout<<closek.lowcost<<endl;closek

33、.lowcost = 0;for (j=0; j<G.vexnum; j+)if (G.arcskj.adj < closej.lowcost)closej.adjvex = G.vexsk;closej.lowcost = G.arcskj.adj;int LocateVex(MGraph G, VerTexType u)int k = 0;while(G.vexsk+ = u)return k-1;return 0;int minimum(closedge close)int j1=0, client = 88, j2;while(closej1.adjvex != '

34、0')if (client > closej1.lowcost && closej1.lowcost != 0)client = closej1.lowcost;j2 = jl；j1+;return j2;五.实验结果1 .背包问题贪心算法武 丁:、算法实验、俞，“法UebuG。nezel运市三星蟀普苞荷壬:优焉连:号噩糖然要要要要要七t 乐品品品品品1>0> j勿勿勿勿勿< <卜久物品的总数量！ 5卜人背包的最大容量 20请揄入篁1件物品的重量二14 请输入第1忤枷品的效益;8请输入第2件物品的重量门 请输入第2件物品的效益：66人第5件

35、物品的重量X ii入畲5件病品的效益;9=0=1 ：0,75：1 run agian exit2. Prim算法实验三动态规划一 . 实验要求1. 理解最优子结构的问题。有一类问题的活动过程可以分成若干个阶段，而且在任一阶段后的行为依赖于该阶段的状态， 与该阶段之前的过程如何达到这种状态的方式无关。这类问题的解决是多阶段的决策过程。在50年代，贝尔曼(Richard Bellman )等人提出了解决这类问题的“最优化原理”，从而创建了最优化问题的一种新的算法设计方法动态规划。对于一个多阶段过程问题，是否可以分段实现最优决策，依赖于该问题是否有最优子结构性质，能否采用动态规划的方法，还要看该问题

36、的子问题是否具有重叠性质。最优子结构性质：原问题的最优解包含了其子问题的最优解。子问题重叠性质：每次产生的子问题并不总是新问题，有些子问题被反复计算多次。问题的最优子结构性质和子问题重叠性质是采用动态规划算法的两个基本要素。2. 理解分段决策Bellman 方程。每一点最优都是上一点最优加上这段长度。即当前最优只与上一步有关。us 0,u j minuiwij .us初始值，Uj第j段的最优值。3. 一般方法1) 找出最优解的性质，并刻画其结构特征；2) 递归地定义最优值(写出动态规划方程)；3) 以自底向上的方式计算出最优值；4) 根据计算最优值时得到的信息，构造一个最优解。步骤 1-3 是

37、动态规划算法的基本步骤。在只需要求出最优值的情形，步骤 4可以省略，步骤3中记录的信息也较少；若需要求出问题的一个最优解，则必须执行步骤4，步骤 3中记录的信息必须足够多以便构造最优解。二 . 实验内容1. 编程实现多段图的最短路径问题的动态规划算法。2. 图的数据结构采用邻接表。3. 要求用文件装入5个多段图数据，编写从文件到邻接表的函数。4. 验证算法的时间复杂性。三 . 核心算法多段图算法procedure FGRAPH（E， k， n， P）/ 输入是按段的顺序给结点编号的，有n 个结点的k段图。既边集，c(i , j)是边<i,j>的成本。P(1： k) 是最小成本路径。

38、/real COST(n)， integerD(n 一 1) ， P(k) ， r ， j ， k， nCOST(n) - 0for j n-1to 1 by1do / 计算 COST(j)设r是一个这样的结点，(j , r) E且使c(j , r)+COST(r)取最小值 COST(j)-c(j , r)+COST(r)D(j)-rrepeat / 向前对 j-1 进行决策/P(1)-1; P(k) -n;for j -2 to k-1 do /找路径上的第j个节点P(j) -D ( P(j-1)repeatend FGRAPH. 程序代码多段图问题#include<stdio.h&g

39、t;#include<conio.h>#include<malloc.h>#define MAX_VERTEX_NUM 50typedef struct ArcNodeint adjvex; /该弧所指向的顶点的位置int value; /该结点与邻接结点间的代价struct ArcNode *nextarc; / 指向下一条弧的指针ArcNode, *node;typedef struct VNodeint data; / 顶点信息ArcNode *firstArc; / 指向第一条依附该顶点的弧的指针VNode, AdjListMAX_VERTEX_NUM;type

40、def struct GraphAdjList vertices;int vexnum,arcnum; / 图的当前顶点数和弧数*ALGraph;int build_adList(ALGraph G,int n,int a) / 建立邻接表int v, m, i, t, h;node p, q;if(n < 0) return printf("ERROR");G->vexnum = n; / 图的顶点数if(a < 0) return printf("ERROR");G->arcnum = a; / 图的弧数for(m = 0;

41、m < n; m+)G->verticesm.data = m;G->verticesm.firstArc = NULL;for(m = 1; m <= a; m+)i = 1;printf(" 输入第原弧：",m);scanf("%d,%d,%d",&t,&h,&v);p = (ArcNode*)malloc(sizeof(ArcNode);p->adjvex = h;p->value = v;p->nextarc = NULL;while(G->verticesi.data !=

42、 t) i+; /转到下一个结点if(!G->verticesi.firstArc) /终点G->verticesi.firstArc = p;else / 若当前结点有后继节点则后移for(q = G->verticesi.firstArc; q->nextarc; q = q->nextarc); q->nextarc = p; / 新开辟结点return v;void print_Graph(ALGraph G) / 打印邻接表ArcNode *p=(ArcNode *)malloc(sizeof(ArcNode);int i;for(i = 1; i

43、 < G->vexnum; i+)p = G->verticesi.firstArc;printf("%d",i);while(p)printf("->%d,%d",p->adjvex,p->value);/第 i 个结点的邻接结点信息p = p->nextarc; printf("n");void fgraph(ALGraph G ,int k,int n)/多段图ALGraph G, n为结点数，k为图的段数/ 输入是按段的顺序给结点编号int cost100;int d100;int p

44、ath100;int j, r, i, min, w, value;node p;costn = 0;for(j = n - 1; j >= 1; j-) /向前处理结点p = G->verticesj.firstArc;min = p->value+costp->adjvex; / 初始化路径最小代价r = p->adjvex;value = p->value;while(p != NULL) /r 是一个的这样的结点，权值c(j,r)+costr 取最小值if(p->value + costp->adjvex) < min) min =

45、 p->value + costp->adjvex; /p->value=c(j,r) r = p->adjvex;value = p->value; p = p->nextarc;当前节点的代价值costj = value + costr; / dj = r; / 决策阶段，各结点到终点最小代价路径上前方顶点的编号path1 = 1; pathk = n;for(i = 2; i <= k - 1; i+) /找出最小代价路径上的结点pathi = dpathi - 1;printf(" 最小成本为:%dn",cost1);pri

46、ntf(" 最小成本路径为: ");for(w = 1; w <= k; w+)printf("%d->", pathw);void main()ALGraph g;int n,a,k;g = (ALGraph)malloc(sizeof(ALGraph);printf(" 请输入多段图节点数目:");scanf("%d", &n);printf(" 请输入多段图边的数目:");scanf("%d", &a);printf(" 请输入多段

47、图的段数:");scanf("%d", &k);printf(" 输入多段图的弧的信息(弧头，弧尾，权值)n");build_adList(g, n, a);printf(" 多段图的邻接表为:n");print_Graph(g);fgraph(g, k, n);getch();五 . 实验结果多段图问题7："算法实蛙'动态性划Debug多段图实现.eze博物入多燧图节点数目：5请扁人多窗图边的数目;6考购入多段图的第数4对人叁露的邨黄信息Y弧头，弧尾，极值）初入第1条弧：1J,4施入第2条孤小3,

48、51£舸入第3卷如,评评 腌入篁4条弧Z5.6 输入霓5条邨：3*g 输入第6条期45,5 多段图的邻接表为: 1->2,4->3,5->4,«21一）5.63 3->5,104175,5袁小成本为其鸟彭卜成本路径为:实验四 深度优先搜索. 实验要求1 理解深度优先搜索策略：深度优先搜索策略是尽可能“深 ”地搜索图。在深度优先搜索中，对于最新发现的顶点v,如果边(v,w)是还未探测的边，则沿(v,w)继续搜索下去。当所有的边 (v,w)都己被探寻过，搜索将回溯到发现结点v的顶点。这一过程一直进行到回到源点为止。如果还存在未被发现的顶点，则选择其中一个

49、作为源结点并重复以上过程，整个进程反复进行直到所有结点都被发现为止。2 理解深度优先搜索过程中顶点的三种状态：还未到达的顶点，当前路径上经过的顶点，深度优先在搜索过程中也为结点着色以表示结点的状态。每个顶点开始均为白色，搜索中被发现时置为灰色，当其邻接表被完全检索之后又被置成黑色。. 实验内容1 编程实现深度优先搜索算法。2 修改算法使之可以找出图的所有树。3 修改算法使之可以判断图是否为一棵树。4 修改算法使之可以判断图是否存在一个环。. 核心算法procedure DFS(G);for每个顶点u C G docoloru . White;repeatfor 每个顶点u C G doif c

50、oloru=Whitethen DFS_Visit(G,u);end;procedure DFS_Visit(u);coloru Gray;for (u,w) C E do /探寻边(u,w)if colorw=Whitethen DFS_Visit(w);repeatcol oru Black;/完成后置u为黑色end;四 . 程序代码#include<iostream.h>#define MAX 50 / 能够处理的最多顶点数char colorMAX; / 保存每个点的颜色标记int n,AMAXMAX; / 顶点数和矩阵int loop=0; /标记环并记录其个数int t

51、ree=0; /标记树并记录其个数void DFS(int i)int k;colori='G' /已访问顶点记为灰色for(k=1;k<=n;k+)if(Aik=1)if(colork='G'|colork='B') /当该点的邻接点中有已被访问的点时存在环loop+;if(colork='W') DFS(k); / 访问邻接点中一个没有被访问的点colori='B' / 当点为死结点时记为黑色void main()int i,j,k,m;cout<<" 请输入总顶点数：n"

52、cin>>n;cout<<" 请输入总边数：n"cin>>m;for(i=1;i<=n;i+)for(j=1;j<=n;j+)Aij=0; / 将矩阵初始化为0colori='W' / 所有顶点颜色初始化为白色for(k=1;k<=m;k+)cout<<"请输入其始点："；cin>>i; cout<<"请输入指向的点："cin>>j; Aij=1; /有边的赋值为1) for(i=1;i<=n;i+) (if(c

53、olori='W') DFS(i);)for(i=1;i<=n;i+)for(j=1;j<n;j+)(if(!(Aij&&Aji) tree+;)if(loop=0)(cout<<"该图中无环!"<<endl;if(m=n-1)cout<<"该图为一棵树!"<<endl;)else(cout<<"该图中共有"<<loop<<"个环!"<<endl; cout<<&q

54、uot;该图不是一棵树!"<<endl;)五.实验结果门"F门算秩实验工厚度优先掳索IMbsn利环.fiie顶点数最continue请输入总边数:! a- s = s = 1- * t =1点:1点=1点:2点=3点=4点问树 y 点的点的点的点的点的点的讨棉标始向始向始向始间始问始向有其指其指其指其指其指卷共是an入入入 入入入入入入入入入中不主星IH直篇4fet皇里 * -L- * IF V ml Tr ¥ TP Tr V -实验五 回溯法一 . 实验要求1. 理解可用回溯法求解的问题问题碰常要能表达为对已知的、由n元组(x1 ,，xn)组成的状态空间E=(x1 ,xn)| xi Si,i=1,2, n,给定关于n元组中的分量的一个约束集D,求才足D的全部约束条件的所有n元组。Si是xi的定义域且Si是有穷集，称E中满足D的全部约束条件的 所有n元组为问题P的一个解。2. 理解回溯法的基本思想回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在