package Ġchapter 4 . section 3 Ċ Ċ import Ġedu . pr inc et on . cs . al gs 4 . Queue Ċ import Ġextensions . format Double Ċ Ċ /** Ċ Ġ* Ġ ç»Ļ å®ļ ä¸Ģ å¹ ħ åĬł æĿĥ åĽ¾ G ä»¥åıĬ å®ĥçļĦ æľĢå°ı çĶŁæĪĲ æłĳ ãĢĤ Ċ Ġ* Ġ åĲĳ G ä¸Ń æ·»åĬł ä¸ĢæĿ¡ è¾¹ e ï¼Į å¦Ĥä½ķ åľ¨ ä¸İ V æĪĲ æŃ£ æ¯Ķ çļĦæĹ¶éĹ´ åĨħ æī¾åĪ° æĸ° åĽ¾ çļĦ æľĢå°ı çĶŁæĪĲ æłĳ ãĢĤ Ċ Ġ* Ċ Ġ* Ġ è§£ ï¼ļ çĶ± æłĳ çļĦ æĢ§ è´¨ åı¯ä»¥ å¾Ĺ çŁ¥ ï¼Į çĶ¨ ä¸ĢæĿ¡ è¾¹ è¿ŀæİ¥ æłĳ ä¸ŃçļĦ ä»»æĦı ä¸¤ä¸ª é¡¶ çĤ¹ éĥ½ä¼ļ äº§çĶŁ ä¸Ģä¸ª æĸ°çļĦ çİ¯ Ċ Ġ* Ġä½¿çĶ¨ å¹¿ åº¦ ä¼ĺåħĪ æĲľç´¢ æī¾åĪ° çİ¯ çļĦæīĢæľī è¾¹ ï¼Į åİ» éĻ¤ çİ¯ ä¸Ń æĿĥ éĩį æľĢå¤§ çļĦ è¾¹ å°±æĺ¯ æĸ°çļĦ æľĢå°ı çĶŁæĪĲ æłĳ Ċ Ġ* Ġ éģįåİĨ æĹ§ çļĦ æľĢå°ı çĶŁæĪĲ æłĳ ï¼Į æŀĦéĢł ä¸Ģä¸ª éĤ » æİ¥ è¡¨ ï¼Į åĨį å°Ĩ è¾¹ e åĬłåħ¥ éĤ » æİ¥ è¡¨ ä¸Ń ï¼Į æĹ¶éĹ´ å¤įæĿĤ åº¦ O ( V ) Ċ Ġ* Ġä»¥ e çļĦä¸Ģä¸ª é¡¶ çĤ¹ å¼Ģå§ĭ ä½¿çĶ¨ å¹¿ åº¦ ï¼Ī æĪĸ æ·± åº¦ ï¼ī ä¼ĺåħĪ æĲľç´¢ æī¾åĪ° ä¸Ģä¸ª çİ¯ ï¼Į æĹ¶éĹ´ å¤įæĿĤ åº¦ O ( V ) Ċ Ġ* Ġ éģįåİĨ çİ¯ ä¸Ń æīĢæľīçļĦ è¾¹ ï¼Į åĪłéĻ¤ æĿĥ éĩį æľĢå¤§ çļĦ è¾¹ ï¼Į åī © ä½Ļ çļĦ è¾¹ æŀĦéĢł æĪĲ æĸ°çļĦ æľĢå°ı çĶŁæĪĲ æłĳ Ċ Ġ*/ Ċ fun Ġex 1 5 ( graph : ĠE WG , Ġm st : ĠM ST , Ġe : ĠEdge ): ĠIterable < Edge > Ġ{ ĊĠĠĠ Ġval Ġtree Ġ= ĠEdge Weighted Graph ( graph . V ) ĊĠĠĠ Ġm st . edges (). forEach Ġ{ ĊĠĠĠĠĠĠĠ Ġtree . add Edge ( it ) ĊĠĠĠ Ġ} ĊĠĠĠ Ġtree . add Edge ( e ) ĊĊĠĠĠ Ġval Ġcycle Ġ= ĠEdge Weighted Graph Cycle ( tree ). cycle ()?. iterator () ĊĠĠĠ Ġif Ġ( cycle Ġ== Ġnull Ġ|| Ġ! cycle . hasNext ()) Ġreturn Ġtree . edges () ĊĠĠĠ Ġvar Ġmax Edge Ġ= Ġcycle . next () ĊĠĠĠ Ġwhile Ġ( cycle . hasNext ()) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġedge Ġ= Ġcycle . next () ĊĠĠĠĠĠĠĠ Ġif Ġ( edge Ġ> Ġmax Edge ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġmax Edge Ġ= Ġedge ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġval Ġresult Ġ= ĠQueue < Edge >() ĊĠĠĠ Ġtree . edges (). forEach Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( it Ġ!= Ġmax Edge ) Ġresult . enqueue ( it ) ĊĠĠĠ Ġ} ĊĠĠĠ Ġreturn Ġresult Ċ } Ċ Ċ fun Ġmain () Ġ{ ĊĠĠĠ Ġval Ġgraph Ġ= Ġget Tiny Weighted Graph () ĊĠĠĠ Ġval Ġm st Ġ= ĠPrim M ST ( graph ) ĊĠĠĠ Ġprintln ( mst ) ĊĊĠĠĠ Ġ// Ġ 1 - 7 - 0 - 2 - 6 - 1 Ġ ç»Ħ æĪĲ ä¸Ģä¸ª çİ¯ ï¼Į 2 - 6 æĿĥ éĩį æľĢå¤§ è¢« åĪłéĻ¤ ï¼Į æľĢå°ı çĶŁæĪĲ æłĳ æĢ» æĿĥ éĩį åĩı å°ı ĊĠĠĠ Ġval Ġe 1 Ġ= ĠEdge ( 1 , Ġ 6 , Ġ 0 . 2 ) ĊĠĠĠ Ġval Ġresult 1 Ġ= Ġex 1 5 ( graph , Ġm st , Ġe 1 ) ĊĠĠĠ Ġvar Ġweight 1 Ġ= Ġ 0 . 0 ĊĠĠĠ Ġresult 1 . forEach Ġ{ ĊĠĠĠĠĠĠĠ Ġweight 1 Ġ+= Ġit . weight ĊĠĠĠ Ġ} ĊĠĠĠ Ġprintln (" weight 1 =${ format Double ( weight 1 , Ġ 2 )} ") ĊĠĠĠ Ġprintln ( result 1 . join ToString ( separator Ġ= Ġ"\ n ") Ġ{ Ġit . toString () Ġ}) ĊĠĠĠ Ġprintln () ĊĊĠĠĠ Ġ// Ġ 1 - 7 - 0 - 2 - 6 - 1 Ġ ç»Ħ æĪĲ ä¸Ģä¸ª çİ¯ ï¼Į æĸ° åĬłåħ¥ çļĦ 1 - 6 æĿĥ éĩį æľĢå¤§ è¢« åĪłéĻ¤ ï¼Į æľĢå°ı çĶŁæĪĲ æłĳ ä¸į åıĺ ĊĠĠĠ Ġval Ġe 2 Ġ= ĠEdge ( 1 , Ġ 6 , Ġ 0 . 5 ) ĊĠĠĠ Ġval Ġresult 2 Ġ= Ġex 1 5 ( graph , Ġm st , Ġe 2 ) ĊĠĠĠ Ġvar Ġweight 2 Ġ= Ġ 0 . 0 ĊĠĠĠ Ġresult 2 . forEach Ġ{ ĊĠĠĠĠĠĠĠ Ġweight 2 Ġ+= Ġit . weight ĊĠĠĠ Ġ} ĊĠĠĠ Ġprintln (" weight 2 =${ format Double ( weight 2 , Ġ 2 )} ") ĊĠĠĠ Ġprintln ( result 2 . join ToString ( separator Ġ= Ġ"\ n ") Ġ{ Ġit . toString () Ġ}) Ċ }