农夫过河深度遍及c++

本题的状态转换算法依然是对状态空间中所有状态进行深度优先搜索，因为狼、羊和菜不会划船，所以状态转换算法也很简单，不需要象“用三个水桶均分8升水”问题那样要用排列组合的方式确定转换方法（倒水动作），本题一共只有8种固定的状态转换运算（过河动作），分别是： 农夫单独过河； 农夫带狼过河； 农夫带羊过河； 农夫带菜过河； 农夫单独返回； 农夫带狼返回； 农夫带羊返回； 农夫带菜返回.

#include
using namespace std;
#define VertexNum 16 //最大顶点数 
typedef struct  // 图的顶点 
{    
   int farmer; // 农夫
   int wolf; // 狼
   int sheep; // 羊
   int veget; // 白菜
}Vertex; 

typedef struct 
{   
   int vertexNum; // 图的当前顶点数     
   Vertex vertex[VertexNum]; // 顶点向量（代表顶点）    
   bool Edge[VertexNum][VertexNum]; // 邻接矩阵. 用于存储图中的边，其矩阵元素个数取决于顶点个数
}AdjGraph; // 定义图的邻接矩阵存储结构 
  
bool visited[VertexNum] = {false}; // 对已访问的顶点进行标记（图的遍历） 
int retPath[VertexNum] = {-1}; // 保存DFS搜索到的路径 
  
// 查找顶点（F，W，S，V）在顶点向量中的位置 
int locate（AdjGraph *graph int farmer int wolf int sheep int veget）
{
   for （int i = 0; i < graph->vertexNum; i++）        
{
      if （ graph->vertex[i].farmer == farmer && graph->vertex[i].wolf == wolf && graph->vertex[i].sheep == sheep && graph->vertex[i].veget == veget ）
{
   return i; //返回当前位置        
}
}
 
   return -1;  //没有找到此顶点 
}  

// 判断目前的（F，W，S，V）是否安全 
bool isSafe（int farmer int wolf int sheep int veget） 
{     
//当农夫与羊不在一起时，狼与羊或羊与白菜在一起是不安全的
   if （ farmer != sheep && （wolf == sheep || sheep == veget） ）    
{
   return false;
}
   else     
{
   return true; // 安全返回true
}
}  
 
// 判断状态i与状态j之间是否可转换 
bool isConnect（AdjGraph *graph int i int j）
{    
   int k = 0;    
 
   if （graph->vertex[i].wolf != graph->vertex[j].wolf） 
{
   k++;   
}
 
   if （graph->vertex[i].sheep != graph->vertex[j].sheep）  
{
   k++;
}
 
   if （graph->vertex[i].veget != graph->vertex[j].veget）   
{
   k++;   
}
 
// 以上三个条件不同时满足两个且农夫状态改变时，返回真 也即农夫每次只能带一件东西过桥        
   if （graph->vertex[i].farmer != graph->vertex[j].farmer && k <= 1）    
{
   return true;  
}
   else     
{
   return false; 
}
}  
 
 
// 创建连接图    调用isSafe  isConnect函数 
void CreateG（AdjGraph *graph）
{   
   int i = 0;
   int j = 0;  
 
// 生成所有安全的图的顶点   找到安全的顶点 
    for （int farmer = 0; farmer <= 1; farmer++）      
    {
        for （int wolf = 0; wolf <= 1; wolf++）   
       {
            for （int sheep = 0; sheep <= 1; sheep++）  
           {
                for （int veget = 0; veget <= 1; veget++）  
               {
                    if （isSafe（farmer wolf sheep veget））             
                   {                     
                        graph->vertex[i].farmer = farmer;           
                        graph->vertex[i].wolf = wolf;                
                        graph->vertex[i].sheep = sheep;