Maximum Matching Found

假设(4,8), (5,9)已经在M中

1. 初始化：把V中空闲点1，2，3 放入队列Q中，Q={1,2,3}

2. 从队列中出队第一个元素1，找到元素1在U中的第一个邻接元素6。因为元素6是空闲元素，所以把(1,6)放进M中，又因为V(元素1）没有被标记，所以直接进入下次循环。 目前M={(1,6), (4,8), (5,9)} ,Q={2, 3}

3. 从队列Q={2,3} 中出队队首元素2，找到元素在U中的第一个邻接元素6，元素6已经在M中配对。因为(2,6)不在M中，所以用2标记元素6，把元素6放入Q的队尾。目前M={(1,6), (4,8), (5,9)} ,Q={3,6}

4. 从队列Q={3,6}中出队队首元素3，找到元素3在U中的邻接元素6，因为元素6在M中已经配对且已经被标记，所以继续找到下一个邻接元素8，元素8已经配对。(3,8)不在M中，且元素8为被标记，所以用3标记元素8，并把8放入Q的队尾。目前M={(1,6), (4,8), (5,9)} ,Q={6,8}

5. 从队列Q={6,8}中出队队首元素6，因为元素6属于U且在M中已经配对，所以用6标记它的配对元素1，并把元素1加入Q中。目前M={(1,6), (4,8), (5,9)} ,Q={8,1}

6. 从队列Q={8,1}中出队队首元素8，因为元素8属于U且在M中已经配对，所以用8标记它的配对元素4，并把元素4加入Q中。目前M={(1,4), (4,8), (5,9)} ,Q={1,4}

7. 从队列Q={1,4}中出队队首元素1，找到邻接元素6，因为6已经配对且标记，所以继续找到邻接元素7，因为元素7为空闲元素，所以把(1,7)加入M中，因为v(元素1)已经被标记，把v(元素1)的标签赋值到u中，即u=6，然后把(v,u)即(1,6)从M中除去。除去后把u(元素6)的标签赋值到v中，即v=2，把(v,u)即(2,6)加入M中。目前M={(1,7), (2,6), (4,8), (5,9)} ,Q={4}

8. 从队列Q={4}中出队队首元素4，找到邻接元素8，因为8已经配对且标记，所以继续找到邻接元素9，元素9已经配对。元素9未为被标记，所以继续找到元素4的邻接元素10，因为元素10为空闲元素，所以把(1,7)加入M中，因为v(元素4)已经被标记，把v(元素4)的标签赋值到u中，即u=8，然后把(v,u)即(4,8)从M中除去。除去后把u(元素8)的标签赋值到v中，即v=3，把(v,u)即(3,8)加入M中。目前M={(1,7), (2,6), (3,8), (4,10), (5,9)} ,Q={9}

9. 队列Q为空，算法结束