graph.cpp

野人和修道士问题。（要求用图的邻接表的存储结构实现） 题目：假设有N个修道士和N个野人准备渡河

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
//---------算法思想:1.构图------先找出安全状态的结点再可行的道路两两连接
//------------------2.再按深搜和广搜搜出可行和最短的路径
#define Max 200
#define MaxSize 200
typedef int Data;

#include"SeqCQueue.h"
int visited[200];//--------用来标记结点是否被访问
int Path[200];//----记下广搜每个结点的前驱，即路径
int Path1[200];//----记录深搜回溯找每条路径，
int v1;//-----所找路径的初始值
int v2;//---------要到达的值
int N;//------最短路化径渡河方案的总数
int M;//--------记录用广搜找到最短路径的长度
typedef struct
{	
	int dao;//修道士
	int	man;//野人
    int flag;//船在哪岸上
}DataType;
typedef struct Node
{
  int dest;//邻接边的弧头的序号
  struct  Node *next;
}Edge;
typedef struct 
{
    DataType data;
	int score;//邻接点的弧序号
	Edge *adj;
}AdjLHeight;
typedef struct 
{
	AdjLHeight a[Max];
	int numOfVerts;
	int numOfEdges;
}AdjLGraph;
//--------------图的初始化
void AdjInitiate(AdjLGraph *G)
{
	int i; 
	G->numOfVerts=0;
    G->numOfEdges=0;
	for(i=0;i<Max;i++)
	{
		G->a[i].score=i;
		G->a[i].adj=NULL;
	}
}
//-------------释放空间
void AdjDestory(AdjLGraph *G)
{
	int i;
	Edge *p,*q;
	for(i=0;i<G->numOfVerts;i++)
	{
		p=G->a[i].adj;
		while(p!=NULL)
		{
			q=p->next;
			free(p);
			p=q;
		}
	}
}
//-------------------插入结点
void InsertVert(AdjLGraph *G,int i,DataType data)
{
   if(i>=0&&i<Max)
   {
	   G->a[i].data=data;
	   G->numOfVerts++;
   }
   else  printf("结点越界\n");
}
//------------------插入边，图是有向图
void InsertEdge(AdjLGraph *G,int i,int j)
{
	Edge *p;
	if(i<0||i>=G->numOfVerts||j<0||j>=G->numOfVerts)
	{
		printf("参数出错!\n");
		return;
	}
	else {
		p=(Edge*)malloc(sizeof(Edge));
		p->dest=j;
		p->next=G->a[i].adj;
        G->a[i].adj=p;
		G->numOfEdges++;//边数加一
	}
}
//---------------查找起始岸状态和最后的结点
int  Search(AdjLGraph *G,int x,int y,int n)
{
	int i;
	for(i=0;i<G->numOfVerts;i++)
	if(G->a[i].data.dao==x&&G->a[i].data.man==y
		&&G->a[i].data.flag==n)
		return i;
	 return -1;
}

