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