Create a filefor a graph that solves the 2-jealous husbands problem.Remember: the boat holds at most 2 people. The problem has 5 objects - two husbands, two wives, and the boat -5 objects in total. This means the game can be in any 1 of 32 states. If you were to write a transition table to solve the problem it would contain 32 x 32 = 1024 entries. Fortunately, most of these transitions are impossible. Since transitions from even numbered states to even numbered states or from odd numbered states to odd numbered states are impossible, 512 transitions are quickly eliminated.

The graph is not a weighted graph. The graph is an array of linked lists.

Do not write a program to solve the problem. Just create a data file for a program that solves the problem.

0->21->16->27->24->31 is one solution

transitions from state 0

0-> 0 impossible0->8 impossible0->16 impossible0->24 impossible

0->1 impossible0->9 violation0->17 dead end0->25 ok

0->2 impossible0->10 impossible0->18 impossible0->26 impossible

0->3 violation0->11 ok0->19 violation0->27 impossible

0->4 impossible0->12 impossible0->20 impossible0->28 impossible

0->5 dead end0->13 violation0->21 ok0->29 impossible

0->6 impossible0->14 impossible0->22 impossible0->30 impossible

0->7 ok0->15 impossible0->23 impossible0->31 impossible

Some transitions are impossible because they describe river crossings without the boat (0->1 and 0->4 for example)

Some transitions are impossible because they describe rivers crossings with more than 2 people in the boat (0->29 for example)

Some transitions are violations because they describe rivers crossings that place a wife with a another men and without her husband

A dead end occurs when the same person or person must repeat the crossing in the opposite direction.