text1.cpp

数据结构实验

#include<iostream.h>
#define MaxNumVertices 10  //最大顶点数
typedef enum {FALSE,TRUE}Boolean;
typedef struct  //图的顶点类型
{
    int Farmer,Wolf,Sheep,Veget;
}VexType;
typedef struct
{
    int VertexNum,CurrentEdges;  //图的当前顶点数和边数
    VexType VerticesList[MaxNumVertices];  //顶点向量（代表顶点）
    int Edge[MaxNumVertices][MaxNumVertices];//邻接矩阵
    //用于存储图中的边，其矩阵元素个数取决于顶点个数，与边数无关
}AdjGraph;  //定义图的邻接矩阵存储结构
Boolean visited[MaxNumVertices];  //对已访问的顶点进行标记（图的遍历）
int path[MaxNumVertices];  
//保存DFS搜索到的路径，即与某顶点到下一顶点的路径

int locate(AdjGraph *G,int F,int W,int S,int V)
//查找顶点（F，W，S，V）在顶点向量中的位置
{  
    int i;
    for(i=0;i<G->VertexNum;i++)
        if(G->VerticesList[i].Farmer==F && G->VerticesList[i].Wolf==W &&
            G->VerticesList[i].Sheep==S && G->VerticesList[i].Veget==V)
            return(i);  //返回当前位置
        return (-1);  //没有找到此顶点
}

int is_safe(int F,int W,int S,int V)
//判断目前的（F，W，S，V）是否安全
{
    if(F!=S && (W==S||S==V))
        return (0);
    //当农夫与羊不在一起时，狼与羊或羊与白菜在一起是不安全的
    else   //否则安全
        return (1);  //安全返回1
}

int is_connected(AdjGraph *G,int i,int j)
//判断状态i与状态j之间是否可转换
{
    int k=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->VerticesList[j].Farmer && k<=1)
    //以上三个条件不同时满足两个且农夫状态改变时，返回真
    //也即农夫每次只能带一件东西过桥
        return(1);
    else
        return(0);
}

void CreateG(AdjGraph*G)
{
    int i,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->VerticesList[i].Wolf=W;
                        G->VerticesList[i].Sheep=S;
                        G->VerticesList[i].Veget=V;
                        i++;
                    }
    G->VertexNum=i;
    for(i=0;i<G->VertexNum;i++)  //邻接矩阵初始化即建立邻接矩阵
        for(j=0;j<G->VertexNum;j++)
            if(is_connected(G,i,j))
                G->Edge[i][j]=G->Edge[j][i]=1;
    //状态i与状态j之间可转化，初始化为1，否则为0
            else
                G->Edge[i][j]=G->Edge[j][i]=0;
    return;
}

void print_path(AdjGraph *G,int u,int v)
//输出从u到v的简单路径，即顶点序列中不重复出现的路径
{
    int k;
    k=u;
    while(k!=v)
    {
    cout<<"("<<G->VerticesList[k].Farmer<<","<<G->VerticesList[k].Wolf
        <<","<<G->VerticesList[k].Sheep<<","<<G->VerticesList[k].Veget<<")";
    cout<<endl;
    k=path[k];
    }
    cout<<"("<<G->VerticesList[k].Farmer<<","<<G->VerticesList[k].Wolf
        <<","<<G->VerticesList[k].Sheep<<","<<G->VerticesList[k].Veget<<")";
    cout<<endl;
}

void DFS_path(AdjGraph *G,int u,int v)
//深度优先搜索从u到v的简单路径
//DFS--Depth First Search
{
    int j;
    visited[u]=TRUE;  //标记已访问过的顶点
    for(j=0;j<G->VertexNum;j++)
        if(G->Edge[u][j] && !visited[j] && !visited[v])
        {
            path[u]=j;
            DFS_path(G,j,v);
        }
}

void main()
{
    int i,j;
    AdjGraph graph;
    CreateG(& graph);
    for(i=0;i<graph.VertexNum;i++)
        visited[i]=FALSE;  //置初值
    i=locate(&graph,0,0,0,0);
    j=locate(&graph,1,1,1,1);
    DFS_path(&graph,i,j);
    if(visited[j])
        print_path(&graph,i,j);
    return;
}