数据结构 农夫过河问题.doc

#includeiostream 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) { // 从0开始查找 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; } } // 创建连接图 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)) {