We illustrate here the application of the Chu-Liu-Edmonds algorithm to dependency parsing on the simple example x = John saw Mary, with directed graph representation G x , The first step of the algorithm is to find, for each word, the highest scoring incoming edge If the result were a tree, it would have to be the maximum spanning tree.
in this case we have a cycle, so we will contract it into a single node and recalculate edge weights according to Figure 3.