数据结构农夫过河问题

数据结构农夫过河问题数据结构农夫过河问题 #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]; // 顶点向...

数据结构农夫过河问题 #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) { // 从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)) { graph->vertex[i].farmer = farmer; graph->vertex[i].wolf = wolf; graph->vertex[i].sheep = sheep; graph->vertex[i].veget = veget; i++; } } } } } // 邻接矩阵初始化即建立邻接矩阵 graph->vertexNum = i; for (i = 0; i < graph->vertexNum; i++) { for (j = 0; j < graph->vertexNum; j++) { // 状态i与状态j之间可转化，初始化为1，否则为0 if (isConnect(graph, i, j)) { graph->Edge[i][j] = graph->Edge[j][i] = true; } else { graph->Edge[i][j] = graph->Edge[j][i] = false; } } } return; } // 判断在河的哪一边 char* judgement(int state) { return ( (0 == state) ? "南岸" : "北岸" ); } // 输出从u到v的简单路径，即顶点序列中不重复出现的路径 void printPath(AdjGraph *graph, int start, int end) { int i = start; cout << "farmer" << ", wolf" << ", sheep" << ", veget" << endl; while (i != end) { cout << "(" << judgement(graph->vertex[i].farmer) << ", " << judgement(graph->vertex[i].wolf) << ", " << judgement(graph->vertex[i].sheep) << ", " << judgement(graph->vertex[i].veget) << ")"; cout << endl; i = retPath[i]; } cout << "(" << judgement(graph->vertex[i].farmer) << ", " << judgement(graph->vertex[i].wolf) << ", " << judgement(graph->vertex[i].sheep) << ", " << judgement(graph->vertex[i].veget) << ")"; cout << endl; } // 深度优先搜索从u到v的简单路径 //DFS--Depth First Search void dfsPath(AdjGraph *graph, int start, int end) { int i = 0; visited[start] = true; //标记已访问过的顶点 if (start == end) { return ; } for (i = 0; i < graph->vertexNum; i++) { if (graph->Edge[start][i] && !visited[i]) { retPath[start] = i; dfsPath(graph, i, end); } } } int main() { AdjGraph graph; CreateG(&graph); int start = locate(&graph, 0, 0, 0, 0); int end = locate(&graph, 1, 1, 1, 1); dfsPath(&graph, start, end); if (visited[end]) { printPath(&graph, start, end); return 0; } return -1; }

                    本文档为【数据结构 农夫过河问题】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

数据结构 农夫过河问题

你可能还喜欢

数据结构农夫过河问题