瀛︿範蹇呭
娆㈣繋涓嬭浇
ACM
鐭ヨ瘑鐐瑰垎绫?/p>
绗竴绫伙細鍩虹绠楁硶
锛?/p>
1
锛?/p>
鍩虹绠楁硶锛?/p>
鏋氫妇锛岃椽蹇冿紝閫掑綊锛屽垎娌伙紝閫掓帹锛屾瀯閫狅紝妯℃嫙
锛?/p>
2
锛?/p>
鍔ㄦ�佽鍒掞細
鑳屽寘闂锛屾爲褰?/p>
dp
锛岀姸鎬佸帇缂?/p>
dp
锛屽崟璋冩�т紭鍖栵紝鎻掑ご
dp
锛?/p>
3
锛?/p>
鎼滅储锛?/p>
dfs
锛?/p>
bfs
锛岃蹇嗗寲鎼滅储锛屼紭鍖栦笌鍓灊锛屽弻骞匡紝
A*
锛?/p>
IDA*
锛岃烦鑸為摼
绗簩绫伙細鏁版嵁缁撴瀯
锛?/p>
1
锛?/p>
绠�鍗曟暟鎹粨鏋勶細
閾捐〃锛屾爤鍜岄槦鍒楋紝涓诧紝鏍戝拰浜屽弶鏍戯紝鍥撅紝鎺掑簭涓庢绱?/p>
锛?/p>
2
锛?/p>
鏍戝舰缁撴瀯锛?/p>
绾挎鏍戯紝鏍戠姸鏁扮粍锛屽瓧鍏告爲锛屼几灞曟爲锛屽乏鍋忔爲锛屽姩鎬佹爲锛?/p>
lca&rmq
锛屽垝鍒?
鏍戯紝
SBT
锛?/p>
3
锛?/p>
瀛楃涓诧細
kmp
锛?/p>
AC
鑷姩鏈猴紝鍚庣紑鏁扮粍锛屾渶灏忚〃绀烘硶
锛?/p>
4
锛?/p>
鍏朵粬锛?/p>
骞舵煡闆嗭紝鏁ｅ垪琛紝鍧楃姸閾捐〃锛屽弻鍚戦摼琛?/p>
绗笁绫伙細鍥捐
锛?/p>
1
锛?/p>
鏈�鐭矾锛?/p>
dijkstra,bellman-ford(spfa
浼樺寲
),floyd,heap+dijkstra ,
宸垎绾︽潫锛岀
K
鏈�
鐭矾
锛?/p>
2
锛?/p>
鐢熸垚鏍戯細
prim,kruskal,
搴﹂檺鍒舵渶灏忕敓鎴愭爲
,
鏈�浼樻瘮鐜囩敓鎴愭爲
,
娆″皬鐢熸垚鏍?/p>
,
鏈�灏忔爲褰㈠浘锛?
鐢熸垚鏍戠殑璁℃暟锛屾爲鐨勫垝鍒嗭紝鏍戠殑鏋氫妇
锛?/p>
3
锛?/p>
鍖归厤闂锛?/p>
浜屽垎鍥剧殑鏈�澶у尮閰?/p>
(
鍖堢墮鍒╃畻娉?/p>
)
锛?/p>
KM
锛?/p>
2-SAT
锛屽悓鏋?/p>
锛?/p>
4
锛?/p>
缃戠粶娴侊細
鏈�澶ф祦锛屾渶灏忚垂鐢ㄦ渶澶ф祦锛屾渶灏忓壊妯″瀷銆佺綉缁滄祦瑙勭害
锛?/p>
5
锛?/p>
鍏朵粬锛?/p>
鎷撴墤鎺掑簭锛屽弻杩為�氬垎閲忥紝寮鸿繛閫氬垎鏀強鍏剁缉鐐癸紝鍥剧殑鍓茶竟涓庡壊鐐癸紝鏃犲悜鍥俱�佹湁
鍚戝浘鐨勬渶灏忕幆锛屾鎷夎矾寰勶紝鍝堝瘑椤胯矾寰勶紝骞抽潰鍥撅紝鍒嗗眰鍥炬�濇兂锛屽伓鍥?/p>