從混合圖中提取鏈組件

Question

給定一個由有向和無向邊組成的混合非循環圖，我想將這個圖分解成鏈組件的有向圖（鏈組件中的每個節點只會與無向邊緣）和他們的順序。

我很困惑我是否應該先拓撲排序的所有有向邊，然後尋找無向邊的鏈組件，還是首先應該我去了所有無向邊，並給他們組的ID，然後找一些有向邊連接這些部件。

由於圖是非循環的，我認爲可以從低編號的組件到高編號的組件排序，但不能提供一個可靠的答案。

Answer 1

我認爲你的兩個方法都能正常工作。

在我看來，第二種方法似乎更自然。

如果我在networkx這樣做，我會通過實現你的第二個方法：

1. 創建僅包含無向邊一個新的圖形小時。

2. 在H上調用connected_components來提取鏈組件併爲每個組件分配一個不同的組ID。

3. 爲每個組ID創建一個具有1個節點的新圖F。基於原始圖中的有向邊，將F中的組連接到有向邊。在F上調用topological_sort以計算組ID的排序。

Answer 2

混合圖表這樣你描述是再次有向圖。只需用兩個指向相反方向的指向邊替換每個無向邊。

此外，你不能有一個非週期圖具有無向邊。至少有一個長度爲2的週期會一直存在，所以我不確定這是什麼意思。

看起來你正在尋找這個圖表中強連通的組件，所以我建議你使用Tarjan's algorith來找到它們。