农夫过河问题（图结构）_农夫过河问题: 一个老农携带一只狼、一只羊羔和一筐白菜,要从南岸过河到北岸。岸

【题目介绍】： 
所谓农夫过河问题是指农夫带一只狼、一只羊和一棵白菜在河南岸需要安全运到北岸。一条小船只能容下他和一件物品只有农夫能撑船。问农夫怎么能安全过河。 
当然，狼吃羊，羊吃白菜，农夫不能将这两种或三种物品单独放在河的一侧，因为没有农夫的照看狼就要吃羊，而羊可能要吃白菜? 这类问题的实质是系统的状态问题, 要寻求的是从初始状态经一系列的安全状态到达系统的终止状态的一条路径。

【问题描述】： 
首先，将这个实际问题抽象为数学模型，过河与没过河是两种不同的状态，农夫、狼、羊和菜，分别处于这两种状态，所以一共有2的4次方，16种状态。但这16种状态中有一些状态是不安全的应该剔除掉。 
如果我们将没过河状态看做0，过河看做1，那么问题就变成从初始状态（0000），经过一定和有限个状态变成最终状态（1111）的过程。这样我们就可以抽象出一张图来，每个状态表示一个节点，满足条件的节点之间有一条路，这样问题就抽象为，在无向图中找一条路。 
1.可定义一个结构体表示农夫，狼，羊和白菜。南岸和北岸用0,1表示。 
2.题目要求求出农夫带一只羊，一条狼和一颗白菜过河的办法，所以依次成功返回运算结果后，需要继续运算，直至求出结果，即给出农夫的过河方案，可以采用递归的方法实现。 
3.输出界面要求具有每一步中农夫所带对象及每步之后各岸的物体，需要定义不同的数组来分别存储上述内容。

【过程理解】：可以看输出结果来理解 
1、一开始有16种组合。 
2、然后判断待在同一边是否安全，得到10种组合，相当于10个顶点。 
3、然后再根据谁要跟农夫过河得到所有可能的路径组合 
4、第一个顶点和最后一个顶点已经确定，所以就可以遍历出最后的路径顺序。

【源代码】：

#include<iostream> 
#include <stdlib.h>
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++) // 从0开始查找
    {
        if (graph->vertex[i].farmer == farmer && graph->vertex[i].wolf == wolf&& graph->vertex[i].sheep == sheep && graph->vertex[i].veget == veget)
        {
            return i; //返回顶点序号i,start=0,end=9
        }
 
    }
    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)
    {
        cout << i<<"->"<<j<<"   ";
        return true;
    }
    else
    {
        return false;
    }
}
 
// 创建连接图
void CreateG(AdjGraph *graph)
{
    int i = 0;
    int j = 0;
    // 生成所有安全的图的顶点
    cout << "生成所有安全的图的顶点:" << endl;
    cout << "       farmer" << ", wolf" << ", sheep" << ", veget" << endl;
    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;
                        cout << "第"<<i<<"组数据组合：(" << graph->vertex[i].farmer << ",  " << graph->vertex[i].wolf << ",    " << graph->vertex[i].sheep << ",   " << graph->vertex[i].veget << ")"<<endl;
                        i++;
                    }
                }
            }
        }
    }
    cout << "i:" << i << endl;
    // 邻接矩阵初始化即建立邻接矩阵
    graph->vertexNum = i;//把产生的10组安全组合赋给vertexNum
    cout << "所有符合条件的路径：" << endl;
    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 << endl;
    cout << "最后符合条件的路径："<<endl;
    cout << "      farmer " << ", wolf " << ", sheep " << ", veget " << endl;
    while (i != end)
    {
        cout << "第"<<i<<"个顶点：(" << judgement(graph->vertex[i].farmer) <<":"<< graph->vertex[i].farmer<< ", " << judgement(graph->vertex[i].wolf) << ":"<<graph->vertex[i].wolf<< ", " << judgement(graph->vertex[i].sheep) <<":" <<graph->vertex[i].sheep<< ", " << judgement(graph->vertex[i].veget) << ":"<<graph->vertex[i].veget<< ")";
        cout << endl;
        i = retPath[i];
    }
    cout << "第" << i << "个顶点：(" << judgement(graph->vertex[i].farmer) << ":" << graph->vertex[i].farmer << ", " << judgement(graph->vertex[i].wolf) << ":" << graph->vertex[i].wolf << ", " << judgement(graph->vertex[i].sheep) << ":" << graph->vertex[i].sheep << ", " << judgement(graph->vertex[i].veget) << ":" << 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);//start=0
    int end = locate(&graph, 1, 1, 1, 1);//end=9
    dfsPath(&graph, start, end);
    if (visited[end])
    {
        printPath(&graph, start, end);
        system("pause");
        return 0;
    }
 
 
    //return -1;
}

图结构包括两大部分： 
1、顶点：所有的数据元素，每个元素就是一个顶点（数字1、2、3、4、5、6）。 
2、边：连接两个元素之间的线就是边。 
图分为无向图和有向图：

【无向图】：没有方向的图结构

 
【有向图】：带有箭头方向的图结构 
 
无向图和有向图最大的区别在于边： 
1、无向图的<1,2>和<2,1>代表同一条边。 
2、有向图中的<1,2>和<2,1>代表不同的两条边。

【顶点的度Degree】:就是连接顶点的变得数量。无向图结构中就有6条边，度就是6.

【邻接顶点】：就是一条边上的两个顶点，无向图无所谓，但是有向图的顶点有入边邻接顶点和出边邻接顶点之分。

【无向完全图】：每两个顶点之间都有一条线连着，就是所有顶点全被连到了。 
 
【有向完全图】：跟上面无向完全图有点像，只不过是两个顶点之间的边变为两条反方向的。 
 
【路径】：路径就是图结构两个顶点之间的连线，跟边有区别，路径可能会有很多条，包含很多条边（2到5之间的黑线就是一条路径，包括2条边，那么路径的度就是2）。

【无向带权图】：无向图的边加了权值，可能表示边的长度或者其他意义。 
 
【有向带权图】：跟无向带权图差不多，就不解释了。