��1���㷨����/1
1.1ʲô���㷨1
1.2�㷨���s��2
1.3�㷨���s��Ӌ��3
1.4�㷨���s�Եı�ʾ4
1.4.1�㷨���s�Եĝu���ԑB4
1.4.2���s�ԝu���A5
1.4.35���u�����x�µ�ӛ̖ 5
1.4.4��Ҋ���㷨�r�g���s��6
1.5�㷨���s�Ե���Ҫ��7
���}18
��2���f�w�c����� /11
2.1�f�w�ĸ���11
2.2���η��Ļ���˼��16
2.3�����������g18
2.3.1���Բ���18
2.3.2����������18
2.3.3���������㷨���s��*�����η���19
2.3.4���������㷨���s��ƽ�����η���20
2.4�������ij˷�20
2.4.1�������˷e�ķ����㷨����20
2.4.2�������˷e�ĕr�g���s���f�Ʒ���21
2.5Strassen��ꇳ˷�21
2.5.1Strassen��ꇷ��γ˷�21
2.5.2�r�g���s���f�Ʒ���22
2.6��P���w���}22
2.6.1���}����22
2.6.2�㷨���s�Է���25
2.7�ϲ�����25
2.7.1���ڱ��^������r�g���s���½�25
2.7.2���f�w����f�w�Pϵʽ26
2.7.3�ϲ�����27
2.8��������30
��1���㷨�����c�OӋĿ䛡�3����3��2.8.1�㷨����30
2.8.2�r�g���s�ȷ���32
2.9ѭ�hِ�ճ̱�����32
2.9.1���}����32
2.9.2���}�ķ��η��OӋ˼��33
2.9.3�����㷨���F33
���}234
��3�„ӑBҎ����/41
3.1�ӑBҎ��������41
3.1.1*����ԭ��41
3.1.2�ӑBҎ�����Ļ������E41
3.2����B�ˆ��}45
3.2.1���}����45
3.2.2����*����ĽY��47
3.2.3�����f�w�Pϵ47
3.2.4Ӌ��*��ֵ48
3.2.5����*����49
3.3�ӑBҎ���㷨�Ļ���Ҫ��50
3.3.1*���ӽY��50
3.3.2�دB�ӆ��}50
3.3.3����䛷���52
3.4*�L���������І��}53
3.4.1���}����53
3.4.2*�L���������еĽY��54
3.4.3�ӆ��}���f�w�Y��54
3.4.4Ӌ��*��ֵ55
3.4.5����*�L����������56
3.4.6�㷨�ĸ��M57
3.5͹��߅�ε�*�������ʷֆ��}57
3.5.1���}����57
3.5.2�����ʷֵĽY���������P���}58
3.5.3*���ӽY�����|60
3.5.4*�������ʷ֌����ę���f�w�Y��60
3.5.5Ӌ��*��ֵ60
3.5.6����*�������ʷ�61
3.6��߅���Α�61
3.6.1���}����61
3.6.2*���ӽY�����| 62
3.6.3�f�w���63
3.6.4�㷨����63
3.7�D�񉺿s65
3.7.1�D�񉺿s����65
3.7.2*���ӽY�����|67
3.7.3�f�wӋ��*��ֵ67
3.7.4�㷨���F68
���}370
��4��؝���㷨/74
4.1��Ӱ��ņ��}74
4.1.1؝���㷨�OӋ�����c74
4.1.2���}����74
4.1.3��Ӱ��ņ��}��؝���㷨 75
4.2؝���㷨�Ļ���Ҫ��76
4.2.1؝���x�����|76
4.2.2*���ӽY�����|77
4.2.3؝���㷨������^��77
4.2.4؝���㷨�c�ӑBҎ�����IJ78
4.3*���b�d79
4.3.1���}����79
4.3.2؝���x�����|79
4.3.3*���ӽY�����|80
4.3.4�㷨����80
4.4*��·�����}80
4.4.1���}����80
4.4.2�㷨����˼��81
4.4.3�㷨���F82
4.5���������a84
4.5.1��������84
4.5.2����һ�ù�������86
4.5.3���������a87
4.5.4�㷨�����c�OӋ89
4.5.5�������㷨�����_��91
4.6TSP���}92
4.6.1TSP���}�о��Mչ92
4.6.2*�����c؝�IJ���93
4.6.3*��朽�؝�IJ���95
4.7*С���ɘ�96
4.7.1Prim�㷨��*����c���ԣ�96
4.7.2Kruskal�㷨��*��߅���ԣ�97
4.8�������}98
4.8.1�������}����98
4.8.2���}��؝���x�����|99
4.8.3���}��*���ӽY�����|99
4.8.4�㷨����99
���}4101
��5�»��ݷ�/107
5.1���ݷ����㷨���107
5.1.1���_���x���}�Ľ���g107
5.1.2�\�û��ݷ����}�IJ��E108
5.1.3���ݷ����㷨���108
5.2n�ʺ��}110
5.2.1���}����110
5.2.2�㷨�OӋ110
5.2.3�㷨���F111
5.2.48�ʺ��}�IJ���Ч������c���F111
5.3�D��m��ɫ���}117
5.3.1���}����117
5.3.2�㷨���F119
5.4���ݷ���Ч�ʷ���120
5.4.1����ԭ��120
5.4.2����Y�c��120
5.4.3���ݷ���Ч��122
���}5122
��6�·�֧�޽編/127
6.1��֧�޽編�Ļ���˼��127
6.2��֧�޽編���㷨����128
6.2.1��֧�޽編��0��1�������}128
6.2.2��֧�޽編�������̆��}130
6.2.3��֧�޽編��15�i���}132
6.3��Դ*��·�����}136
6.3.1���}����136
6.3.2�㷨����136
6.3.3��֧�޽��㷨���F137
6.4�b�d���}141
6.4.1���ʽ��֧�޽編141
6.4.2�㷨�ĸ��M143
6.4.3����*����143
6.4.4*�������֧�޽磨�������ʽ��144
���}6145
��7�¸����㷨/147
7.1�S�C��147
7.2��ֵ�����㷨152
7.2.1���S�CͶ�c��Ӌ��πֵ152
7.2.2Ӌ�㶨�e��154
7.2.3��Ǿ��Է���158
7.2.4��Ǿ��Է��̽M160
7.3���ؿ��_�㷨170
7.3.1���ؿ��_�㷨�Ļ���˼��170
7.3.2���ؿ��_�㷨�ĺ��Α���171
7.3.3��Ԫ�؆��}174
7.3.4�ؔ��yԇ176
7.4��˹�S��˹�㷨181
7.4.1n�ʺ��}181
7.4.2�������ӷֽ�187
7.5������㷨188
7.5.1���ԕr�g�x���㷨189
7.5.2���S��191
���}7193
��8�Œ��ָ��/195
���1���η��ϙC���195
���1��1��P���w���}�ķ��η��OӋ195
���1��2���÷��η����F�ϲ�����197
���1��3�÷��η����F���������㷨200
���1��4ѭ�hِ�ճ̱����ņ��}�ķ��η��OӋ201
���1��5*���Ӷκ͆��}�ķ��η��OӋ203
���2�ӑBҎ�����ϙC���204
���2��1����B�ˆ��}�ĄӑBҎ�����OӋ205
���2��2*�L���������еĄӑBҎ�����OӋ207
���2��3�D�񉺿s���}�ĄӑBҎ�����OӋ208
���3؝���㷨�ϙC���213
���3��1��Ӳ�ņ��}��؝���㷨�OӋ214
���3��2��Ӱ��ņ��}��؝���㷨215
���3��3��Դ*��·�����}��؝���㷨�OӋ216
���4���ݷ��ϙC���219
���4��18�ʺ��}�Ļ��ݷ��OӋ219
���4��2�D����ɫ���}�Ļ��ݷ��OӋ222
��9���㷨�Ԝy��/225
9.1�㷨�Ԝy��1225
9.2�㷨�Ԝy��2226
9.3�㷨�Ԝy��3231
������}������/234
���}1������234
���}2������235
���}3������237
���}4������241
���}5������246
���}6������248
���}7������252
�㷨�Ԝy��1������266
�㷨�Ԝy��2������268
�㷨�Ԝy��3������272