S**Y
发帖数: 136 | 1 一个graph;
class Node
{
priavte:
string vale;
Vector neghbors;
}
问你如何拷贝这个graph?
还挺新颖的，谁给个标准解答？ | g*******y
发帖数: 1930 | | m*****f
发帖数: 1243 | 3 1. traverse the graph use dfs or bfs, make a new object for every node, do a
shallow copy, but push the address of the new object into the neighbor
vector.
2. relink. For each node.
neighbour[x] = neighbour[x]->neighbour[neighbour[x]->neighbour.size()-1]
3. delete the original graph
It's the same idea of the LL with random pointer problem. The key is using
previous data structure to save a link of the new object, copy->relink->
delete. | S**Y
发帖数: 136 | 4 我根据你写的，写下算法，帮我看看对不对：
从source Node开始，用bfs(use a queue),进行traversal,
同时keep一个hash table;
int是一个编号，比如source为1,其邻居为2,3,4
处理source Node 为 一串string-> 1:str:2:3:4 str为节点value直，2/3/4为邻居的编
号, 并且根据编号放进一个array of string ARRAY中，
当bfs traversal到一个Node的时候,先检查他是否在hashTable中，如果不在就hash
ode,编号>到hash table,
并且生成i:string:x:y:z, 放进 ARRAY 中。
其中在第一次discover新Node的时候，只是生成这个新Node的编号，并放进 ARRAY 中，
并不处理它的邻居。只是后来它从Queue pop出来的时候，才从ARRAY中寻找到它（根据
hash table）,并且更新它的邻居。
is this correct?
【在 g*******y 的大作中提到】
: hash;
|
|
