5深度优先算法.docVIP

计算机算法的设计与分析实验报告 ——深度优先遍历 算法 基本思路 ?1、在每个阶段的决策时，采取能深则深的原则试探所有可行的方案，一旦深入一层则保存当前操作引起的状态。 ?2、一旦试探失败，为了摆脱当前失败状态，采取回到上一阶段尝试下一方案的策略（回溯策略）；或者在求解所有解时，求得一个解后，回溯到上一阶段尝试下一方案，以求解下一个解。 ?3、在各个阶段尝试方案时，采取的是穷举的思想。 代码 #include stdafx.h #includeiostream.h//构造有向图p162 #includestring.h #includeiomanip.h #define INFINITY 10000//最大值,无穷 #define MAX_VERTEX_NUM 20//最大顶点个数,即可以计算的最大规模 typedef struct ArcCell { float adj;//无权图为1或0,有权图为权重 char info[30];//该弧相关信息 }ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { char vexs[MAX_VERTEX_NUM][20];//顶点向量,如v1,v2,...等 AdjMatrix arcs; int vexnum,arcnum; }MGraph; //char temp[100][20];//作成全局变量 int LocateVex(MGraph G,char *v) { int i,num=-1; for(i=0;iG.vexnum;i++) { if(strcmp(v,G.vexs[i])==0)//相等时为0,大于为正,小于为负 { num=i; break; } } if(num0) { cout没有匹配的顶点,输入错误!endl; return -1; } else return num; } void CreateNet(MGraph G) { int i,j,k,s=0; int IncInfo=-1;//IncInfo为0则各弧不含其它信息,有信息则为其他数字 char v[2][20];//存放一条边的两个顶点 char *p; float w;//输入的权重 int direct=-1;//有向图为1,无向图为其他数字 //char temp[100][20];//这个temp不能放到本函数内,or,G.vexs[i]引用他时,赋了值,跳出这个函数就没有值.这样不好 //scanf(G.vexnum,G.arcnum,IncInfo); cout构建有向图请输入数字1,构建无向图请输入其他数字(无向图请输入上三角的边).endl; cindirect; cout各顶点无信息则输入数字0,有信息输入其他数字.endl; cinIncInfo; cout请输入顶点和弧数目:endl; cinG.vexnumG.arcnum; cout请输入G.vexnum个顶点的符号,如v1,v2...endl; for(i=0;iG.vexnum;++i) { p=G.vexs[i]; cinp;//注意vexs[MAX_VERTEX_NUM]中的MAX_VERTEX_NUM大于G.vexnum } for(i=0;iG.vexnum;i++) { coutG.vexs[i] ; } for(i=0;iG.vexnum;++i) { for(j=0;jG.vexnum;++j) { G.arcs[i][j].adj=INFINITY; p=G.arcs[i][j].info; p=\0;///////////////////////////////问题 } } for(k=0;kG.arcnum;++k)//循环弧的次数 { cout第k+1次输入:endl; cout出发点:; p=v[0]; cinp; i=LocateVex(G,p); cout接受点:; p=v[1]; cinp; j=LocateVex(G,p); cout权重:; cinw;//输入格式: v1 v2 18 couti=i j=jendl; G.arcs[i][j].adj=w; if(IncInfo) { cout输入信息:; p=G.arcs[i][j].info; cinp; } if(direct!=1) G.arcs[j][i]=G.arcs[i][j]; }