农夫过河c++程序.doc

《农夫过河c++程序.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、#include#defineMaxNumVertices10//最大顶点数typedefenum{FALSE,TRUE}Boolean;typedefstruct//图的顶点类型{intFarmer,Wolf,Sheep,Veget;}VexType;typedefstruct{intVertexNum,CurrentEdges;//图的当前顶点数和边数VexTypeVerticesList[MaxNumVertices];//顶点向量（代表顶点）intEdge[MaxNumVertices][MaxNumVertices

2、];//邻接矩阵//用于存储图中的边，其矩阵元素个数取决于顶点个数，与边数无关}AdjGraph;//定义图的邻接矩阵存储结构Booleanvisited[MaxNumVertices];//对已访问的顶点进行标记（图的遍历）intpath[MaxNumVertices];//保存DFS搜索到的路径，即与某顶点到下一顶点的路径intlocate(AdjGraph*G,intF,intW,intS,intV)//查找顶点（F，W，S，V）在顶点向量中的位置{inti;for(i=0;iVertexNum;i++){if(G->Vertices

3、List[i].Farmer==F&&G->VerticesList[i].Wolf==W&&G->VerticesList[i].Sheep==S&&G->VerticesList[i].Veget==V)return(i);//返回当前位置}return(-1);//没有找到此顶点}intis_safe(intF,intW,intS,intV)//判断目前的（F，W，S，V）是否安全{if(F!=S&&(W==S

4、

5、S==V))return(0);//当农夫与羊不在一起时，狼与羊或羊与白菜在一起是不安全的else//否则安全return(1);

6、//安全返回1}intis_connected(AdjGraph*G,inti,intj)//判断状态i与状态j之间是否可转换{intk=0;if(G->VerticesList[i].Wolf!=G->VerticesList[j].Wolf)k++;if(G->VerticesList[i].Sheep!=G->VerticesList[j].Sheep)k++;if(G->VerticesList[i].Veget!=G->VerticesList[j].Veget)k++;if(G->VerticesList[i].Farmer!=G->V

7、erticesList[j].Farmer&&k<=1)//以上三个条件不同时满足两个且农夫状态改变时，返回真//也即农夫每次只能带一件东西过桥return(1);elsereturn(0);}voidCreateG(AdjGraph*G){inti,j,F,W,S,V;i=0;for(F=0;F<=1;F++)//生成所有安全的图的顶点for(W=0;W<=1;W++)for(S=0;S<=1;S++)for(V=0;V<=1;V++)if(is_safe(F,W,S,V)){G->VerticesList[i].Farmer=F;G->Vert

8、icesList[i].Wolf=W;G->VerticesList[i].Sheep=S;G->VerticesList[i].Veget=V;i++;}G->VertexNum=i;for(i=0;iVertexNum;i++)//邻接矩阵初始化即建立邻接矩阵for(j=0;jVertexNum;j++)if(is_connected(G,i,j))G->Edge[i][j]=G->Edge[j][i]=1;//状态i与状态j之间可转化，初始化为1，否则为0elseG->Edge[i][j]=G->Edge[j][i]=0;re

9、turn;}voidprint_path(AdjGraph*G,intu,intv)//输出从u到v的简单路径，即顶点序列中不重复出现的路径{intk;k=u;while(k!=v){cout<<"("<VerticesList[k].Farmer<<","<VerticesList[k].Wolf<<","<VerticesList[k].Sheep<<","<VerticesList[k].Veget<<")";cout<VerticesList[k]

10、.Farmer<<","<VerticesList[k].Wolf<<","<VerticesList[k