收集DAG

的所有路徑我有向無環圖，其中每個節點是由一個狀態收集DAG

public class State{ 
    List<State> ForwardStates; 
    string stateName; 
}

其中ForwardStates是從當前狀態的下一狀態的列表表示。

我有兩個特殊的狀態

State initialState (name=initial) 
State finalState (name=final)

我希望能夠找到的所有路徑從初始狀態到最終狀態開始，在

List<List<string>> paths

填充例如，給定圖像下面這樣

enter image description here

paths應包含值 {{ 「初始」，「一」，「最後的」}，{ 「初始」，「B」，「最後的」}}

我應該如何輕鬆地做到這一點沒有遞歸的C＃（因爲圖形可能很大）？

來源

2013-01-31 william007

任何算法課程都會教你關於搜索算法 –

看看http://en.wikipedia.org/wiki/Breadth-first_search你學到的第一個 –

如果圖形真的很大，可能的數量路徑可能會呈指數級增長，並且路徑字符串可能不適合磁盤，更不用說內存 – mvp

你的算法可能會去像：

創建的Tuple<State, List<String>>隊列。
排隊{ InitialState, new List<string> { InitialState.Name } }
儘管隊列中有任何物品，
- 出列的第一個項目
- 對於在取出的狀態的所有非決賽前的狀態，排隊{ ForwardState, DequeuedList.ToList().Add(ForwardState.Name) }
- 如果最後的狀態是前狀態，將DequeuedList.ToList().Add(FinalState.Name)添加到您的輸出列表中。

您應該結束了一個空隊列，你的願望字符串列表的列表。

來源

2013-01-31 17:47:42 Rawling

感謝您的意見，我也用在這裏的建議 https://stackoverflow.com/a/9535898/1497720 （關鍵點是不使用BFS/DFS在被訪國家）

下面是一個使用DFS沒有訪問狀態的版本

List<List<string>> paths= new List<List<string>>(); 
      Stack<Tuple<State, List<string>>> working = new Stack<Tuple<State, List<string>>>(); 
      working.Push(new Tuple<State, 
       List<string>>(initialNode, 
       new List<string> { initialNode.stateName })); 
      do 
      { 
       Tuple<State, List<string>> curr = working.Pop(); 


       if (currNexts.stateName == "final") 
       { 
        res.Add(curr.Item2); 
       } 
       else 
       { 
        foreach (State currNext in curr.Item1.ForwardStates) 
        { 
         working.Push(new Tuple<State, 
         List<string>>(rnext, curr.Item2.Union(new[] { rnext.stateName }).ToList())); 
        } 
       } 
      } while (working.Count != 0);

來源

2013-02-01 03:12:58 william007

回答

相關問題