扩展的图形结构在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

回答

相关问题