开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 文章/文档 > 查看源码
5_49.cpp
资源名称：c++ example.rar　[点击查看]
上传用户：zipjojo
上传日期：2009-07-20
资源大小：70k
文件大小：3k
源码类别：

文章/文档

开发平台：

C/C++

5_49.cpp：源码内容
  1. #include<iostream.h>
  2. #define MaxNumVertices 10  //最大顶点数
  3. typedef enum {FALSE,TRUE}Boolean;
  4. typedef struct  //图的顶点类型
  5. {
  6. int Farmer,Wolf,Sheep,Veget;
  7. }VexType;
  8. typedef struct
  9. {
  10. int VertexNum,CurrentEdges;  //图的当前顶点数和边数
  11.     VexType VerticesList[MaxNumVertices];  //顶点向量（代表顶点）
  12. int Edge[MaxNumVertices][MaxNumVertices];//邻接矩阵
  13.     //用于存储图中的边，其矩阵元素个数取决于顶点个数，与边数无关
  14. }AdjGraph;  //定义图的邻接矩阵存储结构
  15. Boolean visited[MaxNumVertices];  //对已访问的顶点进行标记（图的遍历）
  16. int path[MaxNumVertices];  
  17. //保存DFS搜索到的路径，即与某顶点到下一顶点的路径
  18. int locate(AdjGraph *G,int F,int W,int S,int V)
  19. //查找顶点（F，W，S，V）在顶点向量中的位置
  20. {  
  21. int i;
  22. for(i=0;i<G->VertexNum;i++)
  23. if(G->VerticesList[i].Farmer==F && G->VerticesList[i].Wolf==W &&
  24. G->VerticesList[i].Sheep==S && G->VerticesList[i].Veget==V)
  25. return(i);  //返回当前位置
  26. return (-1);  //没有找到此顶点
  27. }
  29. int is_safe(int F,int W,int S,int V)
  30. //判断目前的（F，W，S，V）是否安全
  31. {
  32. if(F!=S && (W==S||S==V))
  33. return (0); 
  34. //当农夫与羊不在一起时，狼与羊或羊与白菜在一起是不安全的
  35. else   //否则安全
  36. return (1);  //安全返回1
  37. }
  39. int is_connected(AdjGraph *G,int i,int j)
  40. //判断状态i与状态j之间是否可转换
  41. {
  42. int k=0;
  43. if(G->VerticesList[i].Wolf!=G->VerticesList[j].Wolf)
  44. k++;
  45. if(G->VerticesList[i].Sheep!=G->VerticesList[j].Sheep)
  46. k++;
  47. if(G->VerticesList[i].Veget!=G->VerticesList[j].Veget)
  48. k++;
  49. if(G->VerticesList[i].Farmer!=G->VerticesList[j].Farmer && k<=1)
  50.     //以上三个条件不同时满足两个且农夫状态改变时，返回真
  51.     //也即农夫每次只能带一件东西过桥
  52. return(1);
  53. else 
  54. return(0);
  55. }
  57. void CreateG(AdjGraph*G)
  58. {
  59. int i,j,F,W,S,V;
  60. i=0;
  61. for(F=0;F<=1;F++)  //生成所有安全的图的顶点
  62. for(W=0;W<=1;W++)
  63. for(S=0;S<=1;S++)
  64. for(V=0;V<=1;V++)
  65. if(is_safe(F,W,S,V))
  66. {
  67. G->VerticesList[i].Farmer=F;
  68. G->VerticesList[i].Wolf=W;
  69. G->VerticesList[i].Sheep=S;
  70. G->VerticesList[i].Veget=V;
  71. i++;
  72. }
  73. G->VertexNum=i;
  74. for(i=0;i<G->VertexNum;i++)  //邻接矩阵初始化即建立邻接矩阵
  75. for(j=0;j<G->VertexNum;j++)
  76. if(is_connected(G,i,j))
  77. G->Edge[i][j]=G->Edge[j][i]=1;
  78. //状态i与状态j之间可转化，初始化为1，否则为0
  79. else
  80. G->Edge[i][j]=G->Edge[j][i]=0;
  81. for(int k=0;k<G->VertexNum;k++){
  82. cout<<"("<<G->VerticesList[k].Farmer<<","<<G->VerticesList[k].Wolf
  83. <<","<<G->VerticesList[k].Sheep<<","<<G->VerticesList[k].Veget<<")";
  84. cout<<endl;}
  85. return;
  86. }
  88. void main()
  89. {
  90. AdjGraph graph;
  91. CreateG(& graph);
  92. return;
  93. }