我正在嘗試通過Java的幫助找到下一個問題的解決方案。我有一個曲線圖,這是它如何能看一個很好的例子:如何解決帶週期的圖形
有其符號:
[{甲 = {C = 0.7},{d = 0.3 }}, {C = {out = 0.2},{F = 0.8}}, {D = {C = 0.1},{F = 0.2},{G = 0.3},{E = 0.4 }}, {S = {A = 0.4},{B = 0.6}},
{Ê = {G = 0.3},{出= 0.7}},{ ģ = {B = 0.2} {出= 0.8}},...
小號 - 是一個起始節點(S = 1),out - 是一種出圖的方式。
我想跟蹤圖表並知道每個節點有多少百分比。 在例如,甲 = 0.4 * S(S = 1),Ç = 0.7A + 0.1D,d = 0.3A + 0.7B
我認爲這是可能的遞歸來做到這一點(有向圖的DFS,特別是Tarjan的alg。),但是有些週期我不認爲會有幫助。另一個解決方案是解決一個線性方程組。 我不知道什麼是更好的工作,也許有一些解決方案存在這種任務。 這個例子只是一個例子,但我應該考慮,我喜歡appr。 2000個節點(以及誰知道多少個週期)。
你會怎麼做?
爲什麼選擇BFS而不是DFS? DFS可能會盡快找到出路。 – 2011-04-13 19:09:53