擴展的圖形結構在C

我的問題：我有一個圖表製作node結構擴展的圖形結構在C

struct node { 
    node *n1; 
    node *n2; 
}

的，我想添加一些成員做出一個新的結構newNode

struct newNode { 
    newNode *n1; 
    newNode *n2; 
    newNode *n3; // new member 
    int  a; // new member 
}

我想要保留原圖中的「節點連接」，以便我能做

newNode *n; 
n->n1->n2...

就像

node *n; 
n->n1->n2...

，其中兩個結構的N1（或N2）表示相同的節點在圖中，同時我也可以做

newNode *n; 
n->n1->a... 
n->n1->n3...

是相當棘手的修改node結構，因爲它是在大型圖書館中定義。

我的想法是多了一個成員添加到newNode結構

struct newNode { 
    node *n; // added member 
    newNode *n1; 
    newNode *n2; 
    newNode *n3; 
    int  a; 
}

首先，我創建一個newNoden_new每個noden。然後我遍歷每一對n_new s，比如說n_new1和n_new2，看看n_new1->n和n_new2->n看它們之間是否有連接，也就是n_new1->n->n1 == n_new2->n或n_new1->n->n2 == n_new2->n，反之亦然。如果是的話，我做n_new1->n1 = n_new2或n_new1->n2 = n_new2，反之亦然。

但時間複雜度爲O(#node^2)。效率低下。

還有其他想法嗎？

P.S.該圖是降階二元決策圖。

來源

2014-01-18 linusz

你想與他們new_node和節點的圖形？ – user3125280

@ user3125280我想保留原始節點（和連接），但也要添加一些新的節點。這兩個結構首先應該代表相同的圖表。 – linusz

啊我現在明白了 - 你想要基本上覆制一個圖形結構。你所描述的確實是一個非常緩慢的方法。我建議你谷歌複製圖形數據結構或類似的。基本上覆制一個節點，創建一個n_new，然後用舊節點的n1和n2的副本填充它的n1和n2。您將需要一種機制來確定您已經複製了哪個節點（可能除非您可以更改節點源，否則您可能需要在此處使用bst或hash）。 – user3125280

你必須遞歸複製，每次遇到一個新的節點（請仔細閱讀這）時創建一個新的new_node。這將是原始圖形的完整副本，結構相同但使用不同的內存。

要確定我們是否已經複製一個節點，我們在映射節點*到new_node *一個BST保持我們已經複製的那些（並且其副本）的列表。

你可以在那裏找到許多BST實現。例如，在stl C++庫中有一個，我想glibc等等。

該代碼將是這樣的：如果沒有樹，所以它還是相當快

struct node { 
    node *n1; 
    node *n2; 
} 

struct new_node { 
    node *n1; 
    node *n2; 
    newNode *n3; // new member 
    int  a; // new member 
} 

new_node* GraphCopy (node* start) 
{ 
    new_node* n_new; 

    if(!start) return NULL; 

    n_new = malloc(sizeof(new_node)); 

    //Add start.n1 and start.n2 to a bst here 
    //with keys of node* and vals of new_node* 

    TreeInsert(start, n_new) 

    if(IsInTree(start->n1)) 
     n_new->n1 = TreeFind(start->n1); 
    else 
     n_new->n1 = GraphCopy(start->n1); 

    //repeat for n2 

}

複雜性將是線性的。（這將是一個哈希表更加線性，例如。）

（樹將映射節點*自己的副本。）

來源

2014-01-18 14:27:05 user3125280

擴展的圖形結構在C

回答

相關問題