求任意兩個頂點之間所有聯系的圖算法我試圖確定完成以下任務的最佳時間效率算法。我有一套記錄。對于這組記錄，我有連接數據，它指示來自這個集合的記錄對如何彼此連接。這基本上代表了一個無向圖，記錄是頂點，連接數據是邊。集合中的所有記錄都有連接信息(即不存在孤立記錄；集合中的每個記錄連接到集合中的一個或多個其他記錄)。我希望從集合中選擇任意兩個記錄，并且能夠顯示所選記錄之間的所有簡單路徑。所謂“簡單路徑”是指路徑中沒有重復記錄的路徑(即僅有限路徑)。注意：兩個選擇的記錄總是不同的(即起始點和結束頂點永遠不會相同；沒有循環)。例如： If I have the following records:
A, B, C, D, E
and the following represents the connections:
(A,B),(A,C),(B,A),(B,D),(B,E),(B,F),(C,A),(C,E),
(C,F),(D,B),(E,C),(E,F),(F,B),(F,C),(F,E)
[where (A,B) means record A connects to record B]如果我選擇B作為我的起始記錄，選擇E作為我的結束記錄，我會希望通過記錄連接找到所有簡單的路徑來連接記錄B以記錄E。 All paths connecting B to E:
B->E
B->F->E
B->F->C->E
B->A->C->E
B->A->C->F->E這是一個例子，在實踐中，我可能有包含數十萬條記錄的集合。
2 回答
千萬里不及你
TA貢獻1784條經驗 獲得超9個贊
[P]是表示當前路徑的頂點列表。 [X]是滿足條件的路徑列表 [s]是源頂點。 [d]是目標頂點。 [C]是當前頂點(路徑查找例程的參數)。
1 PathList [p] 2 ListOfPathLists [x] 3 Vertex [s], [d] 4 PathFind ( Vertex [c] ) 5 Add [c] to tail end of list [p] 6 For each Vertex [v] adjacent to [c] 7 If [v] is equal to [d] then 8 Save list [p] in [x] 9 Else If [v] is not in list [p] 10 PathFind([v]) 11 Next For 12 Remove tail from [p] 13 Return
添加回答
舉報
0/150
提交
取消