//---------------将能够走通的边都连接起来
int  Connect(AdjLGraph *G,int i,int j,int n)
{
    int m;
	m=G->a[j].data.dao-G->a[i].data.dao+G->a[j].data.man-G->a[i].data.man;
  if(G->a[i].data.flag==0&&G->a[j].data.flag==0||G->a[i].data.flag==1&&G->a[j].data.flag==1)
	  return 0;//两个结点都在此岸或都在对岸，不连通
  else if(G->a[i].data.flag==1&&G->a[j].data.flag==0)
  {//-------------从起始岸到终点岸的情况，运过去人应该有所减少
	  if(G->a[j].data.dao>G->a[i].data.dao||G->a[j].data.man>G->a[i].data.man)
	  //----------如果J结点的道士或野人的个数比开始船没从I开到J时还大时
	   return 0;
	   if(G->a[j].data.dao==G->a[i].data.dao&&G->a[j].data.man==G->a[i].data.man)
		   return 0;
	   if((-1)*m>n)return 0;//------------船上的人超重
	   return 1;
  }
  else if(G->a[i].data.flag==0&&G->a[j].data.flag==1)
{
	  //-----------------------从终点到起始最后人应该有所增加
	  if(G->a[j].data.dao<G->a[i].data.dao||G->a[j].data.man<G->a[i].data.man)
	  //----------如果J结点的道士或野人的个数比开始船没从I开到J时还小时
	   return 0;
    if(G->a[j].data.dao==G->a[i].data.dao&&G->a[j].data.man==G->a[i].data.man)
		 return 0;
	   if(m>n)return 0;//------------船上的人超重
	   return 1;
  }
  return 0;
}
//------------------判断这种情况是否可行
int Safe(int x,int y,int z,int n)//道士，野人，船的位置
{
 //------------------考虑起始岸和对岸两方面
 //--------------------n是总共的道士或野人的个数
  if(x>0&&x<y)return 0;
  if(x==n&&y==n&&z==0)return 0;//对岸没人，船在起始岸
  if(x==0&&y==0&&z==1)return 0;//人都在起始岸，船在彼岸
  if(n-x>0&&n-x<n-y)return 0;
  return 1;
}
//----------------创建图，用邻接表的存储
void Great(AdjLGraph *G,int n,int x)
{
	//n-----------船可装的人的总数
	//x-----------修道士和野人的个数
	int i,j,k,m;
	m=0;
	DataType Data;
	for(k=0;k<=1;k++)//船有两种情况,在对岸和在起始岸
	   for(i=0;i<=x;i++)
		   for(j=0;j<=x;j++)
			   if(Safe(i,j,k,x)==1)
			   {
				   Data.dao=i;
				   Data.man=j;
				   Data.flag=k;
				  // printf("(%d %d %d)\n",i,j,k);
				   InsertVert(G,m,Data);
				   m++;
			   }
			  // printf("verts:%d\n",G->numOfVerts);
	//-----------------连接行得通的边,构造有向图

	for(i=0;i<G->numOfVerts;i++)
		for(j=0;j<G->numOfVerts;j++)
			if(Connect(G,i,j,n))
			
				InsertEdge(G,i,j);
}
//------------------打印路径
void Print(AdjLGraph G)
{
	int k,i=0;
   for(k=Path[v1];k!=v2;k=Path[k])i++;
   if(i==M)
   {
	N++;
	printf("(%d %d %d)---->",G.a[v1].data.dao,G.a[v1].data.man,G.a[v1].data.flag);
	for(k=Path[v1];k!=v2;k=Path[k])
	printf("(%d %d %d)---->",G.a[k].data.dao,G.a[k].data.man,G.a[k].data.flag);
    printf("(%d %d %d)\n",G.a[v2].data.dao,G.a[v2].data.man,G.a[v2].data.flag);
   }
}
//--------------------从后向前打印路径
int Print1(AdjLGraph G)
{
	int k,i=0;
	printf("(%d %d %d)<-----",G.a[v2].data.dao,G.a[v2].data.man,G.a[v2].data.flag);
	for(k=Path1[v2];k!=v1;k=Path1[k])
	{
		i++;
		printf("(%d %d %d)<------",G.a[k].data.dao,G.a[k].data.man,G.a[k].data.flag);
	}
    printf("(%d %d %d)\n",G.a[v1].data.dao,G.a[v1].data.man,G.a[v1].data.flag);
	return i;
}
//-----------------------用广度优先遍历，最先搜索到的那条路径一定是最短的
int BroadFSearch(AdjLGraph G,int u,int v)
{
   Edge *p;
   int visit[200];
   int w,z;
   memset(visit,0,sizeof(visit));
   SeqCQueue Q;
   visit[u]=1;
   QueueInitiate(&Q);
   QueueAppend(&Q,u);
   while(QueueNotEmpty(Q))
   {
	   QueueDelete(&Q,&w);
	   p=G.a[w].adj;
	   while(p!=NULL)
	   {
          z=p->dest;
		  if(z==v)
		  {
            Path1[z]=w;//---------------保存前驱
			printf("输出一种最短路径的情况\n");
			M=Print1(G);
			return 1;
		  }
		else if(!visit[z])
		 {
            Path1[z]=w;
			visit[z]=1;
            QueueAppend(&Q,z);
		}
		p=p->next;
	   }
   }
   return 0;
}
          




//---------------------用深搜回溯求出所有解
void DFS2(AdjLGraph G,int u,int v )
{
	Edge *p;
	int w;
	visited[u]=1; 
	p=G.a[u].adj; 
	while(p!=NULL)
	{ 
		w=p->dest;
	    if(w==v)	
		{
			Path[u]=w;//-----记下当前结点的后驱
			Print(G);
		}
		else if(visited[w]==0) {	
		  Path[u]=w;
		 //找后驱，保存下来
	    DFS2(G,w,v);
		}  

		p=p->next;  
	}
	visited[u]=0;
}
//-------访问结点
void visit(AdjLGraph G,int v)
{
	printf("(%d %d %d)\n",G.a[v].data.dao,G.a[v].data.man,G.a[v].data.flag);
}
 //--------------用于测试函数，遍历整个图
void DFS(AdjLGraph G, int v)
{ 
	Edge *p;
	int w;
	visited[v]=1; 
	visit(G,v);  
	p=G.a[v].adj; 
	while(p!=NULL)
	{
		w=p->dest;  
		if(visited[w]==0) DFS(G,w);  
		p=p->next; 
	}
}
//-------------------主函数
 int main()
 {
	 int n,x;
	 AdjLGraph G;
	 printf("输入小船可装的人数:\n");
	 while(scanf("%d",&n)!=EOF)
	 { 
	 memset(Path,0,sizeof(0));
	 memset(visited,0,sizeof(visited));
	 memset(Path1,0,sizeof(Path1));
	 printf("输入野人或修道士的个数:\n");
	 scanf("%d",&x);
	 N=0;
	 AdjInitiate(&G);
     Great(&G,n, x);
	 v1=Search(&G,x,x,1 );
	 v2=Search(&G,0,0,0 );
    if(BroadFSearch( G,v1, v2)==0)
		printf("渡河失败\n");
	else{
		printf("输出所有最短路径的情况:\n");
      DFS2(G,v1,v2);
	 printf("共有%d种情况\n",N);
	 }
 printf("输入小船可装的人数:\n");
	 }
	 return 0;
 }