Posted on 2013-05-26 10:40
鑫龍 閱讀(259)
評論(0) 編輯 收藏 引用 所屬分類:
數據結構與算法
題目：一個單入口單出口的有向無環圖中，要求在某些地方插入一些節點使得任何一條由起點到終點所經歷的節點數相同，類似于下面的圖，要求給出算法描述并分析時間復雜度。
如上圖所示，節點A到C有兩條路徑，ABC這條路徑經過了一個節點，而AC路徑經過了0個節點，我們的算法所要做的事就是要在AC路徑中間加入一個節點，然后ABC路徑和ADC路徑都經過了一個節點。
算法是這樣的：對于每個節點維護一組信息，包括節點的層數（起始節點到該節點的路徑長度，起始節點設為0）以及生成該長度的父節點，相對于右圖，節點6維護的不經處理的信息就是：層數2來自節點3和節點4；節點7維護的不經處理的信息就是：層數3來自節點5和節點6以及層數2來自節點4；節點8的不經處理的信息是：層數4來自節點7，層數3來自節點7，層數2來自節點4。我們算法所要做的事就是最終使每個節點需要維護的層信息變為一個，即無論從那條路徑到該節點，該節點所處的層數都是固定的。算法如下：1、初始化起始節點的層數信息2、從起始節點開始遍歷每條路徑，遇到每個節點生成一個維護信息（1）如果此節點不存在維護信息，創建之；（2）如果該節點存在維護信息，有兩種情況：（a）如果生成的維護信息的層數和原來已有的維護信息的層數是相同的，則合并這兩個維護信息，比如對于例子中的圖，節點5原來的維護信息為“層數3來自節點2”，然后從節點3到節點5生成的維護信息為“層數3來自節點3”，由于層數相同，我們可以將其合并為“層數3來自節點2和節點3”；（b）如果生成的維護信息的層數和原來節點的維護信息的層數不一致，我們需要比較那一個的層數較大：a.如果原來維護信息的層數較大，此時，我們只需要在生成此維護信息的節點與此節點之間插入一個新的節點，然后生成新節點的維護信息，然后從新節點開始（2）過程b.如果新生成的維護信息的層數較大，將新生成的節點信息存入此節點，然后我們需要在生成原來維護信息的所有節點和此節點之間插入新節點，并且需要從所有的新插入節點開始（2）過程