在圖中查找子圖

Question

我在此處顯示一個圖。節點B_0，B_1屬於B，C_0，C_1節點。 C_2，C_3屬於C類節點，依此類推。現在 ，我想找到多個子圖，這可能satify像由本實施例中定義的標準 -

標準 -

1. 子包含類型A的1個節點，B型的1個節點，類型1個節點C，D型的一個節點。
2. 子圖從A型的節點到B型的一個節點，一個邊連接B型和C型，一個節點連接C型和D型。
3. 子圖包含從A型走出B型節點的一條邊，從B型到C型節點的一條邊 外部，從D型到E型的一個邊緣在外面。

現在這說明應該給的結果 -

1. 子:: A_0，B_0，C_1，D_1
2. 子:: A_0，B_0，C_0，D_0
3. 子:: A_0 ，B_1，C_2，D_2
4. 子:: A_0，B_1，C_3，D_3

我想知道，如果有任何的算法，b我可以找到這樣的子圖嗎？ 我試圖找出所有可能的組合算法。但是，這將是子圖中節點的數量的指數。因此，我想知道是否存在有效的計算方法。或者如果圖論中存在類似性質的問題？

Answer 1

您可以通過訪問類型A的所有節點對於每個節點開始，看看它們是B類型的從那裏看和C型的所有節點等連接到的所有節點，跟蹤您從最後一個節點訪問過的節點。然後，只要您到達完成搜索條件的子節點，就可以添加來自A節點的所有節點列表，直到您所在的位置。從本質上講，只要節點滿足隨後應該遵循的標準並且每當沒有更多有效的節點（即，將生成有效的子圖）從該節點出發時返回，則您在進行深度優先搜索，並持續遍歷該圖。你當前的節點。