文档介绍:计算机算法的设计与分析实验报告
——深度优先遍历
算法
基本思路
n1、在每个阶段的决策时,采取能深则深的原则试探所有可行的方案,一旦深入一层则保存当前操作引起的状态。
n2、一旦试探失败,为了摆脱当前失败状态,采取回到上一阶段尝试下一方案的策略(回溯策略);或者在求解所有解时,求得一个解后,回溯到上一阶段尝试下一方案,以求解下一个解。
n3、在各个阶段尝试方案时,采取的是穷举的思想。
代码
#include ""
#include<>//构造有向图p162
#include<>
#include<>
#define INFINITY 10000//最大值,无穷
#define MAX_VERTEX_NUM 20//最大顶点个数,即可以计算的最大规模
typedef struct ell
{
float adj;//无权图为1或0,有权图为权重
char info[30];//该弧相关信息
}ell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
char vexs[MAX_VERTEX_NUM][20];//顶点向量,如v1,v2,...等
AdjMatrix arcs;
int vexnum,um;
}MGraph;
//char temp[100][20];//作成全局变量
int LocateVex(MGraph G,char *v)
{
int i,num=-1;
for(i=0;i<;i++)
{
if(strcmp(v,[i])==0)//相等时为0,大于为正,小于为负
{
num=i;
break;
}
}
if(num<0)
{
cout<<"没有匹配的顶点,输入错误!"<<endl;
return -1;
}
else
return num;
}
void (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,[i]引用他时,赋了值,
//scanf(&,&,&IncInfo);
cout<<"构建有向图请输入数字1,构建无向图请输入其他数字(无向图请输入上三角的边)."<<endl;
cin>>direct;
cout<<"各顶点无信息则输入数字0,有信息输入其他数字."<<endl;
cin>>IncInfo;
cout<<"请输入顶点和弧数目:"<<endl;
cin>>>>;
cout<<"请输入"<<<<"个顶点的符号,如