【题目说明】一个农夫带着一只狼，牵着一只羊，挑着一担菜去赶集，前面有一条河拦住了他，河边有一艘船但船太小一次只能载农夫和他所带的其中一种东西，农夫知道狼会吃羊`羊也会吃他所带的菜要在都不被吃的情况下农夫怎么过去？
【思路】
如果用一个四元组(Farmer,Wolf,Sheep,Veget)表示当前农夫、狼、羊和菜所处的位置，其中每个元素可以是0或者1,0表示在左岸，1表示在右岸。这样对四个元素的不同取值可以构成16种不同的状态，初始时的状态为(0,0,0,0),最终要到达的目标为(1,1,1,1).状态之间可以转换有下面四种情况：
【程序代码】
1 #include2 #define VEX_NUM 10 //最大顶点数 3 typedef enum {FALSE, TRUE} Boolean; 4 5 //定义图的顶点类型 6 typedef struct 7 { 8 int Farmer, Wolf, Sheep, Veget; 9 }VexType; 10 11 typedef struct 12 { 13 int vexnum, e; //图当前顶点数和边数 14 VexType vexs[VEX_NUM]; //顶点向量 15 int adj[VEX_NUM][VEX_NUM]; //邻接矩阵 16 }AdjGraph; 17 18 Boolean visited[VEX_NUM]; 19 int path[VEX_NUM]; 20 21 //查找顶点(F, W, S, V)在顶点向量中的位置 22 int locate(AdjGraph * G, int F, int W, int S, int V) 23 { 24 int i; 25 for(i = 0; i < G->vexnum; i++) 26 if(G->vexs[i].Farmer == F && G->vexs[i].Sheep == S && G->vexs[i].Veget == V && G->vexs[i].Wolf == W) 27 return (i); 28 return -1; 29 } 30 31 //判断状态(F, W, S, V)是否安全 32 int is_safe(int F, int W, int S, int V) 33 { 34 if(F != S && (W == S || S == V)) 35 return 0; 36 else 37 return 1; 38 } 39 40 //检查第i个状态和第j个状态之间是否可以转换 41 int is_connected(AdjGraph * G, int i, int j) 42 { 43 int k; 44 k = 0; 45 if(G->vexs[i].Wolf != G->vexs[j].Wolf) 46 k++; 47 if(G->vexs[i].Sheep != G->vexs[j].Sheep) 48 k++; 49 if(G->vexs[i].Veget != G->vexs[j].Veget) 50 k++; 51 if(G->vexs[i].Farmer != G->vexs[j].Farmer && k <= 1) 52 return 1; 53 else 54 return 0; 55 } 56 57 //创建邻接矩阵 58 void CreateG(AdjGraph *G) 59 { 60 int i, j, F, W, S, V; 61 i = 0; 62 63 //形成所有的安全结点 64 for(F = 0; F <= 1; F++) 65 for(W = 0; W <= 1; W++) 66 for(S = 0; S <=1; S++) 67 for(V = 0; V <= 1; V++) 68 if(is_safe(F, W, S, V)) 69 { 70 G->vexs[i].Farmer = F; 71 G->vexs[i].Wolf = W; 72 G->vexs[i].Sheep = S; 73 G->vexs[i].Veget = V; 74 i++; 75 } 76 G->vexnum = i; 77 for(i = 0; i < G->vexnum; i++) 78 for(j = 0; j < G->vexnum; j++) 79 if(is_connected(G, i, j)) 80 G->adj[i][j] = G->adj[j][i] = 1; 81 else 82 G->adj[i][j] = G->adj[j][i] = 0; 83 return; 84 } 85 86 //输出u到v的简单路径 87 void print_path(AdjGraph * G, int u, int v) 88 { 89 int k; 90 k = u; 91 while(k != v) 92 { 93 printf("(%d,%d,%d,%d)\n", G->vexs[k].Farmer, G->vexs[k].Wolf, G->vexs[k].Sheep, G->vexs[k].Veget); 94 k = path[k]; 95 } 96 printf("(%d,%d,%d,%d)\n", G->vexs[k].Farmer, G->vexs[k].Wolf, G->vexs[k].Sheep, G->vexs[k].Veget); 97 } 98 99 //求u到v的简单路径100 void DFS_path(AdjGraph* G, int u, int v)101 {102 int j;103 visited[u] = TRUE;104 for(j = 0; j < G->vexnum; j++)105 if(G->adj[u][j] && !visited[j] && !visited[v])106 {107 path[u] = j;108 DFS_path(G, j, v);109 }110 }111 112 void main()113 {114 int i, j;115 AdjGraph graph;116 CreateG(&graph);117 for(i = 0; i < graph.vexnum; i++)118 visited[i] = FALSE;119 i = locate(&graph, 0, 0, 0, 0);120 j = locate(&graph, 1, 1, 1, 1);121 DFS_path(&graph, i, j);122 if(visited[j])123 print_path(&graph, i, j);124 125 return;126 }