查找定向圖是否單向連接的有效算法？

是否有任何有效的算法來確定面向圖是否單向連接？單邊連接意味着圖形中從一個頂點到另一個頂點的方式不會超過一個。謝謝。查找定向圖是否單向連接的有效算法？

我假設有，由於僅存在一個任意兩個頂點之間的路徑是樹的圖。（如果圖表未連接，則爲森林。） – biziclop

是單方面連接的簡單循環嗎？ –

@biziclop作爲一棵樹是足夠的但不是必需的：考慮一個5-節點的圖，其邊A-> C，B-> C，C-> D，C-> E。 – Sneftel

其實我覺得你的定義是錯誤的，我重新檢查了好來源，我發現，一個directed graph is connected (or "unilaterally connected") if there is a path between any two vertices

也有

strictly unilaterally connected if it is not strongly connected

（和信息：it is "strongly connected" if there is a path in both directions between any two vertices）

它實際上並沒有說「只有一條路」。所述scrictly單方面連接僅說，如果有從A到B的路徑，不存在從B到路徑A（但仍可以有從甲10點的路徑B）

Alghorithms：

對於「不嚴格」變體，您可以嘗試在每個節點上執行DFS。當DFS在節點「X」上結束時，記住所有未到達的節點「Y1，Y2，Y3 ...」。對於所有的人，如果你在上面運行DFS，他們必須達到X，否則圖不單方面連接

對於「嚴」變種它幾乎是相同的，但你也必須檢查節點「 Z1，Z2，Z3「 - 當節點」X「達到時 - 不能達到X，當你運行DFS時。

複雜性：

DFS本身是O(n + k)（n爲節點，k是邊緣），則必須運行它n次（每個節點上），因此複雜性是O((n+k)*n)

如果您想要的最大複雜度只與節點相關，也是可能的。

邊緣的最大數目是O(k) = O(n^2)，因此最大複雜度是O((n+n^2)*n) = O(n^3)

2015-11-05 13:32:38 libik

謝謝你，你完全正確。但是我需要一個算法來找出在任何兩個頂點之間是否沒有更多可能的路徑。在我的任務中，術語「單向連接圖」就像我以前寫的那樣定義。 –

回答