節點網絡（圖）可以表示爲一棵或多棵樹嗎？

Question

當我將圖轉換成樹時，我不介意樹中有重複的節點。讓我解釋一下相反的方法。假設我有兩棵共同元素的樹。我可以加入他們的共同元素來創建圖表。

我可以在相反的方向做到這一點，即從圖形開始並將元素拆分爲重複以創建多個樹形結構？

Answer 1

如果我理解正確，你需要一個包含原始的所有鏈接的樹，通過允許原始節點在樹中多次出現。這是某種spanning tree，除了約束條件是保持所有鏈接（而不是保留所有節點，如在經典生成樹中）。

因此，您可以使用類似於用於發現經典生成樹的方法。基本方法基於廣度優先搜索或深度優先搜索。您從一個隨機節點開始，然後將其添加到您的樹中。然後使用搜索算法探索其鄰居，並且每次到達節點時，都會將其添加到樹中（使用相應的鏈接）。您必須維護所有處理過的鏈接的列表，以便您不會最終處理相同的鏈接兩次。此外，您需要一種唯一標識每個節點的方法，以允許在您的樹上進行後續處理。例如，只需對原始圖中的節點進行編號即可。