You did most of the job. Each vertex is a state $(M, K, B)$ and edges represent the possibility to pass from a state to another with one ship transport. Let say $B$ can take the values $L$ or $R$ for left and right edges respectively. $K$ is the number of cannibals on left edge and $B$, the number of monks on left edge. Initially all monks and cannibals are on left edge with the boat: state is $(M_0, K_0, L)$. Note that for any state there are $M_0-M$ monks and $K_0-K$ cannibals on right edge.
You can notice that any ship transport would change $B$ value from $L$ to $R$ or vice-versa. Thus your state graph is a bipartite graph. It changes nothing to the problem, but it is interesting to notice it.
Concerning $K$ and $M$, to respect the "cannibal constraint", a valid node must have:
- $K \le M$ for left edge (or $M = 0$),
- $K_0-K \le M_0-M$ for right edge (or $M=M_0$)
A valid left->right transport (edge) should be:
$(M_i, K_i, L)$ -> $(M_i-m, K_i-k, R)$, such that $(m, k)$ in $\{(1, 0), (2, 0), (1, 1), (0, 1), (0, 2)\}$.
and a valid right->left transport (edge) should be:
$(M_i, K_i, R)$ -> $(M_i+m, K_i+k, L)$, such that $(m, k)$ in $\{(1, 0), (2, 0), (1, 1), (0, 1), (0, 2)\}$.
Of course you must keep $0 \le M \le M_0$ and $0 \le K \le K_0$.
BFS in the graph
So now, how to proceed ? You can create all possible vertices that is to say all $(M, K, B)$ with $M \le M_0, K\le K_0, B \in {L, R})$ that does respect the cannibals constraint. Then build all the possible edges (up to 5 from any vertex). Finally you can run the BFS in this graph to find an eventual solution. The graph would have up to $2 M_0 K_0$ vertices and $10 M_0 K_0$ edges.
A stronger solution is to build your graph as you explore it. You can express formally all states reachable from any state and check if the vertex of this state is already explored or not.
Also note that BFS is generally a good exploration method to find the shortest distance, but here you can expect left->right transports should move 2 persons and right->left transports should move only one person to decrease the left edge population.
This is indeed a good exercise for graph state representation and exploration, but after it you should try to answer these questions:
- What property between $M_0$, $K_0$ is necessary and sufficient to have a solution ? (exception of $M_0 = 0$)
- What is the straight forward method to find such solution ?
Here is a small example for $M_0 = 3, K_0=2$. In blue the edges enconutered and in red the followed one.
