JAVA學習筆記：以DFS (深度優先搜尋) 尋找兩節點間所有路徑

現在是深夜2:47
結果我居然在寫JAVA學習筆記....

其實心情低落了三四天了...
繼上星期週末回家之後為了解決6步以內2 node所有的路徑數
首先我使用了老闆所說的用矩陣相乘去找到2步、3步...到6步
正當我花了一整天寫到半夜也已經把方法都寫完的時候~~
我學習同門不點一姐的精神~ 把測試用的網路畫在紙上
開始一條一條走，驗算這些矩陣到底是不是正確的時候....


悲劇發生了


對


使用矩陣來計算有向圖，會造成迴路的問題
也就是說，當矩陣相乘第三次的時候
如果A→B，B→A，而我們要找A→C，
三步的路徑中就會包含這一條A→B→A→C

上網查了之後，發現有網友指出矩陣在迴路方面是很難解決的...
繼續查詢的結果是，建議使用DFS─深度優先搜尋，來解決路徑尋找的問題

DFS演算法我也懶得說了~ 網路上實在族繁不及備載

比較麻煩的是，知道DFS我又要怎麼實現路徑尋找呢?

只能說上天還算是眷顧我~ 藉由陳博士的協助下，他幫我找了一個論壇網頁
裡面正好是在討論我一直在尋找的問題~
更貼心的是~  居然有人把他的程式碼貼上來XD
讓我這個不才研究生可以直接引用T^T

參考網址如下
http://stackoverflow.com/questions/58306/graph-algorithm-to-find-all-connections-between-two-arbitrary-vertices

也因為這個討論串很詳細，所以我在改成我需要的格式其實沒有花太久的時間...
簡單來說，網頁中的Graph.java其實就是指建立有向網路圖的類別
裡面有幾個方法~ 首先是增加新的edge，只要輸入兩個node  前者當KEY，後者放入作為value的linkedlist中~
然後也有檢查雙向edge的方法~
還有去尋找鄰居的方法等等~

Search.java則是實際運用Graph類別，把兩個相連的節點丟入Graph中~
設立起點跟終點之後，建立breadthFirst這個物件就可以找出起點跟終點的所有路徑了~

恩 我寫得真複雜~  但事實上這個作者寫得真的不錯
只是我這個傻子後來還是遇到問題了....

QQ  邏輯阿邏輯
我參~~~~~不透你阿!!