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