鍥撅紙Graph锛夋槸鏁板�﹀拰璁＄畻鏈虹�戝�︿腑鐨勪竴涓�閲嶈�佹�傚康锛屽畠鐢遍《鐐癸紙Vertex锛夊拰杈癸紙Edge锛夌粍鎴愶紝骞挎硾鐢ㄤ簬琛ㄧず鍚勭�嶅叧绯诲拰缁撴瀯銆傚湪杩欑瘒鏂囩珷涓�锛屾垜浠�灏嗘帰璁ㄥ浘鐨勫熀鏈�姒傚康銆佺被鍨嬨�佸簲鐢ㄤ互鍙婁竴浜涘父瑙佺殑绠楁硶銆�
棣栧厛锛屽浘鐨勫熀鏈�瀹氫箟鏄�鐢变竴缁勯《鐐瑰拰涓�缁勮竟缁勬垚鐨勩�傞《鐐瑰彲浠ヨ��瑙嗕负鍥句腑鐨勨�滅偣鈥濓紝鑰岃竟鍒欐槸杩炴帴杩欎簺鐐圭殑鈥滅嚎鈥濄�傝竟鍙�浠ユ槸鏈夊悜鐨勶紙Directed锛夋垨鏃犲悜鐨勶紙Undirected锛夛紝鏈夊悜鍥句腑鐨勮竟鏈夋柟鍚戯紝鑰屾棤鍚戝浘涓�鐨勮竟娌℃湁鏂瑰悜銆傛�ゅ�栵紝鍥句腑鐨勮竟杩樺彲浠ュ甫鏉冮噸锛圵eight锛夛紝杩欐剰鍛崇潃杈逛笂鏈変竴涓�鏁板�艰〃绀哄畠鐨勨�滄垚鏈�鈥濇垨鈥滆窛绂烩�濄�傝繖绉嶅浘绉颁负甯︽潈鍥俱��
鍥剧殑绫诲瀷鏋佸�氾紝甯歌�佺殑鏈夌畝鍗曞浘銆佸畬鍏ㄥ浘銆佺█鐤忓浘鍜屽瘑闆嗗浘绛夈�傜畝鍗曞浘鏄�鎸囨病鏈夐噸澶嶈竟鍜岃嚜鐜�鐨勫浘锛涘畬鍏ㄥ浘鏄�鎸囨瘡瀵归《鐐逛箣闂撮兘鏈夎竟鐩歌繛鐨勫浘锛涚█鐤忓浘鏄�鎸囪竟鐨勬暟閲忚繙灏戜簬椤剁偣鏁伴噺鐨勫浘锛岃�屽瘑闆嗗浘鍒欐槸鎸囪竟鐨勬暟閲忔帴杩戜簬鏈�澶у彲鑳芥暟閲忕殑鍥俱�傝繖浜涗笉鍚岀殑鍥剧粨鏋勪娇寰楀湪瑙ｅ喅瀹為檯闂�棰樻椂鍙�浠ラ�夋嫨鏈�鍚堥�傜殑琛ㄧず鏂瑰紡銆�
鍥剧殑搴旂敤闈炲父骞挎硾锛屽嚑涔庢兜鐩栦簡鐢熸椿涓�鐨勫悇涓�棰嗗煙銆傚湪绀句氦缃戠粶涓�锛岀敤鎴峰彲浠ヨ�嗕负鍥句腑鐨勯《鐐癸紝鑰屼粬浠�涔嬮棿鐨勫叧绯诲垯鏄�杈癸紱鍦ㄤ氦閫氱綉缁滀腑锛屽煄甯傚彲浠ユ槸椤剁偣锛岃�屽煄甯備箣闂寸殑閬撹矾鍒欐槸杈癸紱鍦ㄨ�＄畻鏈虹綉缁滀腑锛岃�＄畻鏈哄彲浠ユ槸椤剁偣锛岀綉缁滀腑鐨勮繛鎺ュ彲浠ヨ�嗕负杈广�傝繖浜涘簲鐢ㄤ娇寰楀浘鎴愪负浜嗙悊瑙ｅ拰鍒嗘瀽澶嶆潅鍏崇郴鐨勯噸瑕佸伐鍏枫��
鍦ㄥ浘璁虹殑鐮旂┒涓�锛屾湁璁稿�氶噸瑕佺殑绠楁硶琚�骞挎硾搴旂敤锛屽叾涓�鍖呮嫭娣卞害浼樺厛鎼滅储锛圖FS锛夈�佸箍搴︿紭鍏堟悳绱�锛圔FS锛夈�丏ijkstra绠楁硶銆丳rim绠楁硶鍜孠ruskal绠楁硶绛夈�傛繁搴︿紭鍏堟悳绱㈠拰骞垮害浼樺厛鎼滅储鏄�鐢ㄤ簬閬嶅巻鎴栨悳绱㈠浘涓�鐨勬墍鏈夐《鐐圭殑鍩烘湰绠楁硶銆侱FS閫氳繃閫掑綊鐨勬柟寮忔繁鍏ュ埌鍥剧殑灞傛�′腑锛岃�孊FS鍒欐槸閫愬眰閬嶅巻銆傝繖涓ょ�嶇畻娉曞湪瑙ｅ喅璺�寰勬煡鎵惧拰杩為�氭�ч棶棰樻椂闈炲父鏈夋晥銆�
Dijkstra绠楁硶鍒欐槸鐢ㄤ簬瑙ｅ喅鏈�鐭�璺�寰勯棶棰樼殑涓�绉嶇粡鍏哥畻娉曪紝閫傜敤浜庡甫鏉冨浘銆傚畠鑳芥壘鍒颁粠涓�涓�璧峰�嬮《鐐瑰埌鎵�鏈夊叾浠栭《鐐圭殑鏈�鐭�璺�寰勩�侾rim绠楁硶鍜孠ruskal绠楁硶鍒欑敤浜庤В鍐虫渶灏忕敓鎴愭爲闂�棰橈紝鍓嶈�呴�氳繃涓嶆柇鎵╁睍鏍戠殑鏂瑰紡鏉ユ瀯閫犳渶灏忕敓鎴愭爲锛岃�屽悗鑰呴�氳繃杈圭殑鏉冮噸杩涜�岄�夋嫨銆�
闇�瑕佹敞鎰忕殑鏄�锛屽浘鐨勫�嶆潅鎬т篃甯︽潵浜嗚�稿�氭寫鎴樸�備緥濡傦紝鍥句腑鐨勬煇浜涢棶棰樻槸NP闅鹃�橈紝濡傚浘鐫�鑹查棶棰樺拰鍝堝瘑灏旈】璺�寰勯棶棰樸�傝櫧鐒跺畠浠�鍦ㄥ皬瑙勬ā瀹炰緥涓�鍙�浠ヨ��鏈夋晥瑙ｅ喅锛屼絾闅忕潃鍥剧殑瑙勬ā澧炲ぇ锛岃繖浜涢棶棰樼殑姹傝В鍙樺緱寮傚父鍥伴毦銆�
鎬荤殑鏉ヨ�达紝鍥炬槸涓�绉嶅己澶ц�岀伒娲荤殑缁撴瀯锛岀敤浜庤〃绀哄拰鍒嗘瀽鍚勭�嶇被鍨嬬殑鏁版嵁鍜屽叧绯汇�傞殢鐫�璁＄畻鏈虹�戝�︿互鍙婃暟鎹�绉戝�︾殑涓嶆柇鍙戝睍锛屽浘鐨勭爺绌跺拰搴旂敤灏嗕細瓒婃潵瓒婂箍娉涳紝鎴愪负鐞嗚В澶嶆潅绯荤粺鐨勯噸瑕佸伐鍏枫�傚�逛簬鐮旂┒鑰呭拰瀹炶返鑰呰�岃█锛屾帉鎻″浘鐨勫熀鏈�姒傚康鍜岀浉鍏崇畻娉曪紝灏嗘槸鐞嗚В鍜屽�勭悊澶嶆潅闂�棰樼殑鍩虹��銆