5_50.cpp

几个C++程序设计实例

#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;
}